rpd000003940 (231300 (01.03.04).Б3 Математическое моделирование динамических систем), страница 2

Тематика: Теория графов

Трудоемкость(СРС): 27

Прикрепленные файлы:

Типовые варианты:

-Кратчайшие пути между всеми парами вершин графа.

-Эйлеровы и гамильтоновы пути (циклы).

-Нахождение компонент сильной связности графа;

-Перечисление путей ориентированного графа методом латинской композиции.

-Нахождение максимального пути в нагруженном графе.

-Нахождение наименьшего покрытия простого графа.

-Раскраска вершин графа.

-Пересчет прадеревьев ориентированного графа и их построение.

1. Рубежный контроль

1. Промежуточная аттестация

1. Экзамен за семестр 1

Прикрепленные файлы:

Вопросы для подготовки к экзамену/зачету:

1.Понятие множества. Основные принципы интуитивной теории множеств.

2.Операции над множествами. Основные тождества алгебры множеств.

3.Прямое произведение множеств. $$Отношения. Примеры. отношений. Отношение эквивалентности. Классы эквивалентности.

4.Разбиение множества. Теорема о связи между отношением эквивалентности и разбением на множестве. Фактор-множество.

5.Понятие функции. Инъюктивные, сюрьективные и биективные функции. Примеры. Характеристические функции. для множеств.

6.Композиция функций и ее свойства.

7.Обратные отношения. Обратные функции. Их свойства.

8.Понятие мощности множеств. Счетные множества. Примеры.

9.Доказательство равно мощности множеств [0,1] и (0,1).

10.Несчетные множества. Теорема Кантоа о несчетности множества [0,1].

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.Пути в графах. Алгоритм Тэрри.

37.Минимальный путь в ненагруженном графе.Алгоритм "фронта волны".

38.Минимальный путь в нагруженном графе. Алгоритм Форда

39.Траспортная сеть. Поток по транспортной сети. Срез транспортной сети. Полный поток.

40.Максимальный поток по транспортной сети. Увеличивающие цепи. Алгоритм Форда - Фалкерсона.

2. Экзамен за семестр 2

Прикрепленные файлы:

Вопросы для подготовки к экзамену/зачету:

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.Бином Ньютона. Свойства треугольника Паскаля. Полиномиальная формула.

37.Вывести формулы для нахождения числа сочетаний и размещений с повторениями и без.

38.Формула включений и исключений. Формула включений и исключений.

39.Количество целочисленных решений линейного уравнения.

40.Граф группы.

1. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

а)основная литература:

1. Осипова В.А. Основы дискретной математики. -М.: ФОРУМ ИНФРА-М, 2006

2. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 2006.

3. Лавров И. А. Математическая логика. -М.: Академия, 2006.

4. Новиков Ф.А. Дискретная математика для программистов: учебное пособие для вузов -М.: Питер, 2005.

5. Лавров И.А., Максимова А.Л.. Задачи по теории множеств, математической логики и теории алгоритмов. -М.: ФИЗМАТЛИТ, 2004

б)дополнительная литература:

1. В.Н.Нефедов, В.А.Осипова. Курс дискретной математики. -М.: МАИ, 1993.

2. А.Кофман. Введение в прикладную комбинаторику. -М.: Наука, 1975.519.К 744.

3. Методические указания к выполнению лабораторных работ по курсу "Дискретная математика". Под ред. Осиповой В.А. -М.: МАИ,1989.

в)программное обеспечение, Интернет-ресурсы, электронные библиотечные системы:

1. Лабораторный практикум "Дискретня матемаитка".

2. Обучающая программа "Машина Тьюринга".

3. Дискретная математика. – Электронный учебник. http://www.lvf2004.com/index.html/

1. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Дисплейный класс персональных компьютеров.

Лабораторный практикум по курсу «Дискретная математика».

Приложение 1
к рабочей программе дисциплины
«Теория графов и математическая логика »

Аннотация рабочей программы

Дисциплина Теория графов и математическая логика является частью Математического и естественно-научный цикл дисциплин подготовки студентов по направлению подготовки Прикладная математика. Дисциплина реализуется на 8 факультете «Московского авиационного института (национального исследовательского университета)» кафедрой (кафедрами) 805.

Дисциплина нацелена на формирование следующих компетенций: ПК-14.

Содержание дисциплины охватывает круг вопросов, связанных с: с описанием задач реального мира с использованием дискретных моделей, основанных на понятиях математической логики (высказывание, таблица истинности, формула и т.п.) и теории графов (вершина, ребро, дуга, матрица смежности и т.п.) .

Преподавание дисциплины предусматривает следующие формы организации учебного процесса: Лекция, мастер-класс, Практическое занятие, Лабораторная работа.

Программой дисциплины предусмотрены следующие виды контроля: промежуточная аттестация в форме Экзамен за семестр 1 ,Экзамен за семестр 2.

Общая трудоемкость освоения дисциплины составляет 10 зачетных единиц, 360 часов. Программой дисциплины предусмотрены лекционные (68 часов), практические (52 часов), лабораторные (16 часов) занятия и (170 часов) самостоятельной работы студента. Основными целями преподавания дисциплины «Теория графов и математическая логика» являются:

• овладение студентами той частью математической науки, главной спецификой которой является дискретность, т.е. антипод непрерывности, и включающий в себя такие разделы математики как алгебру, математическую логику, теорию графов, комбинаторику;

• ознакомление студентов с прикладными возможностями методов дискретной математики, связанными с развитием многих новых отраслей техники, средств передачи, хранения и переработки информации, с применением этих методов математической кибернетики в теории управляющих систем;

• привитие студентам современной математической культуры,

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

Основными задачами преподавания дисциплины "Дискретная математика" являются:

• научить студентов использовать методы следующих разделов математики:

- алгебры множеств;

- логики высказываний;

- логики предикатов;

- теории алгоритмов;

- общей алгебры;

- комбинаторики;

- теории графов;

• применять эти методы к формированию математической модели задач дискретного характера к решению прикладных задач;

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

Приложение 2
к рабочей программе дисциплины
«Теория графов и математическая логика »

Cодержание учебных занятий

1. Лекции

1.1.1. Основные понятия алгебры множеств.(АЗ: 2, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие множеств. Основные принципы интуитивной теории множеств. Парадокс Рассела. Основные операции над множествами. Диаграмма Венна. Основные тождества алгебры множеств.

1.2.1. Отношения на множестве(АЗ: 6, СРС: 4)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Прямое произведение множеств. Бинарное отношение. Операции с бинарными отношениями. n-арное отношение. Отношение эквивалентности. Разбиение множества. Связь между отношением эквивалентности на множестве и разбиением множества.

Фактор множества.

Отношение порядка. Частный и линейный порядок. Изоформизм частично упорядоченных множеств.

Функции. Инъективные, сюръективные и биективные функции. Композиция и обращение функций. Мощность множества. Счетные множества. Несчетность континуума

1.3.1. Элементы логики высказываний(АЗ: 6, СРС: 6)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Высказывания. Логические операции. Таблицы истинности. Язык логики высказываний. Формулы логики высказываний.

Выполнимость формул логики высказываний.

Равносильность формул. Основные равносильности.

Дизъюнктивная и конъюнктивная нормальная форма. Совершенные нормальные формы. Проблема разрешимости для логики высказываний.

Соответствующие булевы функции.

Теорема о представлении булевой функции формулой логики высказываний.

Минимизация в классе д.н.ф.