Дискретная математика для лингвистов

Материал из MathINFO
Перейти к навигации Перейти к поиску
  • Семинары ведут: Кудряшов Юрий Георгиевич, Щуров Илья Валерьевич
  • Учебные ассистенты: Александра Пушкарь

Домашние задания

  • Домашнее задание после 1-го занятия: задача №3 из первого листка. Крайний срок сдачи — 18.09.2011 (по e-mail ling-dm на math-hse точка info). Напоминаем, что надо записывать не только ответ, но и решение. Например, текст, содержащий только количество ходов без дополнительных обоснований, решением не является. С примером оформления доказательства оптимальности алгоритма можно ознакомиться в дополнении к конспекту первой лекции.

Материалы

Индукция и рекурсия

Дата Тема Дополнительные материалы
6.09.2011
 Лекция «Ханойская башня: рекурсия и индукция»
8.09.2011
 Листок «Рекуррентные соотношения и математическая индукция»
15.09.2011
 Листок «Математическая индукция: ошибки и доказательство тождеств»

Комбинаторика

Дата Тема Дополнительные материалы
20.09.2011
 Лекция «Комбинаторика: введение» (список разобранных задач и ответов)
 См. также: в книге Виленкина Н. Я. Комбинаторика:
  • глава 1: Общие правила комбинаторики
  • глава 2: Размещения, перестановки, сочетания.
22.09.2011
 Листок «Комбинаторика: введение»
 Краткие решения задач, разобранных на семинаре
29.09.2011
 Листок «Комбинаторика — 2»
 О двух задачах из ДЗ№2 (задачи 2 и 3c)
04.10.2011
 Лекция «Бином Ньютона»
24.10.2011
 Краткие решения прошедшего зачёта

Теория вероятностей

Дата Тема Дополнительные материалы
18.10.2011
 Лекция «Основные понятия теории вероятностей»
31.10.2011
 Листок Классическое определение вероятности
01.11.2011
 Лекция «Условная вероятность и независимые события»
7.11.2011
 Листок Условная вероятность и независимость
14.11.2011
 Листок Формула полной вероятности и формула Байеса
15.11.2011
 Лекция «Дискретные случайные величины»
21.11.2011
 Листок Обзор и формула Байеса
28.11.2011
 Листок Дискретные случайные величины
29.11.2011
 Лекция «Дисперсия случайной величины»

Введение в математическую логику

Дата Тема Дополнительные материалы
20.01.2012
 Лекция «Основные понятия математической логики»
23.01.2012
 Листок Математическая логика

Введение в теорию графов

Дата Тема Дополнительные материалы
6.02.2012
 Листок «Теория графов — 1»
13.02.2012
 Листок «Теория графов — 2»
20.02.2012
 Листок «Теория графов — 3»

Делимость

Дата Тема Дополнительные материалы
27.02.2012
 Листок «Делимость»
5.03.2012
 Листок «НОД: алгоритм Евклида»
12.03.2012
 Листок «Алгоритм Евклида и линейное представление НОД»

Конечные автоматы и регулярные выражения

Дата Тема Дополнительные материалы
16.04.2012
 Листок «Регулярные выражения»
14.05.2012
 Листок «Недетерминированные конечные автоматы»
 Курсы М. Р. Пентуса

Теория информации

Дата Тема Дополнительные материалы
23.05.2012
 Листок «Количество информации»

Литература

Базовый учебник

  • Кнут Д., Грэхем Ф., Поташник О. Конкретная математика. Основание информатики. М. «Мир», 1998. (или любое другое издание)

Комбинаторика

  • Виленкин Н. Я. Комбинаторика. М., «Наука», 1969 (или любое другое издание).

Теория вероятностей

Мы рекомендуем всем, кто берётся изучать вероятность и статистику, начать с учебника для школьников [1]. Те, кто полностью понимает всё, изложенное в этом учебнике, могут приступать к изучению [2]. На более глубоком уровне существует много учебников по вероятности и статистике. Например, можно читать [3].

Конечные автоматы

Курсы М. Р. Пентуса

Источник — http://math-info.hse.ru/wiki2011-12/index.php?title=Дискретная_математика_для_лингвистов&oldid=16