МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)

Главная  

О кафедре  

Программы  

Учебные пособия  

Публикации  

Гранты  

Экзамены  

Труды семинара  

:: Программы

По данному запросу не найдено записей!

» Версия для печати

Лекции

ЛЕКЦИЯ 1. Теория булевых функций, отношение эквивалентности. Логика предикатов, логика высказываний. Диаграмма Эйлера — Венна. Множество истинностных значений. Логическая переменная. Логическая функция. Отрицание логической переменной, логической функции. Таблица истинности логической функции. Операции булевой логики.

ЛЕКЦИЯ 2. Булевы функции от двух переменных. Дизъюнкция, ее таблица истинности. Конъюнкция, ее таблица истинности. Двойственность конъюнкции и дизъюнкции.

ЛЕКЦИЯ 3. Стрелка Пирса и штрих Шеффера, их таблицы истинности. Разность и импликация, их таблицы истинности. Симметрическая разность и эквивалентность, их таблицы истинности. Формы представления булевых функций.

ЛЕКЦИЯ 4. Понятие конституенты. Тавтология и противоречие. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма и совершенная полиномиальная нормальная форма представления логических функций. Принцип двойственности в теории булевых функций. Нахождение булевой функции по ее таблице истинности.

ЛЕКЦИЯ 5. Методы доказательств в теории булевых функций. Правила теории булевых функций: законы идемпотентности, законы коммутативности, законы ассоциативности, законы дистрибутивности, законы нуля и единицы, законы поглощения, законы де Моргана, законы склеивания.

ЛЕКЦИЯ 6. Независимая система правил теории булевых функций: законы коммутативности, законы ассоциативности, законы дистрибутивности, законы нуля и единицы.

ЛЕКЦИЯ 7. Аксиоматический и конструктивный методы доказательств в логике Буля. Доказательства законов логики Буля: идемпотентности, поглощения, законов де Моргана, законов склеивания с помощью независимой системы законов логики Буля.

ЛЕКЦИЯ 8. Понятие предиката. Операции над предикатами и кванторами. Логика предикатов. Построение доказательств в логике предикатов.

ЛЕКЦИЯ 9. Логика высказываний. Понятие высказывания. Создание сложных высказываний с помощью отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности. Понятие логического круга. Строгая дизъюнкция. Язык и метаязык, объектные и субъектные высказывания. Парадокс лжеца. Парадокс Рассела о парикмахере.

ЛЕКЦИЯ 10. Построение доказательств в логике высказываний. Символ импликации в теории булевых функций. Посылка и заключение, понятие клаузы. Отношение порядка, законы рефлексивности, антисимметричности и транзитивности.

ЛЕКЦИЯ 11. Сортировка данных и ее алгоритмы. Линейный выбор. Линейный выбор с обменом. Стандартный обмен (метод “пузырька”). Челночная сортировка. Сортировка Шелла. Сортировка по методу Неймана.

ЛЕКЦИЯ 12. Линейная вставка. Центрированная и двоичная вставки. Центрированная вставка. Двоичная вставка. Быстрая сортировка по методу Quicksort (метод Хоара). Быстрая сортировка по методу Heapsort (метод Уильямса).

ЛЕКЦИЯ 13. Поиск данных и его алгоритмы. Последовательный (линейный) поиск. Бинарный (двоичный) поиск. Интерполяционный поиск.

ЛЕКЦИЯ 14. Передача информации, кодирование. Кодировка и декодировка. Оптимальное, корректирующее и секретное кодирование. Информационная избыточность. Экономичность кода, средняя длина кодового слова. Кодирование по методу Фано. Префиксное кодирование и по методу Хаффмана. Оптимальное кодирование по методу Фано и Хаффмана.

ЛЕКЦИЯ 15. Криптография. Понятие бита, механическая интерпретация понятия бита. Системы счислений. Хранение информации в ЭВМ.

ЛЕКЦИЯ 16. Код “Горячей линии Белый Дом — Кремль”. Создание электронной подписи. Передача 8-битовой информации по 6-битовым каналам.

Практика

ЗАНЯТИЕ 1. Теория булевых функций. Логика предикатов, логика высказываний. Диаграмма Эйлера — Венна.

ЗАНЯТИЕ 2. Булевы функции от двух переменных. Нахождение булевой функции по ее таблице истинности.

ЗАНЯТИЕ 3. Методы доказательств в теории булевых функций. Правила теории булевых функций.

ЗАНЯТИЕ 4. Аксиоматический и конструктивный методы доказательств в теории булевых функций.

ЗАНЯТИЕ 5. Построение доказательств в логике предикатов. Построение доказательств в логике высказываний.

ЗАНЯТИЕ 6. Сортировка данных и ее алгоритмы.

ЗАНЯТИЕ 7. Поиск данных и его алгоритмы.

ЗАНЯТИЕ 8. Передача информации, кодирование.

Курсовые работы

Курсовых работ нет.

Рекомендуемая литература

Основная

1. Бабаш А. В. Криптография, М., Солон, 2000.

2. Василенко О. Н. Теоретико-числовые алгоритмы в криптогра-фии, М., МЦНМО, 2003.

3. Жемерев А. В. Введение в булеву логику. Методическое пособие для студентов 2-го факультета МАТИ. М., МАТИ, 2003.

4. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., Лаборатория базовых знаний, 2001.

5. Мендельсон Э. Введение в математическую логику, М., Наука, 2000.

6. Романовский И.В. Дискретный анализ, СПб., Невский диалект, 2001.

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

7. Виленкин Н.Я, Ивашев-Мусатов О.С, Шварцбурд С.И. Алгебра и математический анализ для 11 класса, М., Просвещение, 1995.

8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М., Энергоатомиздат, 1988.

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

10. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М., Изд-во МАИ, 1993.

11. Новиков Ф.А. Дискретная математика для программистов. СПб., Питер, 2001.

12. Яблонский С.В. Введение в дискретную математику, М., Выс-шая школа, 2001.