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

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

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

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

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

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

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

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

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

Алгоритмы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• выбор метода проектирования алгоритма;

• выбор формы записи алгоритма (блок-схемы, псевдокод и др.);

• выбор тестов и метода тестирования;

• проектирование алгоритма.

4. Программирование:

• выбор языка программирования;

• уточнение способов организации данных;

• запись алгоритма на выбранном языке

программирования.

5. Тестирование и отладка:

• синтаксическая отладка;

• отладка семантики и логической структуры;

• тестовые расчеты и анализ результатов тестирования;

• совершенствование программы.

6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5.

7. Сопровождение программы:

• доработка программы для решения конкретных задач;

• составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию