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

Содержание самостоятельной работы

Предварительные сведения.
Решение задач по теории множеств и комбинаторике.
Булевы функции
Решение задач на построение совершенных ДНФ и КНФ, сокращенных ДНФ, многочленов Жегалкина, доказательство эквивалентности булевых формул, определение полноты систем булевых функций.
Графы
Решение задач на представление графов, нахождение графа достижимости, нахождение баз графа, представление формул деревьями, обходы деревьев, проверку двудольности графа, построение Эйлерова цикла, нахождение минимального остовного дерева, обходы графа "в глубину", поиск кратчайших путей из одного источника. 
Применение графов для представления булевых функций.
Решение задач на построение логических схем по булевым функциям и на анализ логических схем, на построение сокращенных УБДР по формулам.
Конечные автоматы - 1
Решение задач на конструирование конечных автоматов с выходом, конструирование конечных автоматов по описанию языка, на детерминизацию недетерминированных конечных автоматов.
Конечные автоматы - 2
Решение задач следующих типов:
Алгоритмы -1: структурированные программы.
Решение задач на построение структурированных программ для арифметических функций.
Алгоритмы - 2: частично рекурсивные функции.
Решение задач на реализацию арифметических функций рекурсивными описаниями.
Алгоритмы-2: машины Тьюринга
Решение задач на построение машин Тьюринга для арифметических функций.