Программа дисциплины дискретная математика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника

Скачать 224,91 Kb.

Название	Программа дисциплины дискретная математика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника
Дата публикации	31.07.2013
Размер	224,91 Kb.
Тип	Программа дисциплины

pochit.ru > Информатика > Программа дисциплины

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

"УТВЕРЖДАЮ"

Проректор

__________ В.С.Бухмин

ПРОГРАММА ДИСЦИПЛИНЫ

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

Цикл ЕН.Ф.

Специальность: 013800 – Радиофизика и электроника

Специализация: 013817 – Компьютерные информационные системы и защита информации

Принята на заседании кафедры Теории относительности и гравитации

(протокол № 6 от "5" июня 2009 г.)

Заведующий кафедрой
________________ (А.В. Аминова)

Утверждена Учебно-методической комиссией физического факультета КГУ.

(протокол №___ от "__"__________200__ г.)
Председатель комиссии
____________________ (Д.А. Таюрский)

Рабочая программа дисциплины "Дискретная математика" предназначена для студентов 2,3 курса

по специальности: 013800 – Радиофизика и электроника

Специализация: 013817 – Компьютерные информационные системы и защита информации
АВТОР: Иваньшин П.Н.
^ КРАТКАЯ АННОТАЦИЯ: Курс лекций «Дискретная математика» состоит из разделов: Теория графов и Теория формальных языков и автоматов
1. Требования к уровню подготовки студента, завершившего изучение дисциплины "Дискретная математика".

Студенты, завершившие изучение данной дисциплины должны:

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

2. Объем дисциплины и виды учебной работы (в часах)

Форма обучения очная

Количество семестров 2

Форма контроля: ^ 4 семестр зачет

5 семестр экзамен

№ п/п	Виды учебных занятий	Количество часов
		4 семестр	5 семестр
1.	Всего часов по дисциплине	131	69
2.	Самостоятельная работа	63	33
3.	Аудиторных занятий	68	36
	в том числе: лекций	34	18
	семинарских (или лабораторно-практических) занятий	34	18

3. Содержание дисциплины.

^ ТРЕБОВАНИЯ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ СОДЕРЖАНИЯ ПРОГРАММЫ

Индекс	Наименование дисциплины и ее основные разделы	Всего часов
ЕН.Ф.12	Дискретная математика. Теория графов: Графы и орграфы; изоморфизмы; деревья; Эйлеровы графы; Планарные графы; покрытия и независимые множества; сильная связность в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла в графе; задача о коммивояжере. Теория формальных языков и автоматов: Конечные автоматы; автоматные базисы и проблема полноты; эквивалентноть в автоматах; автоматные языки; понятие формальной грамматики; применение грамматик для построения языков высокого уровня; тестирование автоматов; вероятностные автоматы.	200

Примечание: Если дисциплина, устанавливается вузом самостоятельно, то в данной таблице ставится прочерк.

^ СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ

№ п/п	Название темы	Всего час.	Ауд. лекц.	Практ.
	Семестр 4
1.	Понятие графа. Орграф, мультиграф. Лемма о рукопожатиях. Операции над графами. Изоморфизмы графов.	4	2	2
2.	Связность графов. Цепи, маршруты, циклы. Связность, реберная связность. Компоненты графа. Сильная связность в орграфах.	4	2	2
3.	Расстояние в графах. Понятия: радиус, диаметр, обхват, окружение и их свойства. Задача коммивояжера.	4	2	2
4.	Деревья и леса. Эквивалентные определения дерева. Классификация деревьев. Существование остовного дерева.	4	2	2
5.	Обходы графов. Гамильтоновы и Эйлеровы графы. Теоремы Дирака, Оре и Эйлера. Алгоритм Флери.	4	2	2
6.	Линейная алгебра на графах. Матрицы инцидентности и смежности. Пространства циклов и разрезов графов. Индуцированные циклы и минимальные разрезы.	4	2	2
7.	Реализация графов. Реализация графов в R^3. Планарные графы. Формула Эйлера и ее следствия. Плоско-двойственные графы. Теорема Куратовского.	8	4	4
8.	Раскрашивание графов Теоремы о 5-и и 4-х красках. Раскрашивание вершин, ребер и граней. Оценки раскрашиваемости.	4	2	2
9.	Хроматическое число и хроматический полином.	4	2	2
10.	Алгоритмы поиска кратчайших путей в графах. Алгоритмы Дийкстры и Флойда-Уоршолла.	4	2	2
11.	Минимальные остовные деревья. Алгоритмы Прима и Крускала.	4	2	2
12.	Потоки в сетях. Понятие потока. Максимальный поток. Теорема о максимальном потоке и минимальном разрезе.	4	2	2
13.	Накрытия. Вершинные и реберные накрытия. Независимые семейства вершин и ребер.	8	4	4
14.	Анализ графа цепи Маркова. Неприводимость цепи Маркова и сильная связность орграфа. Рекуррентные состояния. Алгоритм поиска в глубину.	4	2	2
15.	Период состояния цепи Маркова. Алгоритм поиска в ширину. Стационарные состояния.	4	2	2
	Итого в 4-м семестре	68	34	34
	Семестр 5
16.	Основные понятия теории автоматов. Алфавиты, слова, языки. Операции над словами и языками. Определение абстрактного автомата. Способы задания автоматов.	4	2	2
17.	Конечные автоматы. Операции над конечными автоматами.	4	2	2
18.	Эквивалентные автоматы. Теорема Мура. Автоматы Мили и Мура. Частично-определенные автоматы. Минимизация конечных автоматов.	4	2	2
19.	Понятие частично-определенного автомата. Совместимость состояний. Классы совместимости. Алгоритм Ангера-Пола минимизации автоматов.	4	2	2
20	Алгебраическая теория конечных автоматов. Кодирование внутренних состояний. Последовательная и параллельная декомпозиции.	4	2	2
21.	Регулярные выражения. Операторы регулярных выражений. выражения и шаблоны. Языки регулярных выражений и шаблонов. Построение регулярных выражений по шаблонам.	4	2	2
22.	Построение регулярного выражения по ДКА. Алгоритм преобразования регулярных выражений в ДКА. Теорема Клини. Лексический анализ. Применение регулярных выражений для решения задач лексического анализа. Алгебра Клини регулярных выражений. Теорема Клини	4	2	2
23.	Формальные грамматики. Деревья вывода. Регулярные и нерегулярные языки и грамматики.	4	2	2
24.	Регулярные языки. Свойства замкнутости регулярных языков. Замкнутость относительно булевых операций. Обращение. Гомоморфизмы.	4	2	2
25.	Проверка пустоты регулярных языков и алгоритмы ее решения . Проблема принадлежности слова регулярному языку и алгоритмы ее решения. Лемма накачки. Применение леммы накачки для доказательства нерегулярности языков.	6	3	3
26.	Контекстно-свободные грамматики и языки. Определение контекстно-свободных грамматик. Контекстно-свободный грамматический вывод. Примеры кс-языков.	4	2	2
27.	Деревья разбора. Взаимосвязь грамматических выводов и деревьев разбора. Неоднозначность в кс-языках и грамматиках. Исключение неоднозначности из кс-грамматик.	4	2	2
28.	Автоматы с магазинной памятью. Определение автомата с магазинной памятью (МПА). Вычисления МПА. Языки МПА. Допустимость по заключительному состоянию и по пустому магазину.	4	2	2
29.	Эквивалентность двух определений допустимости МПА. Преобразование кс-грамматики в МПА. Построение кс-грамматики по МПА. Детерминированные МПА (ДМПА). Соотношение между регулярными языками, кс-языками и языками ДМПА.	4	2	2
30.	Свойства контекстно-свободных грамматик. Нормальные формы кс-грамматик. Приведение кс-грамматик к нормальной форме Хомского. Лемма накачки для кс-языков. Примеры языков, не являющихся контекстно-свободными. Замкнутость кс-языков относительно подстановки, объединения, пересечения, гомоморфизма. Замкнутость кс-языков относительно пересечения с регулярными языками.	4	2	2
31.	Алгоритм проверки пустоты кс-языков. Алгоритм Кока-Янгера-Касами проверки принадлежности слова кс-языку. Синтаксические анализаторы. Генераторы синтаксических анализаторов.	4	2	2
32.	Вероятностные автоматы (ва). Определение вероятностного автомата. Типы вероятностных автоматов. Пердставимость языка в виде ва.	4	2	2
	Итого в 5 семестре	72	36	36
	Итого за 4 и 5 семестры	140	70	70

^ ОСНОВНАЯ ЛИТЕРАТУРА.

Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К.
Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.Кристофидес Н.
Оре О. Теория графов. ― 2-е изд.. ― М.: Наука, 1980. ― С. 336.
Ю.Карпов. Теория автоматов. ― Спб.:Питер, 2003.
Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.
Харари Ф. Теория графовХарари Ф. Теория графов. ― М.: Теория графовХарари Ф. Теория графовМирТеория графовХарари Ф. Теория графов, 1973.Теория графовХарари Ф. Теория графовХарари Ф.
Diestel R. Graph Theory, Electronic EditionDiestel R. Graph Theory, Electronic Edition. ― NY: Springer-Verlag, 2005. ― С. 422С.Graph Theory, Electronic EditionDiestel R. Graph Theory, Electronic EditionDiestel R.
Поспелов Д.А. Вероятностные автоматы (1970).
J. A. Anderson. Automata Theory with Modern Applications, Cambridge University Press, 2006.

Вопросы к экзамену

1) Понятие графа. Орграф, мультиграф. Лемма о

рукопожатиях.

2) Вероятностные автоматы (ва). Определение вероятностного автомата. Типы вероятностных автоматов. Пердставимость языка в виде ва.

1) Операции над графами. Изоморфизмы графов.

2) Алгоритм проверки пустоты кс-языков. Алгоритм Кока-Янгера-Касами проверки принадлежности слова кс-языку. Синтаксические анализаторы. Генераторы синтаксических анализаторов.

1) Связность графов. Цепи, маршруты, циклы. Связность, реберная связность. Компоненты графа. Сильная связность в орграфах.

2) Лемма накачки для кс-языков. Примеры языков, не являющихся контекстно-свободными. Замкнутость кс-языков относительно подстановки, объединения, пересечения, гомоморфизма. Замкнутость кс-языков относительно пересечения с регулярными языками.

1) Расстояние в графах. Понятия: радиус, диаметр, обхват, окружение и их свойства. Задача коммивояжера.

2) Эквивалентность двух определений допустимости МПА. Преобразование кс-грамматики в МПА. Построение кс-грамматики по МПА.

1) Деревья и леса. Эквивалентные определения дерева.

2) Нормальные формы кс-грамматик. Приведение кс-грамматик к нормальной форме Хомского.

1) Классификация деревьев. Существование остовного дерева.

2) Детерминированные МПА (ДМПА). Соотношение между регулярными языками, кс-языками и языками ДМПА. Свойства контекстно-свободных грамматик.

1) Обходы графов. Гамильтоновы и Эйлеровы графы.

2) Автоматы с магазинной памятью. Определение автомата с магазинной памятью (МПА). Вычисления МПА. Языки МПА. Допустимость по заключительному состоянию и по пустому магазину.

1) Теоремы Дирака, Оре и Эйлера.

2) Неоднозначность в кс-языках и грамматиках. Исключение неоднозначности из кс-грамматик.

1) Алгоритм Флери.

2)Деревья разбора. Взаимосвязь грамматических выводов и деревьев разбора.

1) Линейная алгебра на графах. Матрицы инцидентности и смежности.

2) Контекстно-свободные грамматики и языки. Определение контекстно-свободных грамматик.

1) Пространства циклов и разрезов графов. Индуцированные циклы и минимальные разрезы.

2) Контекстно-свободный грамматический вывод. Примеры кс-языков.

1) Реализация графов. Реализация графов в R^3.

2) Лемма накачки. Применение леммы накачки для доказательства нерегулярности языков.

1) Планарные графы. Формула Эйлера и ее следствия.

2) Проверка пустоты регулярных языков и алгоритмы ее решения. Проблема принадлежности слова регулярному языку и алгоритмы ее решения.

1) Плоско-двойственные графы. Теорема Куратовского.

2) Свойства замкнутости регулярных языков. Замкнутость относительно булевых операций. Обращение. Гомоморфизмы.

1) Раскрашивание графов. Теоремы о 5-и и 4-х красках.

2) Деревья вывода. Регулярные и нерегулярные языки и грамматики. Регулярные языки.

1) Раскрашивание вершин, ребер и граней. Оценки раскрашиваемости.

2) Лексический анализ. Применение регулярных выражений для решения задач лексического анализа. Алгебра Клини регулярных выражений. Теорема Клини

1) Хроматическое число и хроматический полином.

2) Построение регулярного выражения по ДКА. Алгоритм преобразования регулярных выражений в ДКА.

1) Алгоритмы поиска кратчайших путей в графах. Алгоритмы Дийкстры и Флойда-Уоршолла.

2) Операторы регулярных выражений. выражения и шаблоны. Языки регулярных выражений и шаблонов. Построение регулярных выражений по шаблонам.

1) Минимальные остовные деревья. Алгоритмы Прима и Крускала.

2) Кодирование внутренних состояний. Последовательная и параллельная декомпозиции.

1) Потоки в сетях. Понятие потока. Максимальный поток. Теорема о максимальном потоке и минимальном разрезе.

2) Совместимость состояний. Классы совместимости. Алгоритм Ангера-Пола минимизации автоматов.

1) Накрытия. Вершинные и реберные накрытия. Независимые семейства вершин и ребер.

2) Минимизация конечных автоматов. Понятие частично-определенного автомата.

1) Анализ графа цепи Маркова. Неприводимость цепи Маркова и сильная связность орграфа. Рекуррентные состояния. Алгоритм поиска в глубину.

2) Эквивалентные автоматы. Теорема Мура. Автоматы Мили и Мура. Частично-определенные автоматы.

1) Период состояния цепи Маркова. Алгоритм поиска в ширину. Стационарные состояния.

2) Конечные автоматы. Операции над конечными автоматами.

	Программа дисциплины функциональный анализ Цикл ен. В специальность:... Рабочая программа дисциплины "Функциональный анализ" предназначена для студентов 2 курса		Программа дисциплины дифференциальные уравнения Цикл ен. В. Специальность:... Рабочая программа дисциплины «Дифференциальные уравнения» предназначена для студентов 2 курса
	Программа дисциплины алгебра Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника Требования к уровню подготовки студента, завершившего изучение дисциплины "Алгебра"		Программа дисциплины интегральные уравнения и вариационное исчисление... Рабочая программа дисциплины «Интегральные уравнения и вариационное исчисление» предназначена для студентов 2 курса
	Программа дисциплины дифференциальные уравнения Цикл ен специальность... Рабочая программа дисциплины "Дифференциальные уравнения" предназначена для студентов 3 курса		Программа дисциплины векторный и тензорный анализ Цикл ен. В. Специальность... Рабочая программа дисциплины "Векторный и тензорный анализ" предназначена для студентов 2 курса
	Программа дисциплины методы математической физики Цикл опд. Ф специальность:... Рабочая программа дисциплины "Методы математической физики" предназначена для студентов 3 курса		Программа дисциплины теория вероятностей и математическая статистика... Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 1 курса
	Программа дисциплины теория вероятностей и математическая статистика... Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 2 курса		Программа дисциплины теория вероятностей и математическая статистика... Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 3 курса

Программа дисциплины дискретная математика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника

Похожие: