ВУЗ:
Составители:
Рубрика:
РПД ДМ /АИТ -2005
ние множеств. Способы задания отношений. Свойства отношения. Отношение эк-
вивалентности. Отношения порядка.
Сочетания, перестановки, размещения. Комбинаторные задачи.
Построение таблиц истинности. Доказательство равносильности формул. До-
казательство тавтологий.
ДНФ и КНФ. Приведение формул к СДНФ и СКНФ.
Упрощение формул. Составление СДНФ и СКНФ по таблицам истинности.
Алгоритмы построения минимальных ДНФ и КНФ.
Основные
понятия булевой алгебры. Исследование полноты системы логиче-
ских функций (использование теоремы Поста).
Способы задания графов. Матрицы смежности, инцидентности, достижимо-
сти, контрдостижимости. Операции над графами.
Доказательство изоморфизма графов. Определение основных метрических
характеристик графов.
Нахождение Эйлеровых и гамильтоновых циклов в графах. Построение ос-
товного дерева и ассоциированной с ним фундаментальной системы циклов.
Построение двойственных графов. Доказательство планарности графов (тео-
рема Куратовского). Раскрашивание графов.
Алгоритмы нахождения кратчайших путей в графах. Алгоритмы обхода гра-
фов.
Машина Тьюринга. Вычисление функций на машине Тьюринга.
Описание автоматов. Эквивалентность автоматов. Минимизация автоматов.
Построение синтаксических диаграмм и деревьев. Построение цепочек тер-
минальных символов.
9 Лабораторные занятия
9.1 Основные темы:
1. Теория множеств. (4 часа)
2. Способы задания неориентированных графов. Вычисление основных мет-
рических характеристик графов. Операции над графами. Отождествление,
расщепление вершин графа. Стягивание и удаление ребер графа.(5 часов)
3. Синтез логических схем с помощью логических элементов.(4 часа)
4. Разработка алгоритмов для абстрактных машин Тьюринга и Поста и и от-
ладка их с помощью
интерпретатора. (4 часа)
10 Семинарские занятия
Не предусмотрено.
11 Другие виды аудиторных занятий
Не предусмотрено.
РПД ДМ /АИТ -2005
ние множеств. Способы задания отношений. Свойства отношения. Отношение эк-
вивалентности. Отношения порядка.
Сочетания, перестановки, размещения. Комбинаторные задачи.
Построение таблиц истинности. Доказательство равносильности формул. До-
казательство тавтологий.
ДНФ и КНФ. Приведение формул к СДНФ и СКНФ.
Упрощение формул. Составление СДНФ и СКНФ по таблицам истинности.
Алгоритмы построения минимальных ДНФ и КНФ.
Основные понятия булевой алгебры. Исследование полноты системы логиче-
ских функций (использование теоремы Поста).
Способы задания графов. Матрицы смежности, инцидентности, достижимо-
сти, контрдостижимости. Операции над графами.
Доказательство изоморфизма графов. Определение основных метрических
характеристик графов.
Нахождение Эйлеровых и гамильтоновых циклов в графах. Построение ос-
товного дерева и ассоциированной с ним фундаментальной системы циклов.
Построение двойственных графов. Доказательство планарности графов (тео-
рема Куратовского). Раскрашивание графов.
Алгоритмы нахождения кратчайших путей в графах. Алгоритмы обхода гра-
фов.
Машина Тьюринга. Вычисление функций на машине Тьюринга.
Описание автоматов. Эквивалентность автоматов. Минимизация автоматов.
Построение синтаксических диаграмм и деревьев. Построение цепочек тер-
минальных символов.
9 Лабораторные занятия
9.1 Основные темы:
1. Теория множеств. (4 часа)
2. Способы задания неориентированных графов. Вычисление основных мет-
рических характеристик графов. Операции над графами. Отождествление,
расщепление вершин графа. Стягивание и удаление ребер графа.(5 часов)
3. Синтез логических схем с помощью логических элементов.(4 часа)
4. Разработка алгоритмов для абстрактных машин Тьюринга и Поста и и от-
ладка их с помощью интерпретатора. (4 часа)
10 Семинарские занятия
Не предусмотрено.
11 Другие виды аудиторных занятий
Не предусмотрено.
