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




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


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


Факультет вычислительной техники

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


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



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


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

по направлению 652000 "Мехатроника и робототехника"

специальности 220402 "Роботы и робототехнические системы",


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


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


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

"____" ____________ 2005 г.

2 РЕЦЕНЗЕНТ

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

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

"____" ____________ 2005 г.

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

Заведующий кафедрой "КТУ"

д.т.н., профессор А.И. Годунов

"____" ____________ 2005 г.

4 ВНЕСЕНА методической группой кафедры "Дискретная математика"

Руководитель

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

"____" ____________ 2005 г.

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

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

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

"____" ____________ 2005 г.

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

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

д.т.н., профессор А.И. Годунов

"____" ____________ 2005 г.


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

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

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


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

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

Предназначена для преподавателей, ведущих дисциплину, студентов специальности 220402 "Роботы и робототехнические системы" направления 652000 "Мехатроника и робототехника", изучающих дисциплину.


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

Государственный образовательный стандарт высшего профессионального образования. Направление подготовки дипломированного специалиста 652000 " Мехатроника и робототехника ".

Учебный план ПГУ по направлению 652000 " Мехатроника и робототехника " специальности 220402 "Роботы и робототехнические системы", утвержденный в 2005 г.

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

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


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

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

Общая

102/6







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

Лекции

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

68/4


34/2

34/2




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

Аудиторная

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

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

34/2




34/2





Контроль

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

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

экзамен





V семестр


V семестр






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

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

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

Знать:

основы формальной логики: исчисление высказываний; исчисление предикатов;

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

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

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

основы теории конечных автоматов и сетей Петри;

уметь:

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

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

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

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

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

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

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

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




аудиторных

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







лекционных

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







1

2

3

4

5

Введение в формальную логику, исчисление высказываний

2

2

2




Основы алгебры логики

2

2

2




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

2

2

2







1

2

3

4

5

Разложения булевых функций по переменным.

2

2

2




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

2

2

2




Методы минимизации булевых функций.

4

4

4




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

2

2

2




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

2

2

2




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

2

2

2




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

2

2

2




Логика предикатов

2

2

2




Формальные языки и грамматики.

2

2

2




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

2

2

2




Минимизация конечных автоматов.

2

2

2




Сети Петри.

2

2

2




Программная реализация автоматов и сетей.

2

2

2




Сумма:

34

34

34





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 Формальные языки и грамматики

Слова и языки. Формальные грамматики. DOL-системы и сверхслова. Регулярные языки и выражения.

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

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

7.1.14 Минимизация конечных автоматов

Информативные деревья. Эквивалентность автоматов. Различимость состояний автоматов. Минимизация автоматов.

7.1.15 Сети Петри

Определение сетей Петри. Маркировка сетей Петри. Диаграммы достижимых состояний. Использование сетей Петри как формальный аппарат для моделирования систем.

7.1.16 Программная реализация автоматов и сетей

Основные методы программной реализации автоматов и сетей.

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

Лекции.

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

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

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

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.1.11 Логика предикатов.

9.1.12 Формальные языки и грамматики.

9.1.13 Методы задания конечных автоматов.

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

9.1.15 Минимизация конечных автоматов.

9.1.16 Анализ сетей Петри

9.1.17 Применение сетей Петри

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

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

9.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 Горбатов В.А. Основы дискретной математики. Учеб. Пособие для студентов вузов – М.: Высшая школа, 1986 (128 экз.). – 311 с.

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

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

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

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

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

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

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

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

14.12 Котов В. Е. Сети Петри. – М.: Наука, 1984 (1 экз.). – 160 с.

14.13 Розенблюм Л. Я. Сети Петри // Изв. АН СССР. Техн. кибернетика. – 1983. – № 5. – С. 12-40.

14.14. Питерсон Дж. Теория сетей Петри и моделирование систем. – М.: Мир, 1984 (1 экз.). – 264 с.14.12 Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов – М.: ГИФМЛ, 1962. – 404 с.

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

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

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

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

Учебный

год

Учебная

группа

Решение

кафедры

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

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

Решение

выпускающей

кафедры

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

Лектор

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

Номер

изменения



























































































Похожие:

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


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