ВУЗ:
Составители:
Рубрика:
РПД ДМ /АИТ -2005
7 Лекции
7.1 Разделы и их содержание
Основные положения теории множеств
. Понятие множества. Способы за-
дания множества. Операции над множествами. Векторы и прямые произведения.
Функции. Отношения.
Комбинаторика
Комбинаторные задачи. Понятие упорядоченной и неупорядоченной вы-
борки. Перестановки и сочетания (с повторениями и без повторений). Основные
комбинаторные числа. Формула Стирлинга. Бином Ньютона. Комбинаторные то-
ждества. Принцип включения-исключения.
Логика
. Основные понятия логики высказываний. Равносильность формул.
Тавтологии. Двойственность. Нормальные формы. Минимизация нормальных
форм. Булева алгебра. Полнота и замкнутость систем логических функций. Логи-
ка предикатов. Понятие предиката, квантора. Применение логики предикатов для
описания математических понятий. Формулы логики предикатов. Интерпретация.
Выполнимость и общезначимость.
Теория графов
. Понятие графа. Способы задания графов. Изоморфизм гра-
фов. Операции над графами. Маршруты, цепи и циклы. Метрические характери-
стики графов. Остовное дерево. Фундаментальная система циклов. Циклический и
коциклический ранги графа. Эйлеровы и Гамильтоновы графы. Деревья. Планар-
ные, двойственные графы. Раскрашивание графов. Основные алгоритмы на гра-
фах и сетях.
Теория алгоритмов
.
Понятие алгоритма. Основные свойства алгоритмов, требования к алгорит-
мам. Машина Тьюринга. Вычисление функций и предикатов на машине Тьюрин-
га. Универсальная машина Тьюринга. Проблема остановки. Канонические систе-
мы Поста.
Конечные автоматы
Конечный автомат как математическая модель устройства с конечной памя-
тью и как управляющая система. Задачи теории автоматов: задача анализа, задача
синтеза, задача полноты, задача эквивалентных преобразований. Способы описа-
ния конечных автоматов. Минимизация конечных автоматов.
Языки и грамматики
Языки и их представления. Формальные грамматики. Место теории фор-
мальных грамматик в математической лингвистике. Порождающая грамматика.
Вывод в порождающей формальной грамматике. Основные классы порождающих
грамматик.
8 Практические занятия
Основные темы:
Основные понятия теории множеств. Способы задания множеств. Операции
над множествами. Использование кругов Эйлера. Векторы и декартово произведе-
РПД ДМ /АИТ -2005
7 Лекции
7.1 Разделы и их содержание
Основные положения теории множеств. Понятие множества. Способы за-
дания множества. Операции над множествами. Векторы и прямые произведения.
Функции. Отношения.
Комбинаторика
Комбинаторные задачи. Понятие упорядоченной и неупорядоченной вы-
борки. Перестановки и сочетания (с повторениями и без повторений). Основные
комбинаторные числа. Формула Стирлинга. Бином Ньютона. Комбинаторные то-
ждества. Принцип включения-исключения.
Логика. Основные понятия логики высказываний. Равносильность формул.
Тавтологии. Двойственность. Нормальные формы. Минимизация нормальных
форм. Булева алгебра. Полнота и замкнутость систем логических функций. Логи-
ка предикатов. Понятие предиката, квантора. Применение логики предикатов для
описания математических понятий. Формулы логики предикатов. Интерпретация.
Выполнимость и общезначимость.
Теория графов. Понятие графа. Способы задания графов. Изоморфизм гра-
фов. Операции над графами. Маршруты, цепи и циклы. Метрические характери-
стики графов. Остовное дерево. Фундаментальная система циклов. Циклический и
коциклический ранги графа. Эйлеровы и Гамильтоновы графы. Деревья. Планар-
ные, двойственные графы. Раскрашивание графов. Основные алгоритмы на гра-
фах и сетях.
Теория алгоритмов.
Понятие алгоритма. Основные свойства алгоритмов, требования к алгорит-
мам. Машина Тьюринга. Вычисление функций и предикатов на машине Тьюрин-
га. Универсальная машина Тьюринга. Проблема остановки. Канонические систе-
мы Поста.
Конечные автоматы
Конечный автомат как математическая модель устройства с конечной памя-
тью и как управляющая система. Задачи теории автоматов: задача анализа, задача
синтеза, задача полноты, задача эквивалентных преобразований. Способы описа-
ния конечных автоматов. Минимизация конечных автоматов.
Языки и грамматики
Языки и их представления. Формальные грамматики. Место теории фор-
мальных грамматик в математической лингвистике. Порождающая грамматика.
Вывод в порождающей формальной грамматике. Основные классы порождающих
грамматик.
8 Практические занятия
Основные темы:
Основные понятия теории множеств. Способы задания множеств. Операции
над множествами. Использование кругов Эйлера. Векторы и декартово произведе-
