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

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



НазваниеРабочая программа дисциплины дискретная математика
Дата конвертации05.06.2013
Размер164.01 Kb.
ТипЛекции
скачать >>>

УТВЕРЖДАЮ

Проректор-директор ИК

________________ Сонькин М.А.

«___»_____________2011 г.


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

ДИСКРЕТНАЯ МАТЕМАТИКА


НАПРАВЛЕНИЕ ООП 230100 Информатика и вычислительная техника,

230400 Информационные системы и технологии


ПРОФИЛИ ПОДГОТОВКИ Вычислительные машины, комплексы, системы и сети, Системы автоматизированного проектирования, Геоинформационные системы, Информационные системы и технологии в бизнесе


КВАЛИФИКАЦИЯ (СТЕПЕНЬ) бакалавр

^ БАЗОВЫЙ УЧЕБНЫЙ ПЛАН ПРИЕМА 2011 г.

КУРС 2 СЕМЕСТР 3

КОЛИЧЕСТВО КРЕДИТОВ 6 кредитов ECTS

ПРЕРЕКВИЗИТЫ Б2.Б3


ВИДЫ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ И ВРЕМЕННОЙ РЕСУРС:

Лекции 36 час.

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

^ АУДИТОРНЫЕ ЗАНЯТИЯ 81 час.

САМОСТОЯТЕЛЬНАЯ РАБОТА 72 час.

ИТОГО 153час.

ФОРМА ОБУЧЕНИЯ очная


ВИД ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ экзамен


^ ОБЕСПЕЧИВАЮЩЕЕ ПОДРАЗДЕЛЕНИЕ кафедра ВТ


ЗАВЕДУЮЩИЙ КАФЕДРОЙ ВТ ____________ Марков Н.Г., профессор

РУКОВОДИТЕЛЬ ООП ____________ Рейзлин В.И., доцент

____________ Дмитриева Е.А., доцент

ПРЕПОДАВАТЕЛЬ ____________ Буркатовская Ю.Б., доцент


2011 г.

  1. ^ ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

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

Поставленные цели полностью соответствуют целям (Ц1-Ц3, Ц5) ООП.

^ 2.МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП

Дисциплина «Дискретная математика» (Б2.В1.1) входит в математический и естественнонаучный цикл (Б2) и является базовой вариативной части (Б2.В).

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

Пререквизитами данной дисциплины являются дисциплины математического и естественнонаучного цикла (Б2): «Математика» (Б2.Б3).

  1. ^ РЕЗУЛЬТАТЫ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Планируемым результатом освоения дисциплины является способность применять базовые и специальные естественно-научные и математические знания в области информатики и вычислительной техники, достаточные для комплексной инженерной деятельности (Р1).

В результате освоения дисциплины (Р1) студент должен:

знать:

теорию булевых функций и основы теории графов (З.1.4):

  • графы, их классификация и способы задания (З.1.4.1);

  • связность графов (З.1.4.2);

  • поиск путей в графе (З.1.4.3);

  • деревья (З.1.4.4);

  • эйлеровы и гамильтоновы графы (З.1.4.5);

  • основные понятия теории булевых функций (З.1.4.6);

  • нормальные формы (З.1.4.7);

  • минимизация булевых функций (З.1.4.8);

  • минимизация не полностью определенных булевых функций (З.1.4.9);

  • минимизация систем булевых функций (З.1.4.10);

уметь:

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

  • применять методы минимизации булевых функций для решения практических задач из области схемотехники (У.1.4.1);

  • применять методы и алгоритмы теории графов для формализации и решения оптимизационных задач (У.1.4.2);

владеть:

методами и алгоритмами теории графов и теории булевых функций (В.1.4):

  • поиск оптимальных путей (В.1.4.1);

  • построение кратчайшего остова (В.1.4.2);

  • поиск эйлеровых и гамильтоновых циклов (В.1.4.3);

  • минимизация булевых функций (В.1.4.4);

  • минимизация не полностью определенных булевых функций (В.1.4.5);

  • минимизация систем булевых функций (В.1.4.6).

В процессе освоения дисциплины у студентов развиваются следующие компетенции:

1.Универсальные (общекультурные):

- владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1 ФГОС);

- использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10 ФГОС).

2. Профессиональные:

- разрабатывать модели компонентов информационных систем, включая модели баз данных (ПК- 4 ФГОС);

- разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технологии программирования (ПК-5 ФГОС);

- обосновывать принимаемые проектные решения, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности (ПК-6 ФГОС).


^ 4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

4.1 Аннотированное содержание разделов дисциплины:

1. Основы теории графов. История развития теории графов и область ее применения. Графы, их классификация и способы задания. Изоморфные графы. Подграф. Маршруты в графе, диаметр, радиус и центры графа. Связность. Теорема об оценке числа ребер в графе и следствие о связном графе. Обход графа в глубину и в ширину. Поиск кратчайшего пути: волновой алгоритм. Поиск минимального пути: алгоритм Дейкстра. Деревья. Теорема о шести эквивалентных утверждениях о дереве. Поиск кратчайшего остова: алгоритм Краскала. Эйлеровы графы. Необходимое и достаточное условие эйлеровости графа. Алгоритм Флери. Гамильтоновы графы. Теорема Дирака. Задача коммивояжера.

^ 2. Основные понятия теории булевых функций. Булевы константы и векторы. Булево пространство, способы задания булева пространства. Интервал в булевом пространстве. Булевы переменные. Булева функция, способы ее задания. Теорема о числе булевых функций. Фиктивные переменные. Элементарные булевы функции. Формула как способ задания функции. Тождественно истинная и тождественно ложная формулы, равносильные формулы, способы доказательства равносильностей, основные равносильности. Двойственная функция, утверждение о взаимности, двойственная формула, принцип двойственности, следствие.

^ 3. Нормальные формы булевых функций. Формула Шеннона, разложение булевой функции по к переменным. Совершенная дизъюнктивная нормальная форма (СовДНФ), утверждение о ее существовании и единственности, алгоритм построения СовДНФ по таблице истинности. Совершенная конъюнктивная нормальная форма (СовКНФ), утверждение о ее существовании и единственности, алгоритм построения СовКНФ по таблице истинности. Элементарная конъюнкция, ранг, полная конъюнкция, утверждение о конъюнкции и интервале. Дизъюнктивная нормальная форма (ДНФ), ее длина и ранг, преобразование ДНФ в СовДНФ, построение матрицы Грея по ДНФ и ДНФ по матрице Грея.

^ 4. Минимизация булевых функций. Импликанта, простая импликанта, сокращенная ДНФ. Минимальная, кратчайшая и безызбыточная ДНФ. Поиск сокращенной ДНФ: теорема Квайна и алгоритм Квайна-МакКласки, теорема Блейка и алгоритм Блейка-Порецкого. Поиск кратчайщей ДНФ: таблица Квайна, покрытие, его длина, минимальное, кратчайшее и безызбыточное покрытие. Алгоритмы поиска одного и всех безызбыточных покрытий, кратчайшего покрытия. Приближенная кратчайшая ДНФ, метод Закревского.

^ 5. Не полностью определенные булевы функции и системы булевых функций. Определение и способы задания не полностью определенных (частичных) булевых функций, доопределение. Точный метод минимизации, метод Закревского, метод конкурирующих интервалов. Системы булевых функций. Кратчайшая и безызбыточная системы ДНФ. Минимизация системы булевых функций: метод конкурирующих интервалов.


4.2 Структура модуля по разделам и формам организации обучения приведена в таблице 1.

Таблица 1.

Структура дисциплины

по разделам и формам организации обучения

Название раздела/темы

Аудиторная работа (час)

СРС

(час)

Колл,

Контр.Р.

Итого

Лекции

Практ./сем.

занятия

Лаб. зан.

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

8

12




16




36

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

8

8




16




32

3. Нормальные формы булевых функций

6

8




12




26

4. Минимизация булевых функций

8

9




16




33

5. Не полностью определенные булевы функции и системы булевых функций

6

8




12




26

Итого

36

45




72




153


4.3 Распределение компетенций по разделам дисциплины

Таблица 2.

Распределение по разделам дисциплины планируемых результатов обучения



Формируемые

компетенции

Разделы дисциплины

1

2

3

4

5



З.1.4.1

+















З.1.4.2

+















З.1.4.3

+















З.1.4.4

+















З.1.4.5

+















З.1.4.6




+












З.1.4.7







+









З.1.4.8










+






З.1.4.9













+



З.1.4.10













+



У.1.4.1.













+



У.1.2.4.

+















В.1.4.1

+















В.1.4.2

+















В.1.4.3

+















В.1.4.4










+






В.1.4.5













+



В.1.4.6













+



^ 5. ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ

В таблице 3 приведено описание образовательных технологий, используемых в данном модуле.


Таблица 3.

Методы и формы организации обучения (ФОО)

ФОО


Методы

Лекц.

Лаб. раб.

Пр. зан./

Сем.,

Тр*., Мк**

СРС

К. пр.

IT-методы













+




Работа в команде







+




+




Case-study



















Игра



















Методы проблемного обучения.

+




+










Обучение

на основе опыта



















Опережающая самостоятельная работа













+




Проектный метод













+




Поисковый метод







+




+




Исследовательский метод



















Другие методы



















* - Тренинг, ** - Мастер-класс


^ 6. ОРГАНИЗАЦИЯ И УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ

6.1 Самостоятельную работу студентов (СРС) можно разделить на текущую и творческую.

^ Текущая СР – работа с лекционным материалом, подготовка к практическим занятиям с использованием сетевого образовательного ресурса (Web CT); опережающая самостоятельная работа; выполнение домашних заданий; изучение тем, вынесенных на самостоятельную проработку; подготовка к экзамену.

^ Творческая проблемно-ориентированная самостоятельная работ

(ТСР) – поиск, анализ, структурирование информации и разработка программ, реализующей алгоритмы дискретной математики.


^ 6.2 Содержание самостоятельной работы студентов по модулю

Темы индивидуальных заданий:

алгоритмы поиска путей;

построение фактор-графа;

поиск кратчайшего цикла;

задача коммивояжера;

построение сокращенной ДНФ;

поиск кратчайших ДНФ;

метод конкурирующих интервалов.


^ Темы для самостоятельного изучения:

задача почтальона;

поиск паросочетаний и покрытий в графе;

поиск максимального потока в сети;

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


^ 6.3 Контроль самостоятельной работы

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

Самоконтроль в обучающей программе.

Рубежный контроль в виде пяти контрольных работ.

Написание программ, реализующих изученные алгоритмы.

По результатам текущего и рубежного контроля формируется допуск студента к экзамену. Экзамен проводится в письменной форме и оценивается преподавателем.

    1. ^ Учебно-методическое обеспечение самостоятельной работы студентов

Для самостоятельной работы студентов используются сетевые образовательные ресурсы, представленные в среде Web CT.


^ 7. СРЕДСТВА (ФОС) ТЕКУЩЕЙ И ИТОГОВОЙ ОЦЕНКИ КАЧЕСТВА ОСВОЕНИЯ МОДУЛЯ

Для организации текущего контроля полученных студентами знаний по данной дисциплине используются 15 тестов. Каждый тест имеет 2 или 3 варианта и содержит 10 вопросов. Образец контролирующего теста приведен ниже (ПРИЛОЖЕНИЕ 1). Для проведения экзамена предлагаются 40 вопросов. Экзаменационный билет содержит 6 вопросов.


^ 8. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

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

  1. С.В.Яблонский. Введение в дискретную математику. - М.: Наука, 1979.

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

  3. С.В.Быкова, Ю.Б.Буркатовская. Булевы функции. Изд-во ТГУ, 2010.

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

  5. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.:БХВ-Петербург, 2006.



  • дополнительная литература:

  1. Б.М.Логинов. Введение в дискретную математику. — Калуга, 1998.

  2. Н.Кристофидес. Теория графов. Алгоритмический подход. - М.: Мир, 1977.

  3. А.И.Белоусов, С.В.Ткачев. Дискретная математика. - М., изд-во МГТУ им. Баумана, 2002.



  • программное обеспечение и Internet-ресурсы:



  1. Мультимедийный электронный учебник «Дискретная математика»

http://e-le.lcg.tpu.ru/public/DISM_0961/index.html





Программа составлена на основе Стандарта ООП ТПУ в соответствии с требованиями ФГОС по направлению 230100 «Информатика и вычислительная техника» и профилю подготовки «Вычислительные машины, комплексы, системы и сети», «Системы автоматизированного проектирования»; по направлению 230400 «Информационные системы и технологии» и профилям подготовки «Геоинформационные системы», «Информационные системы и технологии в бизнесе»

Программа одобрена на заседании кафедры вычислительной техники


(протокол № ____ от «___» _______ 2011 г.).


Автор ________________________________ Буркатовская Ю.Б.


Рецензент(ы) __________________________




Похожие:

Рабочая программа дисциплины дискретная математика iconФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика

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

Рабочая программа дисциплины дискретная математика iconНаправление: 010100. 62 «Математика» Подготовка
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины теория информационных процессов и систем
Пререквизиты: «Информатика», «Математика», «Математическая логика и теория алгоритмов», «Дискретная математика»
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика
Профиль подготовки: Автоматизация технологических процессов и производств в нефтегазовой отрасли
Рабочая программа дисциплины дискретная математика iconФакультет математики
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика
В результате освоения данной дисциплины бакалавр приобретает знания, умения и навыки, обеспечивающие достижение целей Ц1, Ц3, Ц5...
Рабочая программа дисциплины дискретная математика iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика»

Рабочая программа дисциплины дискретная математика iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы