2 Семестр

1. Элементы математической логики. АВ, ИВ, ИП.

2. Язык ИВ, пример.

3. Аксиомы и правила вывода в ИВ, пример.

4. Соответствие между формулами АВ и ИВ, пример.

5. Непротиворечивость ИВ.

6. Полнота ИВ.

7. ИП. Формулы ИП, пример.

8. Аксиомы и правила образования выводимых формул в ИП, пример.

9. Понятие интерпретации, пример.

10. Выполнимость формулы 1-го порядка, пример.

11. Общезначимость формулы 1-го порядка, пример.

12. Детерминированные функции, их свойства, пример.

13. Способ задания д. функций, пример.

14. Вес д. функции, пример.

15. О.-д. функции, пример.

16. Способы задания о.-д. функций.

17. Усеченное дерево, пример.

18. Диаграмма Мура, пример.

19. Канонические таблицы, пример.

20. Канонические уравнения, пример.

21. Операции над о.-д. функциями.

22. Операция суперпозиции. Замкнутость классов о.-д. функций относительно этой операции.

23. Операция обратной связи. Замкнутость классов о.-д. функций относительно этой операции.

24. Полнота системы о.-д. функций.

25. Пример полных систем.

26. Пример универсальной о.-д. функции.

27. Проблема распознавания полноты систем о.-д. функций.

28. Машины Тьюринга.

29. Методы построения машин Тьюринга.

30. Описание технологии программирования для машин Тьюринга.

31. Машинные коды и их преобразования.

32. Вычислимые функции.

33. Операции суперпозиции, примитивной рекурсии и минимизации.

34. Классы вычислимых и рекурсивных функций.

35. Тезис Черча, тезис Тьюринга.

36. Эквивалентность класса рекурсивных функций и функций, вычислимых на ма­шинах Тьюринга.

37. Коды. Задачи теории кодирования.

38. Алфавитное кодирование.

39. Однозначность декодирования (теорема 1, теорема 2).

40. Критерий однозначности декодирования.

41. Теорема А.А. Маркова.

42. Алгоритм распознавания однозначности декодирования (на языке графов).

43. Разделимые коды. Неравенство Крафта-Макмиллана для разделимых кодов.

44. Условие существования разделимого кода с заданными длинами кодовых слов.

45. Оптимальные коды. Теорема редукции.

46. Метод Хаффмана построения оптимального кода.

47. Равномерное кодирование. Самокорректирующиеся коды.

48. Коды Хэмминга.

49. Применение кодирования для защиты информации.

50. Криптография.

Литература Основная

1. Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. – М.: Наука, 1979, 1986 (2-е изд., перераб. и доп.), 2001 (3-е изд., стер.).

2. Яблонский, С.В. Методические разработки по курсу «Элементы дискретной математики» / С.В. Яблонский. – М.: Изд-во МГУ, 1971.

3. Яблонский, С.В. Дискретная математика и математические вопросы кибернетики / С.В. Яблонский, О.Б. Лупанов. – М.: Наука, 1974.

4. Гаврилов, Г.П. Сборник задач по дискретной математике / Г.П. Гаврилов, А.А. Сапоженко. – М.: Наука, 1977, 1991 (2-е изд., перераб. и доп.), 2004 (3-е изд., перераб.).

5. Алексеев, В.Б. Лекции по дискретной математике: учебное пособие / В.Б. Алексеев. – М.: Изд. отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2004. – 76 с.

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

К разделу 1

1. Ежов, И.И. Элементы комбинаторики / И.И. Ежов, А.В. Скороход, М.Л. Ядренко. – М.: Наука, 1987.

2. Райзер, Г. Комбинаторная математика / Г. Райзер. – М.: Мир, 1966.

3. Рыбников, К.А. Введение в комбинаторный анализ / К.А. Рыбников. – М.: Изд-во МГУ, 1985.

4. Холл, М. Комбинаторика / М. Холл. – М.: Мир, 1970.

К разделу 2

1. Яблонский, С.В. Функции алгебры логики и классы Поста / С.В. Яблонский, Г.П. Гаврилов, В.Б. Кудрявцев. – М.: Наука, 1966.

2. Михеева, Е.А. Индивидуальные задания для математического практикума на ЭВМ по «Дискретной математике»: методические указания / Е.А. Михеева. – Ульяновск: фМГУ, 1995. – 49 с.

К разделу 3

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

2. Алексеев, В.Б. Элементы теории графов и схем: методическая разработка / В.Б. Алексеев, С.А. Ложкин. – М.: Изд-во МГУ, 1991.

3. Алексеев, В.Б. Элементы теории графов, схем и автоматов: учебное пособие для студентов / В.Б. Алексеев, С.А. Ложкин. – М.: Изд. отдел ф-та ВМиК МГУ, 2002. – 58 с.

4. Ложкин, С.А. Лекции по основам кибернетики: учебное пособие / С.А. Ложкин. – М.: Изд. отдел ф-та ВМиК МГУ, 2004. – 256 с.

К разделу 4

1. Оре, О. Теория графов / О. Оре. – М.: Наука, 1968.

2. Харари, Ф. Теория графов / Ф. Харари. – М.: Мир, 1973.

3. Уилсон, Р. Введение в теорию графов / Р. Уилсон. – М.: Мир, 1977.

К разделу 5

1. Новиков, П.С. Элементы математической логики / П.С. Новиков. – 2-е изд. – М.: Наука, 1973.

2. Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. – М.: Наука, 1976.

3. Игошин, В.И. Задачник-практикум по математической логике / В.И. Игошин. – М.: Просвещение, 1986.

К разделу 6

1. Кудрявцев, В.Б. Введение в теорию автоматов / В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М.: Наука, 1986.

К разделу 7

1. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – М.: Наука, 1975.

2. Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. – М.: Наука, 1965.

3. Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. – М.: Мир, 1972.

4. Эббинхауз, Г.Д. Машины Тьюринга и рекурсивные функции / Г.Д. Эббинхауз, К. Якобо, Ф.К. Ман, Г.М. Хермес. – М.: Мир, 1972.

5. Ляпунов, А.А. О логических схемах программ / А.А. Ляпунов // Проблемы кибернетики. – Вып. 1. – М.: Физматгиз, 1958. – С. 46-74.

К разделу 8

1. Марков, А.А. Введение в теорию кодирования / А.А. Марков. – М.: Наука, 1982.