2011/2012 — Весенний семестр

Разделы

Элементы дискретной математики и математической кибернетики

Годовой курс по выбору.

Проходит: по понедельникам с 18:30 до 20:00, первое занятие 27 февраля. Аудитория: 115 КПМ.

Лектор: Бурцев А. А., к. ф.-м. н., доцент каф. высшей математики МФТИ.

Курс рассчитан на студентов 1-го курса и на студентов, у которых не было или нет соответствующего основного курса. Курс по выбору представляет собой дополнительные главы к основным соответствующим курсам.

Итоговый экзамен по вопросам следующей программы.

Программа.

1. Функции алгебры логики. Элементарные функции. Формулы. Реализация функуий формулами.

2. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности. Цепи эквивалентностей.

3. Разложение булевых функций по переменным. Разложение по одной переменной Разложение по всем переменным. Совершенная дизъюнктивная нормальная форма Совершенная конъюнктивная нормальная форма.

4. Применение к естественному языку. Сокращённые таблицы. Задача Кислера.

5. Полиномы Жегалкина.

6. Полнота и замкнутость. Базисы. Важнейшие замкнутые классы (то есть, классы линейных, монотонных и самодвойственных функций, классы Т-ноль и Т-один).

7. Критерий полноты. Примеры полных и минимальных полных систем.

8. k-значные логики и их особенности. Представление о результатах Поста, Янова и Мучника.

9. Схемы из функциональных элементов. Сложность и глубина схем. Элементарные методы синтеза. Функции Шеннона. Нижняя оценка для L(n).

10. Метод Шеннона.

11. Метод Лупанова.

12. Метод Карацубы.

13. Метод Тоома.

14. Теорема об умножении целых чисел с почти линейной сложностью.

15. Конечные поля и их квадратичные расширения. Сложность арифметики в GF(49).

16. Метод дискретного преобразования Фурье. Умножение многочленов седьмой степени над GF(49) методом Фурье 16-го порядка.

17. Элементы комбинаторного анализа: перестановки, размещения, сочетания, сочетания с повторениями, Группы подстановок. Индикаторы (характеристические функции) множеств. Формула включений-исключений. Бином Ньютона и его следствия. Метод производящих функций- Возвратные последовательности. Формулы Стерлинга и Валлиса. Многочлен Лагранжа.

18. Множества и операции над ними. Принцип двойственности. Мощности. Теоремы Кантора и Кантора Бернштейна. Теорема Цермело-Кантора. Существование собственных классов. Арифметика кардиналов. Континуум — гипотеза (в формулировке Кантора). Аксиомы теории множеств по Цермело-Френкелю. Упорядоченная пара по Куратовскому и по Винеру.

19. Отношения. Бинарные отношения. Отношения эквивалентности и частичного порядка. Фактор-множество. Максимальный и наибольший элементы. Упорядоченные и вполне упорядоченные множества. Изоморфизм упорядоченных множеств. Порядковые числа (ординалы).

20. Фундированные множества Математическая (финитная и трансфинитная индукция). Базис Гамеля. Всюду определённая на R числовая функция, такая, что f(x+y)=f(x)+f(y) для всех х и у из R, которая не есть умножение на константу.

21. Функции и их графики. Биекции, сюрьекции, инъекции. Лемма о сюръективном и инъективном отображениях. Существование и единственность обратного отображения. Понятие о группе.

Литература

Основная:

1. С. В. Яблонский. Введение в дискретную математику. М., Высшая школа, 2001. Часть I, глава 1, глава 2; часть II; часть V, глава 2.

2. Д. Кнут. Искусство программирования. Том 2. Параграфы о методе Карацубы и о методе Тоома.

3. Н. К. Верещагин, А. Шень. Начала теории множеств. М., МЦМНО, 2002.

4. А. И. Кострикин. Введение в алгебру. М., Наука, 1977.

5. Ноден, Китте. Алгебраическая алгоритмика. М., Мир, 1999. (Здесь о ДПФ).

6. О. Б. Лупанов. Асимптотические оценки сложности управляющих систем. Издательство МГУ, 1984.

7. Гаврилов, Сапоженко. Задачи и упражнения по дискретной математике. М., физматлит, 2004.

Дополнительная:

8. С. Клини. Математическая логика. М., «Мир», 1973. Глава I и приложения.

9. И. А. Лавров. Л. Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. М., физматлит, 2004.

10. Успенский, Верещагин, Плиско. Вводный курс математической логики. М., физматлит, 2004.

11. Н. Я. Виленкин. Рассказы о множествах. М., МЦМНО, 2005.

12. Дискретная математика и математические вопросы кибернетики. Под общей редакцией С. В. Яблонского и О. Б. Лупанова, М., Наука, 1974.

13. Лидл, Нидеррайтер. Конечные поля. Том 1. Том 2. (для углублённого изучения)

14. Болотов, Фролов, Гашков, Часовских, Элементарное введение в эллиптическую криптографию. М., КомКнига, 2006. (Здесь кратко о конечных полях).

Что развивает курс (данные для «Вектора»)

Алгоритмы и методы анализа данных (развивает косвенно)
Проектирование аппаратуры (языки описания аппаратуры, работа с САПР и др.) (развивает косвенно)

Информация о развиваемых компетенциях занесена в систему для работы «Вектора». Поскольку занесение информации производится редакторами проекта, а не авторами курсов, информация может быть неполной или даже частично неверной. Если Вы нашли ошибку, напишите нам об этом. См. также подробнее о системе «Вектор» и полный список компетенций.