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




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


РПД ДМ / МО и ПЭВМ ________ 2006


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


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

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


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


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


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

по направлению 230100 "Информатика и ВТ",

специальности 230105 "Программное обеспечение вычислительной

техники и автоматизированных систем",


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

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


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

"____" ____________ 2006 г.

2 РЕЦЕНЗЕНТ

Председатель МК ИВТ

д.т.н., профессор Н.Н. Коннов

"____" ____________ 2006 г.

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

Заведующий кафедрой "МО и ПЭВМ"

к.т.н., профессор Б.Д. Шашков

"____" ____________ 2006 г.

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

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

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

"____" ____________ 2006 г.

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

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

к.т.н., профессор Б.Д. Шашков

"____" ____________ 2006 г.


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

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

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

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

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

Предназначена для преподавателей, ведущих дисциплину, и студентов специальности 230105 "Программное обеспечение вычислительной техники и автоматизированных систем" направления 230100 "Информатика и ВТ", изучающих дисциплину.

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

Государственный образовательный стандарт высшего профессионального образования. Направление подготовки дипломированного специалиста 230100 "Информатика и ВТ" (позиция ЕН.Ф.01.03).

Учебный план ПГУ по направлению 230100 "Информатика и ВТ" специальности 230105, утвержденный в 2006 г.

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

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

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

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

Общая

136/8

III семестр

IV семестр

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

Лекции

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

68/4


34/2

34/2




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

Аудиторная

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

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

68/4




68/4







Контроль

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

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

зачет

экзамен





III семестр



III семестр

III семестр







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

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

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

Знать:

основы теории множеств и общей алгебры;

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

основные элементы комбинаторного анализа;

основы алгебры логики и ее применения;

уметь:

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

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

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

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

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

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

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

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




аудиторных

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







лекционных

лабораторных







1

2

3

4

5

Множества и их спецификации, диаграммы Эйлера – Венна.

2

2

4




Отношения, свойства отношений, разбиения и отношение эквивалентности, отношение порядка.

2

2

4







1

2

3

4

5

Функции и отображения.

2

2

4




Операции на алгебраических структурах.

2

4

5




Основные понятия теории графов.

2

3

4




Маршруты, циклы, связность.

3

4

5




Раскраски. Планарные графы.

2

3

5




Деревья. Задачи подсчета деревьев специального вида.

3

3

5




Элементы комбинаторики.

2

2

4




Переключательные функции (ПФ).

2

2

5




Способы задания ПФ, специальные разложения ПФ, не полностью определенные (частные) ПФ.

3

3

5




Минимизация ПФ и не полностью определенных ПФ.

2

4

5




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

3



5




Разрешимые и неразрешимые проблемы.

2



4




Схемы алгоритмов, схемы потоков данных.

2



4




Сумма:

34

34

68





7. Лекции

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

7.1.1 Множества и их спецификации, диаграммы Венна

Множества, диаграммы Эйлера – Венна. Подмножества, операции над множествами. Покрытия, разбиения и перечисление элементов множеств. Числа Стирлинга второго рода. Представление множеств в ЭВМ. Коды Грея.

7.1.2 Отношения, свойства отношений, разбиения и отношение эквивалентности, отношение порядка

Отношения и их свойства. Представление отношений графами. Композиция отношений. Отношение эквивалентности и его свойства. Отношение порядка и его свойства. Матричное представление отношений.

7.1.3 Функции и отображения

Функции, их свойства. Представление функций в ЭВМ. Инъекция, сюръекция и биекция, их свойства. Подстановки, перестановки, группы подстановок. Представление подстановок циклами. Знак подстановки. Числа Стирлинга первого рода.

7.1.4 Операции на алгебраических структурах

Операции на алгебраических структурах. Группы, подгруппы, нормальные группы, их свойства. Теоремы Лагранжа и Кэли. Кольца, их основные свойства. Кольца многочленов, их свойства. Подкольца, идеалы, их свойства. Поля, их основные свойства. Алгоритм деления многочленов.

7.1.5 Основные понятия теории графов

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

7.1.6 Маршруты, циклы, связность

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

7.1.7 Раскраски. Планарные графы

Вершинные и реберные раскраски графа. Хроматическое число и хроматический индекс, их свойства. Планарность. Теорема Понтрягина – Куратовского. Теорема о четырех красках.

7.1.8 Деревья. Задачи подсчета деревьев специального вида

Деревья. Матричная теорема о деревьях, подсчет числа остовов. Подсчет кубических деревьев специального вида. Числа Фибоначчи и Каталана, их свойства.

7.1.9 Элементы комбинаторики

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

7.1.10 Переключательные функции (ПФ)

Основные понятия, связанные с булевым кубом и функциями алгебры логики. Элементарные булевы функции. Формулы. Реализация булевых функций формулами. Принцип двойственности. Основные классы булевых функций. Базовые функциональные элементы.

7.1.11 Способы задания ПФ, специальные разложения ПФ, не полностью определенные (частные) ПФ

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

7.1.12 Минимизация ПФ и не полностью определенных ПФ

Виды дизъюнктивных нормальных форм (ДНФ) и конъюнктивных нормальных форм (КНФ). Методы получения сокращенных ДНФ (КНФ) и их минимизации: использование булева куба, метод Блейка – Порецкого, метод Квайна – Макласки, метод минимизирующих карт. Реализация булевых функций схемами из функциональных элементов.

7.1.13 Теорема о функциональной полноте, примеры функционально полных базисов

Полнота и замкнутость. Важнейшие замкнутые классы. Теорема о полноте. Примеры функционально полных базисов.

7.1.14 Разрешимые и неразрешимые проблемы

Основные понятия о разрешимых и неразрешимых проблемах. Алгоритмы и разрешимость.

7.1.15 Схемы алгоритмов, схемы потоков данных

Схемы алгоритмов, схемы потоков данных и использовании теории графов и теории конечных автоматов для их описания.

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

Лекции.

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

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

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

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

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

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

9.1.1 Множества, операции над множествами.

9.1.2 Отношения, их представления и свойства.

9.1.3 Функции, их представления и свойства.

9.1.4 Операции над алгебраическими структурами.

9.1.5 Графы и их основные свойства.

9.1.6 Маршруты, цепи, циклы, связность.

9.1.7 Задачи на графах. Паросочетания, раскраски и планарность

9.1.8 Деревья. Элементы комбинаторики.

9.1.9 Функции алгебры логики. Реализация формулами и схемами

9.1.10 Минимизация функций алгебры логики. Реализация формулами и схемами

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

Занятия проводятся в компьютерном классе.

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

Персональные компьютеры.

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 Говорухин В. Н., Цибулин В. Г. Введение в Maple. Математический пакет для всех. – М.: Мир, 1997. – 208 с.

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

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

14.6 Сачков В. Н. Введение в комбинаторные методы дискретной математики. – М.: Наука, 1982 (20 экз.). – 384 с.

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

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

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

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

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

14.12 Минский М. Вычисления и автоматы. – М.: Мир, 1971 (3 экз.). – 364 с.

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
обратиться к администрации
Библиотека
Главная страница