Основы дискретной математики.

Элементы теории множеств. Комбинаторика.

Множества. Мощность множества. Операции над множествами. Прямое произведение множеств.
Подмножества. Мультимножества.
Бинарные отношения. Отношение эквивалентности.
Выборки с повторением и без повторения.
Размещения и сочетания. Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля.
Мультиномиальные коэффициенты.
Числа Стирлинга и их свойства.
Разложение и разбиение натуральных чисел. Формулы для числа разложений и числа разбиений.
Перестановки множеств. Произведение перестановок. Циклы перестановок. Разложение перестановки на циклы. Число перестановок заданного типа.
Принцип включения-исключения. Задача о беспорядках. Мощность объединения множеств.

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

Алгебра логики. Функции алгебры логики. Элементарные функции. Формулы. Эквивалентность формул.
Разложение функций алгебры-логики по переменным.
Дизъюнктивная и конъюнктивная нормальные формы. Существование и единственность представления функции алгебры логики в СДНФ и СКНФ.
Полином Жегалкина.
Принцип двойственности. Замкнутые классы функций. Несамодвойственные функции. Немонотонные функции. Нелинейные функции.
Необходимые и достаточные условия полноты системы функций алгебры логики.
Исчисления высказываний. Аксиомы и правила вывода исчисления высказываний.
Полнота исчисления высказываний. Независимость аксиом исчисления высказываний.
Исчисление предикатов. Примеры описания утверждений на языке исчисления предикатов.

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

Определения алгоритма. Машины Тьюринга. Вычислимые функции. Существование невычислимой функции. Максимальная продуктивность машины Тьюринга с n состояниями.
Сложность алгоритма. Полиномиально разрешимые задачи. Полиномиальная сводимость.
Классы P и NP. NP-полные и NP-трудные задачи. NP-полнота задачи 3 ВЫПОЛНИМОСТЬ.

Теория графов.

Различные виды и определения графов. Мультиграфы и псевдографы. Ориентированные и неориентированные графы.
Простейшие свойства графов. Матрицы смежности и инциденции. Степени вершин графов. Теорема о степенях.
Подграфы, суграфы и остовные графы. Операции над графами. Полные и пустые графы. Дополнение графа.
Маршруты и пути в графе. Связность. Компоненты связности. Сильная связность ориентированных графов.
Изоморфизм графов. Инварианты графов.
Эйлеровы и Гамильтоновы графы.
Раскраски графа. Хроматическое число.
Примеры NP-полных задач на графах: размер максимальной клики, изоморфизм подграфу, хроматическое число.

Алгоритмы.

Алгоритм поиска минимального остовного дерева графа.
Задача коммивояжера. Приближенные алгоритмы решения.
Алгоритмы поиска кратчайших путей в графе.
Поиск в глубину и поиск в ширину в графе.
Двудольные графы. Построение наибольшего паросочетания.
Алгоритм древесной сортировки. Алгоритм быстрой сортировки.
Структуры данных и операции с ними. Массивы. Стеки. Очереди. Списки. Хэши. Деревья.

Этапы решения задач на ЭВМ.

Программирование (programming) - теоретическая и практическая деятельность, связанная с созданием программ. Решение задач на компьютере включает в себя следующие основные этапы, часть из которых осуществляется без участия компьютера.

1. Постановка задачи:

• сбор информации о задаче;

• формулировка условия задачи;

• определение конечных целей решения задачи;

• определение формы выдачи результатов;

• описание данных (их типов, диапазонов величин, структуры и т. п.).

2. Анализ и исследование задачи, модели:

• анализ существующих аналогов;

• анализ технических и программных средств;

• разработка математической модели;

• разработка структур данных.

3. Разработка алгоритма: