Пензенский государственный университет институт информатики и вычислительной техники Кафедра "Дискретная математика" Дискретная математика




Скачать 132.09 Kb.
НазваниеПензенский государственный университет институт информатики и вычислительной техники Кафедра "Дискретная математика" Дискретная математика
Дата13.02.2013
Размер132.09 Kb.
ТипГосударственный образовательный стандарт


РПД ДМ / ИБСТ ________ 2006


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


Институт информатики и вычислительной техники

Кафедра "Дискретная математика"


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


Рабочая программа учебной дисциплины


по подготовке специалиста

по направлению 090000 "Защита информации",

специальности 090105 "Комплексное обеспечение информационной

безопасности автоматизированных систем"


1 РАЗРАБОТАНА

На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ.


Автор к.т.н., доцент Л.Н. Бондаренко

"____" ____________ 2006 г.

2 РЕЦЕНЗЕНТ


"____" ____________ 2006 г.

3 СОГЛАСОВАНА

Заведующий кафедрой "ИБСТ"

к.т.н., доцент В.М. Алексеев

"____" ____________ 2006 г.

4 УТВЕРЖДЕНА на заседании кафедры "Дискретная математика"

Заведующий кафедрой

д. ф.-м. н., профессор М.А. Алехина

"____" ____________ 2006 г.

5 УТВЕРЖДЕНА на заседании выпускающей кафедры "ИБСТ"

Заведующий кафедрой

к.т.н., доцент В.М. Алексеев

"____" ____________ 2006 г.


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

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

Рабочая программа дисциплины

1 Область применения

Настоящая рабочая программа устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности по дисциплине "Дискретная математика".

Предназначена для преподавателей, ведущих дисциплину, и студентов специальности 090105 "Комплексное обеспечение безопасности автоматизированных систем" направления 090000 "Защита информации", изучающих дисциплину.

2 Нормативные ссылки

Государственный образовательный стандарт высшего профессионального образования. Направление подготовки дипломированного специалиста 090000 "Защита информации" (позиция ЕН.Ф.07).

Учебный план ПГУ по направлению 090000 "Защита информации" специальности 090105, утвержденный в 2006 г.

Семестровый учебный план на текущий учебный год.

И151.30.03-2000 Рабочие программы учебных дисциплин. Порядок разработки и требования к содержанию.

3 Нормативная трудоемкость изучения дисциплины

Трудоемкость дисциплины в часах, исходя из 17-недельного семестра:

Общая

187

III семестр

68/4

IV семестр

119/7

Обязательная аудиторная

Лекции

Практические занятия

68

17/1

17/1



51/3

34/2

17/1

Самостоятельная работа студента

Аудиторная

Внеаудиторная

в т.ч. курсовая работа (проект)

119

51/3



51/3



68/4



68/4



Контроль

текущий на занятиях

защита курсовой работы (проекта)

зачет

экзамен





III семестр



III семестр




IV семестр





IV семестр

4 Цель и задачи дисциплины

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

    1. В результате изучения дисциплины студент должен

Знать:

основные положения теории графов;

основы теории конечных автоматов и формальных языков;

уметь:

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

5 Место дисциплины в учебном процессе

Дисциплина относится к циклу математических и общих естественнонаучных дисциплин. Изучение данной дисциплины базируется на курсах "Алгебра и геометрия", "Математический анализ", "Информатика". Основные ее положения используются при изучении дисциплин: "Криптографические методы и средства", "теория принятия решений", "Теория информации".

Дисциплина изучается в III и IV семестрах.

6 Сводные данные об основных разделах дисциплины

III Семестр

Наименование раздела

Количество часов занятий

Уровни изучения




аудиторных

лекционных

самостоятельных




Графы и орграфы.

2

6




Изоморфизмы. Деревья.

2

6




Эйлеровы графы. Планарные графы.

2

6




Покрытия и независимые множества.

2

6




Сильная связность в орграфах.

2

6




Анализ графа цепи Маркова.

2

6




Алгоритмы поиска кратчайших путей в графах.

3

8




Задача поиска гамильтонова цикла в графах. Задача о коммивояжере.

2

7




Сумма:

17

51




IV семестр

Наименование раздела

Количество часов занятий

Уровни изучения




аудиторных

самостоятельных







лекционных

практических







Конечные автоматы.

4

3

8




Автоматные базисы и проблема полноты.

4



8




Эквивалентность в автоматах.

4

3

8




Автоматные языки.

4

3

8




Понятие формальной грамматики.

4

2

8




Применение грамматик для построения языков высокого уровня.

4

2

10




Тестирование автоматов.

4

2

8




Вероятностные автоматы.

8

2

10




Сумма:

34

17

68





7. Лекции

7.1 Разделы и их содержание

III семестр

7.1.1 Графы и орграфы

Основные понятия теории графов. Подграфы. Матрицы смежности и инцидентности, их основные свойства.

7.1.2 Изоморфизмы. Деревья.

Изоморфизм графов и подграфов. Остовные подграфы, компоненты, связность. Операции над графами. Деревья. Матричная теорема о деревьях, подсчет числа остовов. Подсчет кубических деревьев специального вида.

7.1.3 Эйлеровы графы. Планарные графы.

Маршруты, цепи, циклы. Эйлеровы и гамильтоновы цепи и циклы. Теоремы о существовании эйлеровых и гамильтоновых циклов. Цикломатическое число, его свойства. Планарность. Теорема Понтрягина – Куратовского. Теорема о четырех красках.

7.1.4 Покрытия и независимые множества. Сильная связность в орграфах. Анализ графа цепи Маркова.

Вершинные и реберные покрытия, числа внутренней и внешней устойчивости, паросочетания. Теоремы Кенига, Холла, Фробениуса. Задачи о подсчете совершенных паросочетаний. Анализ графа цепи Маркова.

7.1.5 Алгоритмы поиска кратчайших путей в графах.

Задачи о кратчайшем пути. Алгоритмы поиска кратчайших путей в графах. Теорема Менгера. Потоки и разрезы.

7.1.6 Задача поиска гамильтонова цикла в графах. Задача о коммивояжере.

Задача поиска гамильтонова цикла в графах. Гамильтоновы циклы и 2-паросочетания. Задача китайского почтальона. Задача о коммивояжере.

IV семестр

7.1.7 Конечные автоматы

Конечные автоматы Мили и Мура. Канонические уравнения. Представление конечных автоматов каноническими таблицами и оргграфами. Представление автомата Мура булевыми матрицами. Преобразование автомата Мили в автомат Мура и обратно.

7.1.8 Автоматные базисы и проблема полноты

Простейшие автоматные базисы. Задача реализации. Автоматные базисы и проблема полноты

7.1.9 Эквивалентность в автоматах.

Эквивалентность состояний автомата Мили. Построение сокращенного автомата Мили. Синтез автоматов с использованием информативного дерева. Минимизация автоматов с использованием канонических таблиц.

7.1.10 Автоматные языки

Основные понятия формальных языков. Регулярные языки и выражения.

7.1.11 Понятие формальной грамматики

КС-грамматики. Формальные грамматики. Иерархия Хомского. Языки типов 0 и 1. Иерархия Хомского. Языки типов 2 и 3.

7.1.12 Применение грамматик для построения языков высокого уровня

Представимость языков. Теорема Клини. Конечные автоматы и регулярные выражения. Использование регулярных выражений для анализа и синтеза автоматов. Применение грамматик для построения языков высокого уровня.

7.1.13 Тестирование автоматов

Последовательное соединение двух автоматов. Последовательное соединение с выходной функцией. Соединение автоматов с обратной связью. Компонентный автомат сети. Сеть автоматов. Тестирование автоматов.

7.1.14 Вероятностные автоматы

Определение вероятностного автомата. Способы задания вероятностного автомата. Инициальная эквивалентность вероятностных автоматов.

  1. Форма проведения занятий

Лекции.

  1. Материально-техническое обеспечение

Учебная литература, монографии, методические указания.

8 Практические занятия

8.1 Основные темы

8.1.1. Конечные автоматы Мили и Мура.

8.1.2 Преобразования конечных автоматов.

8.1.3 Эквивалентность в автоматах. Структурный анализ.

8.1.4 Эквивалентность в автоматах. Структурный синтез.

8.1.5 Регулярные выражения.

8.1.6 Использование регулярных выражений для анализа и синтеза.

8.1.7 Реализация конечных автоматов в простейших базисах.

8.1.8 Вероятностные автоматы.

8.2 Форма проведения занятий

Практические занятия.

8.3 Материально-техническое обеспечение

Учебная литература, монографии, методические указания.

9 Лабораторные занятия

Не запланированы.

10 Семинарские занятия

Не запланированы.

11 Другие виды аудиторных занятий

Не запланированы.

12 Курсовой проект (курсовая работа)

Не запланированы.

13 Другие виды самостоятельной работы

Внеаудиторная подготовка к лекциям и лабораторным работам.

14 Рекомендуемая литература

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

14.1 Новиков Ф. А. Дискретная математика для программистов. – СПБ.: Питер, 2001 (2 экз.), 2002 (10 экз.), 2005 (23 экз.). – 304 с.

14.2 Яблонский С. В. Введение в дискретную математику. – М.: Высшая школа, 2001 (20 экз.). – 384 с.

14.3 Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. – М.: Физматлит, 2005 (20 экз.). – 416 с.

Дополнительная литература

14.4 Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998 (5 экз.). – 703 с.

14.5 Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980 (1 экз.). – 478 с.

14.6 Оре О. Теория графов. – М.: Наука, 1968 (17 экз.), 1980 (2 экз.). – 352 с.

14.7 Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962. – 320 с.

14.8 Татт У. Теория графов. – М.: Мир, 1988. – 424 с.

14.9 Ловас Л., Пламмер М. Прикладные задачи теории графов. – М.: Мир, 1998. – 654 с.

14.10 Трахтенброт Б. А., Барздинь А. М. Конечные автоматы (поведение и синтез). – М.: Наука, 1970. (8 экз.). – 400 с.

14.11 Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. – М.: ГИФМЛ, 1962. (3 экз.). – 404 с.

14.12 Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. (3 экз.). – 392 с.

14.13 Логический подход к искусственному интеллекту: от классической логики к логическому программированию. – М.: Мир, 1990. – 432 с.

14.14 Кузнецов О. П. Дискретная математика для инженеров. – СПб.: Издательство Лань, 2004. – 400 с.

14.15 Белоусов А. И., Ткачев С. Б. Дискретная математика. – М.: Изд-во МГТУ им Н.Э. Баумана, 2001. –744 с.

14.16 Бухараев Р. Г. Основы теории вероятностных автоматов. – М.: Наука, 1985. (3 экз.). – 288 с.

15 Методические материалы

15.1 Волченская Т. В., Хмелевской Б. Г. Основы дискретной математики. Учеб. пособие. – Пенза: Пенз. политехн. ин-т, 1991 (3 экз.). – 88 с.

16 Сведения о переутверждении программы

на очередной учебный год и регистрация изменений

Учебный

год

Учебная

группа

Решение

кафедры

(№ протокола, дата,

подпись зав. кафедрой)

Решение

выпускающей

кафедры

(№ протокола, дата, подпись зав. кафедрой)

Лектор

(разработчик программы)

Номер

изменения





























































































Похожие:

Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconПензенский государственный университет институт информатики и вычислительной техники Кафедра "Дискретная математика" Дискретная математика
На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconПензенский государственный университет факультет вычислительной техники Кафедра "Дискретная математика" Дискретная математика
На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconАннотация рабочей программы «Дискретная математика»
Дискретная математика принадлежит Базовой части Профессионального цикла дисциплин ( Б. 1) подготовки студентов направления 010400...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconРабочая программа по дисциплине “Дискретная математика” для специальности 230105 (220400) “Программное обеспечение вычислительной техники и автоматизированных систем”
Томский государственный университет систем управления и радиоэлектроники ( тусур )
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconАннотация рабочей программы дисциплины Дискретная математика
Дисциплина ( Б. 2) «Дискретная математика» принадлежит базовой части математического и естественнонаучного цикла дисциплин подготовки...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconПрограмма дисциплины дискретная математика для направления 080500. 62 «Бизнес-информатика»
Требования к студентам: Изучение курса «Дискретная математика» не требует предварительных знаний, выходящих за пределы программ общеобразовательной...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconДжеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон
Индивидуальное домашнее задание по дисциплине «Дискретная математика» для студентов групп ас – 08, аи – 08, пм – 08, ук – 08, см...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconРабочая программа учебной дисциплины «Дискретная математика»
Дисциплина «Дискретная математика» входит в базовую часть (Б2) математического и естественнонаучного цикла. Для изучения дисциплины...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconПрограмма дисциплины Дискретная математика для социологов
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Пензенский государственный университет институт информатики и вычислительной техники Кафедра \"Дискретная математика\" Дискретная математика iconПримерная программа наименование дисциплины «Дискретная математика» Рекомендуется для направлений подготовки
Изучение дисциплины "Дискретная математика" должно воспитывать у слушателей творческое мышление, навыки самостоятельного решения...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница