|
Читайте также: |
1. Практические занятия – (4 часа).
2. Защита курсового проекта.
На протяжении 1-го и 2-го семестров проводятся консультации каждую нечетную субботу в соответствии с расписанием.
СТРУКТУРА ДИСЦИПЛИНЫ
Раздел 1. Задачи оптимизации на конечных множествах
Материал раздела излагается во время лекционных занятий в первом семестре.
Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 4…55;
Задание на контрольную работу № 1 состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
- Вопросы и задачи к параграфу 1.2.6 стр. 24 (задание В)
- Вопросы и задачи к параграфу 1.2.8 стр. 31 (задание Д)
- Вопросы и задачи к параграфу 1.4.3 стр. 44 (задание В)
Вопросы для самопроверки
1. Отношения. Основные свойства отношений.
2. Отношение эквивалентности. Отношение толерантности.
3. Отношения порядка. Линейное упорядочение.
4. Наибольший и максимальный элементы.
5. Задача о покрытии. Минимальные и кратчайшие покрытия.
6. Сокращение таблицы покрытий.
7. Разложение таблицы покрытий по столбцу.
8. Совместимые подмножества. Метод граничного перебора.
9. Комбинаторика. Основные виды наборов.
Раздел 2. Задачи оптимизации на графах.
Материал раздела излагается во время лекционных занятий во втором семестре. Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 55…116;
Задание на курсовую работу (Часть1) состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
- Вопросы и задачи к параграфу 2.1 стр. 57
- Вопросы и задачи к параграфу 2.2 стр. 66 (задание В)
- Вопросы и задачи к параграфу 2.4 стр. 77 (задания А, Б, В)
- Параграф 2.7.4 Построение максимального потока. Варианты стр.102
Вопросы для самопроверки
1. Пути в графе. Кратчайший путь. Волновой алгоритм в
не взвешенном и во взвешенном графе.
2. Алгоритм Дейкстры построения кратчайшего пути.
3. Понятие связности. Построение компоненты связности в
ненаправленном и направленном графах.
4. Циклы в графе. Понятие системы независимых циклов.
5. Цикломатическое число. Построение фундаментальной системы циклов на основе остова.
6. Алгоритм построения остова. Алгоритм Краскала
построения минимального остова.
7. Задача о раскраске графа. Хроматическое число. Алгоритм
решения задачи кратчайшей раскраски графа.
8. Определение потока в сети. Задача о максимальном потоке.
9. Алгоритм Форда-Фалкерсона.
10. Определение потока в сети. Задача о минимальном потоке.
11. Планарные графы. Теорема о четырех красках и системе циклов.
12. Алгоритм построения плоского изображения графа.
Раздел 3. Булевы функции и алгоритмические преобразования
Материал раздела излагается во время лекционных занятий в третьем семестре. Дополнительную информацию по данному разделу можно получить из следующих источников:
[2] стр. 116…197;
Задание на курсовую работу (Часть2) состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:
- Вопросы и задачи к параграфу 3.2 стр. 136 (задание Б)
- Вопросы и задачи к параграфу 3.5 стр. 171 (задание А, В, Г)
Вопросы для самопроверки
1. Что такое булева функция?
2. Основные виды булевых функций.
3. Аксиомы и теоремы булевой алгебры.
4. Совершенная дизъюнктивная нормальная форма.
5. Совершенная конъюнктивная нормальная форма.
6. Метод Квайна-Мак-Класки минимизации булевых функций.
7. Что такое простая импликанта?
8. Что такое безызбыточная ДНФ?
9. Алгоритм построения кода Грея.
10. Матричные формы в позиционном коде и в коде Грея.
Необходимым условием допуска к экзамену по предмету является качественно выполненные и защищенные контрольные работы № 1,2, а также защищенная курсовая работа.
Варианты заданий и краткие методические указания по выполнению курсового проекта определены в [2] (стр. 84-108).
Консультации по всем видам работ, предусмотренных рабочей программой дисциплины, проводит преподаватель по нечетным субботам. Время консультаций определяется, исходя из расписания занятий ведущего дисциплину преподавателя.
Дата добавления: 2015-04-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав |