rpd000003403 (210601 (11.05.01).С6 Лазерные информационные системы и комплексы), страница 2
Описание файла
Файл "rpd000003403" внутри архива находится в следующих папках: 210601 (11.05.01).С6 Лазерные информационные системы и комплексы, 210601.С6. Документ из архива "210601 (11.05.01).С6 Лазерные информационные системы и комплексы", который расположен в категории "". Всё это находится в предмете "вспомогательные материалы для первокурсников" из 1 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "вспомогательные материалы для первокурсников" в общих файлах.
Онлайн просмотр документа "rpd000003403"
Текст 2 страницы из документа "rpd000003403"
8. Комбинаторные схемы
- 8.1. Сочетаия и размещения
- 8.2. Формула включений и исключений
- 8.3. Алгоритмическая сложность алгоритмов
-
Лекции
№ п/п | Раздел дисциплины | Объем, часов | Тема лекции | Дидакт. единицы |
1 | 1.1.Основные понятия алгебры множеств | 2 | Основные понятия алгебры множеств. | 1.1 |
2 | 1.2.Отношения на множествах | 2 | Отношения на множестве | 2.1, 2.2 |
3 | 1.3.Логика высказываний и исчисление высказываний | 2 | Основные понятия логики высказываний | 3.1 |
4 | 1.3.Логика высказываний и исчисление высказываний | 2 | Нормальные и совершенные формы. МИнимизация в классе ДНФ | 3.1 |
5 | 1.3.Логика высказываний и исчисление высказываний | 2 | Исчисление высказываний | 3.3 |
6 | 1.4.Логика и исчисление предикатов | 4 | Логика и исчисление предикатов. | 4.1, 4.2, 3.3 |
7 | 1.5.Теория графов | 2 | Основные понятия теории графов.. Пути в графе. | 6.1, 6.2 |
8 | 1.5.Теория графов | 2 | Транспортные сети. | 6.4 |
9 | 1.5.Теория графов | 2 | Деревья и циклы | 6.3 |
10 | 1.5.Теория графов | 2 | Внутренние и внешние устойчивые подмножества. Ядро. | 6.6 |
11 | 1.6.Элементы теории алгоритмов | 2 | Элементы теории алгоритмов | 5.1, 5.2 |
12 | 1.7.Алгебраические структуры | 4 | Теория групп | 7.1 |
13 | 1.7.Алгебраические структуры | 2 | Кольца и поля | 7.3 |
14 | 1.7.Алгебраические структуры | 2 | Элементы теории кодирования | 7.2 |
15 | 1.8.Комбинаторные схемы | 2 | Комбинаторные схемы | 8.1, 8.2 |
Итого: | 34 |
-
Практические занятия
№ п/п | Раздел дисциплины | Объем, часов | Тема практического занятия | Дидакт. единицы |
1 | 1.1.Основные понятия алгебры множеств | 2 | Основные понятия алгебры множеств. | 1.1 |
2 | 1.2.Отношения на множествах | 2 | Прямое произведение множеств. Бинарные отношения | 2.1 |
3 | 1.2.Отношения на множествах | 2 | Отношения порядка и эквивалентности. | 2.1 |
4 | 1.3.Логика высказываний и исчисление высказываний | 2 | Основные понятия логики высказываний | 3.1 |
5 | 1.3.Логика высказываний и исчисление высказываний | 2 | СДНФ, СКНФ | 3.1 |
6 | 1.4.Логика и исчисление предикатов | 2 | Логика предикатов | 4.1 |
7 | 1.5.Теория графов | 2 | Матричное задание графа | 6.1 |
8 | 1.8.Комбинаторные схемы | 2 | Комбинаторные схемы | 8.1, 8.3, 8.3 |
Итого: | 16 |
-
Лабораторные работы
№ п/п | Раздел дисциплины | Наименование лабораторной работы | Наименование лаборатории | Объем, часов | Дидакт. единицы |
Итого: |
-
Типовые задания
№ п/п | Раздел дисциплины | Объем, часов | Наименование типового задания |
1 | Основные понятия алгебры множеств | 1 | Доказательство тождеств алгебры множеств |
2 | Отношения на множествах | 1 | Проверка свойств бинарных отношений, нахождение области определения и значений |
3 | Логика высказываний и исчисление высказываний | 2 | СДНФ, СКНФ |
4 | Логика и исчисление предикатов | 1 | Привести равносильными преобразованиями к приведенной нормальной форме данную формулу логики предикатов. |
5 | Логика и исчисление предикатов | 2 | Проверить правильность рассуждения в логике предикатов. |
6 | Теория графов | 1 | Определить для орграфа, заданного матрицей смежности: имеются ли контуры; матрицу односторонней связности; матрицу сильной связности. |
7 | Теория графов | 1 | Используя алгоритм Терри, определить замкнутый маршрут, проходящий ровно по два раза (по одному в каждом направлении) через каждое ребро графа. |
8 | Теория графов | 2 | Используя алгоритм “фронта волны”, найти все минимальные пути из первой вершины в последнюю орграфа, заданного матрицей смежности. |
9 | Теория графов | 2 | Используя алгоритм Форда, найти минимальные пути из первой вершины во все достижимые вершины в нагруженном графе, заданном матрицей длин дуг. |
10 | Теория графов | 2 | Построить максимальный поток по транспортной сети. |
11 | Теория графов | 2 | Для заданной графом электрической цепи составить системы уравнений Кирхгофа для токов и напряжений |
12 | Теория графов | 1 | Найти минимальное остовное дерево графа |
13 | Элементы теории алгоритмов | 2 | Машина Тьюринга |
14 | Алгебраические структуры | 2 | Проверить является ли множество групопй |
Итого: | 22 |
-
Курсовые работы и проекты по дисциплине
-
Рубежный контроль
-
Промежуточная аттестация
1. Экзамен за семестр 4
Прикрепленные файлы:
Вопросы для подготовки к экзамену/зачету:
1.Понятие множества. Основные определения. Операции над множествами.
2.Основные тождества алгебры множеств.
3.Прямое произведение, примеры. Доказательство тождеств, содержащих прямое произведение.
4.Отношение эквивалентности и разбиение множеств. Классы эквивалентности. Примеры
5.Теорема о связи между разбиением и отношением эквивалентности.
6.Обратные отношения. Композиция отношений. Примеры.
7.Функция. Инъективная, сюръективная и биективная функция. Примеры.
8.Отношение частичного и линейного порядка. Примеры.
9.Диаграмма Хассе. Наибольший, наименьший минимальный, максимальный элемент. Примеры.
10.Высказывания. Логические операции. Формулы логики высказываний. Примеры.
11.Основные тождества логики высказываний.
12.Алгоритм приведения формул логики высказываний к СДНФ и СКНФ.
13.Тождественно-истинные формулы. Правильные рассуждения. Косвенные методы доказательства.
14.Булевы функции. Теорема о представлении булевой функции формулой логики высказываний.
15.Минимальная ДНФ. Алгоритм нахождения. Пример.
16.Преобразование переключатетельных схем на основе преоразования функции проводимости. Пример.
17.Полные системы булевых функций. Многочлен Жегалкина.
18.Основные понятия логики предикатов: предикат, квантор, формула, интерпретация
19.Основные равносильности логики предикатов.
20.Основные равносильности логики предикатов.
21.Выполняемость и общезначимость формул логики предикатов. Проблема разрешимости в логике высказываний и в логики предикатов.
22.Примитивно-рекурсивные и частично-рекурсивные функции. Примеры
23.Полугруппы. Моноиды. Группы. Примеры.
24.Циклические группы и подгруппы, теорема о подгруппе циклической группы. Примеры.
25.Симметрические группы. Теорема о разложении подстановок в произведение независимых циклов.
26.Кольца и поля. Примеры
27.Графы. Основные понятия. Матричное задание графа.
28.Алгоритм Тэрри поиска пути в графе. Примеры
29.Алгоритм поиска кратчайшего пути в орграфе. Примеры.
30.Алгоритм нахождения минимального пути в нагруженнои орграфе.
31.Внутренне и внешне устойчивые подмножества в графе. Ядро графа. Разбиение графа на уровни.
32.Четыре определения дерева. Их эквивалентность.
33.Понятие остовного дерева. Алгоритм нахождения остовного дерева наименьшей длины.
34.Понятие базиса циклов. Алгоритм нахождение базиса циклов. Вектор-циклы. Цикломатическая матрица.
35.Составление уравнений Кирхгофа для токов и напряжений по графу электрической цепи.
36.Транспортные сети. Нахождение полного и максимального потока в транспортной сети.