ПРОГРАММА

Государственного экзамена по информатике на математическом факультете мпгу по специальностям «Информатика» и «Информатика» с дополнительной специальностью «Математика» в 2011/12 уч.Г.

Дискретная математика

Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на разложение шаров по ящикам.

Принцип включения и исключения. Число разложений n различимых шаров по k различимым ящикам при условии того, что ящики не могут быть пустыми. Число представлений n–множества в виде объединения k непустых непересекающихся подмножеств.

Понятие рекуррентного соотношения. Биномиальные коэффициенты, их комбинаторная интерпретация. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля.

Производящие функции. Применение производящих функций для решения рекуррентных соотношений. Явная формула для чисел Фибоначчи.

Числа Каталана. Явная формула для чисел Каталана. Примеры перечислительных задач, решением которых являются числа Каталана.

Основные понятия теории графов. Способы задания графов. Изоморфизм графов. Понятие инварианта графа. Примеры инвариантов графа.

Связные графы. Компоненты связности графа. Число компонент связности графа, имеющего p вершин и q ребер. Необходимое условие связности графа.

Деревья. Основные свойства деревьев. Остов графа. Задача о минимальном остове.

ЛИТЕРАТУРА

Основная

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005.

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

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

4. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. Основы информатики. М.: Мир, 1998.

5. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.Наука, 1977.

6. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982

Математическая логика

Алгебра высказываний. Таблицы истинности для основных логических операций. Выполнимые и общезначимые формулы алгебры высказываний. Основные равносильности алгебры высказываний. Совершенная дизъюнктивная нормальная форма.

Исчисление высказываний. Доказуемые и выводимые формулы в исчислении высказываний. Непротиворечивость и полнота исчисления высказываний. Теорема дедукции. Семантика исчисления высказываний. Непротиворечивость и полнота исчисления высказываний.

Алгебра предикатов. Выполнимые и общезначимые формулы алгебры предикатов. Основные равносильности алгебры предикатов.

Исчисление предикатов. Доказуемые и выводимые формулы в исчислении предикатов. Семантика исчисления предикатов. Непротиворечивость исчисления предикатов.

ЛИТЕРАТУРА

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

2. Тимофеева И.Л. Курс лекций по математической логике. ч. I, II. – М.: Прометей, 2003.

Теория алгоритмов

Понятие алгоритма. Основные свойства алгоритма. Вычислимые функции. Основные вычислительные модели. Тезис Черча.

Пример невычислимой функции. Алгоритмические проблемы. Проблема останова, ее алгоритмическая неразрешимость. Понятие алгоритмической сводимости. Теорема Успенского-Райса. Примеры алгоритмически неразрешимых проблем в информатике.

Понятие сложности алгоритма. Сложность основных алгоритмов сортировки. Оценка сложности рекурсивного алгоритма. Дихотомический алгоритм возведения в степень.

Полиномиальные алгоритмы, их важность для информатики. Понятие класса сложности. Классы P и NP. Проблема перебора.

Полиномиальная сводимость. NP-полные проблемы. Задача о выполнимости коньюнктивной нормальной формы. Примеры NP-полных проблем. Важность теории NP-полноты для практического программирования.

ЛИТЕРАТУРА