Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника



Скачать 88.99 Kb.
Дата23.12.2012
Размер88.99 Kb.
ТипРабочая программа
Федеральное агентство по образованию

Федеральное государственное образовательное учреждение

высшего профессионального образования

“Чувашский государственный университет имени И.Н. Ульянова”

Технический институт

Факультет дизайна и компьютерных технологий

Кафедра компьютерных технологий
СОГЛАСОВАНО УТВЕРЖДАЮ

Декан ФДиКТ Проректор

проф._________________ В.П. Желтов ____________________ В.Г. Агаков

«___» _________________ 2009 г. «____» ___________________ 2009 г.

РАБОЧАЯ ПРОГРАММА
Дисциплина Дискретная математика

Направление 230100 – Информатика и вычислительная техника

Специальность 230102 – АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ

ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

Заочная форма

БЮДЖЕТ ВРЕМЕНИ (час.)




Семестр

Всего

Аудиторные занятия

Самост. работа, включая курсовое проектир-ие

Итоговый контроль

Форма

обу­чения

Всего аудит.

лекции

практ

лабор

экз

зач

кур. про­ект (ра­бота), контр. работа

заоч.

2

140

16

10

6

-

124

+



контр., курсовая

заоч. сокр.

2

140

16

10

6

-

124

+



контр.
, курсовая


Рабочая программа составлена в соответствии с государственным образовательным стандартом высшего профессионального образования направления подготовки дипломированного специалиста 654600 – Информатика и вычислительная техника, специальности 230102 – Автоматизированные системы обработки информации и управления, утвержденным 27 марта 2000г. (Регистрационный номер 224 тех/дс).
Составитель, ассистент А.Н. Мытников

Рабочая программа обсуждена, одобрена и рекомендована к использованию на заседании кафедры компьютерных технологий, «___» ___________ 20__ г., протокол №___
Зав. кафедрой компьютерных технологий,

профессор В.П. Желтов

Рассмотрена и одобрена методическим советом ФДиКТ

Председатель методсовета, доцент кафедры КТ В.Г. Захаров
Чебоксары – 2009 г.

Государственный образовательный стандарт

по специальности АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ

ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ
Множества и их спецификации; диаграммы Венна; отношения; свойства отношений; разбиения и отношение эквивалентности; отношение порядка; функции и отображения; операции; основные понятия теории графов; маршруты; циклы; связность; планарные графы; переключательные функции (ПФ); способы задания ПФ; специальные разложения ПФ; неполностью определенные (частные) ПФ; минимизация ПФ и неполностью определенных ПФ; теорема о функциональной полноте; примеры функционально-полных базисов; разрешимые и неразрешимые проблемы; схемы алгоритмов; схемы потоков данных.
ПРЕДИСЛОВИЕ
Дискретная математика имеет дело с совокупностями объектов, называемых множествами, и определенными на них структурами Элементы этих множеств, как правило, изолированы друг от друга и геометрически не связаны. Дискретная математика привлекается для решения задач на компьютере в терминах аппаратных средств и программного обеспечения с привлечением организации символов и манипуляции данными. Понимание принципов работы компьютера можно достигнуть, если представить машину как дискретную математическую систему.

Цель курса «Дискретная математика» – обеспечить у будущего инженера формирование достаточно глубокой фундаментальной основы и вооружение его конкретными знаниями, умениями и навыками, позволяющими согласовать фундаментальность курса с профессиональной направленностью его деятельности.

Ориентируя преподавание дискретной математики на обеспечение фундаментальной подготовки, реализовать в полной мере соответствующие задачи:

- понимание основных идей, понятий, теорий и методов дискретной математики;

- формирование представлений о дискретной математике как о научной дисциплине;

- знание структурной и групповой точек зрения на дискретную математику.

Реализуя цели, обусловленные прикладной направленностью подготовки инженера, осуществлять:

- демонстрацию практических приложений дискретной математики в науке, технике, и т.п.;

- обучение созданию и использованию дискретных моделей при решении практических задач, прогнозированию явлений;

- развитие логического, конструктивного, наглядно-образного мышления;

- обеспечение междисциплинарного подхода, в том числе внутри самой математики
Требования к уровню усвоения содержания дисциплины

В результате изучения дисциплины «Дискретная математика»

а) студент должен знать:

  1. Основные понятия теории множеств и отношений;

  2. Основные понятия теории булевых функций;

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

  4. Основные понятия логики высказываний и предикатов.

  5. Основные понятия переключательных функций.


б) студент должен уметь:

  1. Применять комбинаторные конфигурации для решения задач.

  2. Определять тип бинарного отношения и его свойства.

  3. Представлять графы различными способами, выполнять операции над графами.

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

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

  6. Решать задачи о путях во взвешенных орграфах.

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

  8. Строить минимальные ДНФ.


Содержание дисциплины «Дискретная математика»

Основные разделы дисциплины

1. Элементы теории множеств и отношений:

а) основные понятия теории множеств;

б) отношения и функции.

2. Дискретные структуры:

а) теория графов;

б) сети.

3.Дизъюнктивные нормальные формы и схемы из функциональных элементов:

а) представление булевых функций формулами.

б) нормальные формы;

в) переключательные функции.
Темы, их содержание и объем в часах лекционных занятий

2 семестр (10 часов)
Тема 1. Функциональные системы с операциями – 3 ч.
Основы теории множеств и отношений:

Основные понятия теории множеств (элементы множеств, способы задания, графическая интерпретация, диаграммы Венна, операции над множествами). Мощность множества. Декартово произведение множеств, его свойства. Комбинаторные конфигурации.

Отношения и функции:

Отображения. Инъекция, биекция, сюръекция. Отношения. Функции. Соответствие как обобщение понятия отображения. График и граф соответствия. Композиция соответствий. Ограничение, сужение соответствия. Специальные свойства бинарных отношений. Отношение эквивалентности. Отношения порядка. Упорядоченные и линейно упорядоченные множества.
Тема 2. Дискретные структуры (графы, сети, коды) – 3 ч.
Теория графов:

Понятие графа. Виды графов. Элементы графа. Операции над графами. Способы представления графов. Маршруты. Циклы. Достижимость. Связность. Расстояния в графах. Степени вершин. Планарные графы. Деревья. Лес. Раскраска графов.

Сети:

Порядковая функция сети. Топологическая сортировка.
Тема 3. Дизъюнктивные нормальные формы и схемы из функциональных элементов – 4 ч.
Представление булевых функций формулами:

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

Нормальные формы:

Дизъюнктивные и конъюнктивные нормальные формы. Построение минимальных ДНФ: алгоритм простой склейки, тупиковые ДНФ. Схемы из функциональных элементов.

Переключательные функции:

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

Практические занятия, их содержание, объем в часах

2 семестр (6 часов)
Тема 1. Основные понятия теории множеств (элементы множеств, способы задания, графическая интерпретация, диаграммы Венна, операции над множествами). Отображения. Инъекция, биекция, сюръекция. – 2 ч.

Тема 2. Понятие графа. Виды графов. Элементы графа. Операции над графами. Способы представления графов. – 2 ч.

Тема 3. Таблицы булевых функций. Правила подстановки и замены. Двойственные булевы функции. – 2 ч.

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

Примерный перечень вопросов к экзамену
1. Основные понятия теории множеств: элементы множеств, способы задания, диаграммы Венна, графическая интерпретация, операции над множествами.

2. Декартово произведение множеств, его свойства. Декартова степень множества.

3. Комбинаторные конфигурации.

4. Отображения. Инъекция, биекция, сюръекция.

5. Соответствие как обобщение понятия отображения.

6. График и граф соответствия.

7. Композиция соответствий.

8. Свойства композиции соответствий.

9. Специальные свойства бинарных отношений.

10. Классы бинарных отношений на множестве.

11. Отношение эквивалентности.

12. Функции. Обратимые функции. Композиция функций.

13. Отношения порядка. Упорядоченные и линейно упорядоченные множества.

14. Мощность множества. Счетные множества.

15. Понятие графа. Виды графов.

16. Элементы графа.

17. Операции над графами.

18. Способы представления графов.

19. Маршруты. Достижимость. Связность.

20. Расстояния в графах.

21. Подграф.

22. Деревья. Лес.

23. Остовное дерево наименьшего веса.

24. Сеть. Порядковая функция сети.

25. Топологическая сортировка.

26. Ориентированная сеть и упорядоченное множество: связь понятий.

27. Понятие булевой функции.

28. Таблицы булевых функций.

29.Представление булевых функций формулами.

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

31.Двойственные булевы функции.

32.Дизъюнктивные и конъюнктивные нормальные формы.

33.Схемы из функциональных элементов.

34.Способы задания ПФ.

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

36.Функционально-полные базисы.
Литература

Основная

  1. Новиков Ф.А. Дискретная математика для программистов. Санкт-Петербург. Питер, 2001.

  2. Яблонский С.В. Введение в дискретную математику. Москва. Высшая школа, 2001.

  3. Уилсон Р. Дж. Введение в теорию графов. - М.: 1977.

  4. Березина Л.Ю. Графы и их применения. - М.: Просвещение, 1979.

  5. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: ВШ, 1976.

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

  1. Горбатов В.А Основы дискретной математики. Москва. Высшая школа, 1986.

  2. Емеличев В.А. Лекции по теории графов. - М.: Наука, 1990.

  3. Оре О. Теория графов. - М.: Наука, 1968.

  4. Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией. - М.: 1976.

  5. Кейслер Г., Чен Ч.Ч. Теория моделей. - М.: Мир, 1977.

  6. Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука,1979.

  7. Шайн Б. М. Лекции о полугруппах преобразований.

  8. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. - Екатеринбург: Изд-во УрГУ, 1996.

  9. Богомолов А.В., Салий В.Н. Алгебраические основы теории дискретных систем. - М.: Наука, 1997.

  10. Биркгоф Г., Барти Т. Современная прикладная алгебра. - М.: Мир, 1976.

Похожие:

Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconОбразовательная программа по направлению 230100 " Информатика и вычислительная техника" специальность 230101, «Вычислительные машины, комплексы, системы и сети»
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по направлению...
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconРабочая программа дисциплина гсэ. Р. 02 Методы научных исследований направление 654600 Информатика и вычислительная техника
Специальность 230102 – Автоматизированные системы обработки информации и управления
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconРабочая программа по дисциплине "Дискретная математика" для специальности 230105 (220400)
Гос во по направлению 654600 Информатика и вычислительная техника (специальность 230105 (220400) – “Программное обеспечение вычислительной...
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconРабочая программа дисциплины математическая логика и теория алгоритмов
Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению...
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 230100 «Информатика и вычислительная техника»
Курс входит в профессиональный цикл ооп 230100 «Информатика и вычислительная техника»
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconПрограмма дисциплины математическая статистика. Направление подготовки 010100. 62 математика (вычислительная математика и информатика)
Направление подготовки 010100. 62 математика (вычислительная математика и информатика)
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconПрограмма дисциплины функциональный анализ Направление подготовки 010100. 62 математика (вычислительная математика и информатика)
Направление подготовки 010100. 62 математика (вычислительная математика и информатика)
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconСостав групп 1 курса факультета ивт направление 230100 «Информатика и вычислительная техника»
Профиль «Программное обеспечение вычислительной техники и автоматизированных систем»
Рабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника iconРабочая программа по дисциплине «дискретная математика» для специальности
Рабочая программа составлена на основании гос впо 010200 – Прикладная математика и информатика, утвержденного в 2000 г
Разместите кнопку на своём сайте:
ru.convdocs.org


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