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

Материалы по математике, 2011-12 учебный год, НИУ ВШЭ и РЭШ
Перейти к: навигация, поиск
  • Лекции читает: Кудряшов Юрий Георгиевич
  • Семинары ведут: Кудряшов Юрий Георгиевич, Щуров Илья Валерьевич
  • Учебные ассистенты: Александра Пушкарь

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

  • Домашнее задание после 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].

  1. Тюрин Ю. Н., Макаров А. А., Высоцкий И. Р., Ященко И. В. Теория вероятностей и статистика (учебное пособие для учащихся 7—9 классов). М.: МЦНМО, 2008
  2. Тюрин Ю. Н., Макаров А. А., Симонова Г. И. Теория вероятностей. Учебник для экономических и гуманитарных специальностей. М.: МЦНМО, 2009.
  3. Кремер. Н. Ш. Теория вероятностей и математическая статистика. М.: Юнити-Дана, 2010.

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

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