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


Скачать 224.91 Kb.
НазваниеПрограмма дисциплины дискретная математика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника
Иваньшин П Н
Дата26.10.2012
Размер224.91 Kb.
ТипПрограмма дисциплины

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


"УТВЕРЖДАЮ"

Проректор

__________ В.С.Бухмин


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


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


Цикл ЕН.Ф.


Специальность: 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


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


  1. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.

  2. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.Берж К.

  3. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.Кристофидес Н.

  4. Оре О. Теория графов. ― 2-е изд.. ― М.: Наука, 1980. ― С. 336.

  5. Ю.Карпов. Теория автоматов. ― Спб.:Питер, 2003.

  6. Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.

  7. Харари Ф. Теория графовХарари Ф. Теория графов. ― М.: Теория графовХарари Ф. Теория графовМирТеория графовХарари Ф. Теория графов, 1973.Теория графовХарари Ф. Теория графовХарари Ф.

  8. 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.

  9. Поспелов Д.А. Вероятностные автоматы (1970).

  10. J. A. Anderson. Automata Theory with Modern Applications, Cambridge University Press, 2006.


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


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

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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница