ОДОБРЕНО

Цикловой комиссией ПЦ

специальности 230113

Председатель

_________ О.А. Бердыева

«___» ___________ 2012 г.

УТВЕРЖДАЮ

Директор ГБОУ СПО «ОНТ

_________ А.С. Дорофеев

«___» _________ 2012 г.

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

ОП.08 ДИСКРЕТНАЯ МАТЕМАТИКА

ОПОП по специальности

230113 Компьютерные системы и комплексы

Отрадный,2012

Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее - ФГОС) по специальности среднего профессионального образования (далее - СПО)

230113 Компьютерные системы и комплексы

и примерной программы по дисциплине утвержденной ………… "____"_________ 2012 года

Составитель:

Юдина А.И.

преподаватель ГБОУ СПО "ОНТ"

2КК

Эксперты:

Внутренняя экспертиза

Техническая экспертиза

Минеева И.Ю.

методист

ГБОУ СПО "ОНТ"

Содержательная экспертиза

Бердыева О.А.

председатель ЦК,

преподаватель

ГБОУ СПО "ОНТ"

Внешняя экспертиза

Содержательная экспертиза

С О Д Е Р Ж А Н И Е

стр.

1. Паспорт рабочей программы учебной дисциплины

4

2. Структура и содержание учебной дисциплины

6

3. Условия реализации учебной дисциплины

9

4. Контроль и оценка результатов освоения учебной дисциплины

10

5. Приложение 1

12

6. Приложение 2

14

7. Лист изменений и дополнений, внесенных в рабочую программу

16

1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

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

1.1. Область применения рабочей программы

Рабочая программа учебной дисциплины является частью основной профессиональной образовательной программы ГБОУ СПО «ОНТ» по специальности СПО
230113 Компьютерные системы и комплексы (базовая подготовка), разработанной в соответствии с ФГОС СПО третьего поколения.

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

Рабочая программа составлена для использования по очной форме обучения.

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

1.3. Цели и задачи учебной дисциплины - требования к результатам освоения учебной дисциплины:

Базовая часть

В результате освоения учебной дисциплины обучающийся должен уметь:

• формулировать задачи логического характера и применять средства математической логики для их решения;

• применять законы алгебры логики;

• определять типы графов и давать их характеристики;

• строить простейшие автоматы;

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

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

• логические операции, формулы логики, законы алгебры логики;

• основные классы функций, полнота множества функций, теорема Поста;

• основные понятия теории множеств, теоретико- множественные операции и их связь с логическими операциями;

• логика предикатов, бинарные отношения и их виды;

• элементы теории отображений и алгебры подстановок;

• метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

• основные понятия теории графов, характеристики и виды графов;

• элементы теории автоматов

Вариативная часть - не предусмотрено.

Содержание дисциплины должно быть ориентировано на подготовку студентов к освоению профессиональных модулей ОПОП по специальности 230113 Компьютерные системы и комплексы и овладению профессиональными компетенциями (ПК) (Приложение 1):

ПК 1.1. Разрабатывать схемы цифровых устройств на основе интегральных схем разной степени интеграции.

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

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

В процессе освоения дисциплины у студентов должны формировать общие компе­тенции (ОК) (Приложение 2):

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

ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.

ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.

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

ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).

1.4. Количество часов на освоение учебной дисциплины:
максимальной учебной нагрузки студента 102 часа, в том числе:

обязательной аудиторной учебной нагрузки студента 68 часов;
самостоятельной работы студента 34 часов.

2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

2.1. Объем учебной дисциплины и виды учебной работы

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

104

Обязательная аудиторная учебная нагрузка (всего)

68

в том числе:

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

не предусмотрено

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

24

контрольные работы

не предусмотрено

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

не предусмотрено

Самостоятельная работа обучающегося (всего)

34

в том числе:

самостоятельная работа над курсовой работой (проектом)

не предусмотрено

поиск информации и написание докладов на заданные темы;

создание тематических кроссвордов;

создание тестов;

оформление наглядных пособий;

создание графов;

построение контактных схем.

4

6

6

4

6

8

Форма промежуточной аттестации

Дифференцированный зачёт

2.2. Тематический план и содержание учебной дисциплины дискретная математика

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

Содержание учебного материала, лабораторные и практические занятия, самостоятельная работа обучающихся, курсовая работ (проект)

Объем часов

Уровень освоения

1

2

3

4

Раздел 1. Дискретная математика.

102

Тема 1.1. Языки описания цифровых автоматов.

Содержание учебного материала

10

3

1

Классификация языков.

Входной алфавит, выходной алфавит, множество событий, дизъюнкция , конъюнкция, классификация языков описания автомата.

2.

Элементы теории графов.

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

Лабораторные работы

-

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

10

1.

2.

3.

4.

5.

Построение автоматов и операции с ними.

Построение графов и способы их задания.

Работа с деревьями и остовами.

Построение Эйлеровых графов.

Изучение путей и циклов в графах.

Контрольные работы

-

Самостоятельная работа обучающихся

Сложение графов. Поиск изоморфизма графов. Нахождение путей, циклов, мостов и компонент связности. Отыскание гамильтоновых и эйлеровых циклов. Изучение планарности. Раскрашивание графов. Нахождение матриц смежности. Отыскание кратчайших путей. Создание графов.

10

Тема 1.2. Логические функции и алгебра предикатов.

Содержание учебного материала

10

2

1

Логические функции.

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

2

Алгебра предикатов.

Предикаты на множестве и их связь с отношением. Логические операции над предикатами. Формулы алгебры предикатов. Выполнимые, тождественно истинные и тождественно ложные формулы. Реализация булевых функций контактными и функциональными схемами. Построение контактных схем, реализующих булеву функцию или схему булевых функций методом каскадов. Понятие о функции сложности Шеннона

Лабораторные работы

-

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

10

1.

2.

3.

Изучение многочлена Жегалкина.

Изучение функциональной полноты и замкнутых классов.

Изучение критерий Поста.

Контрольные работы

-

Самостоятельная работа обучающихся

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

Создание тематических кроссвордов.

Создание тестов.

Оформление наглядных пособий.

Построение контактных схем.

16

Тема 1.3. Алгоритмы и их сложность.

Содержание учебного материала

10

1.

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

Лабораторные работы

-

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

-

Контрольные работы

-

Самостоятельная работа обучающихся

-

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

Содержание учебного материала

8

1.

Основные понятия. Языки и грамматика. Эквивалентность состояний. Алгоритм разбиения состояний. Автоматы без потери информации. Регулярные автоматы. Линейные автоматы. Периодичность в линейных автоматах.

Лабораторные работы

-

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

-

Контрольные работы

-

Самостоятельная работа обучающихся

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

Создание тематических кроссвордов.

Создание тестов

6

Тема 1.5 Линейные коды.

Содержание учебного материала

6

1.

Постановка задач теории кодирования. Общие границы параметров кодов. Линейные коды. Порождающая и проверочная матрицы. Процесс кодирования и декодирования. Граница Варшамова-Гилберта. Коды Хемминга. Циклические коды и их декодирование. Распределение весов кода. Тождество Мак-Вильямс. Оптимальные Коды Фано и Хаффмена.

Лабораторные работы

-

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

-

Контрольные работы

-

Самостоятельная работа обучающихся

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

6

Примерная тематика курсовой работы (проекта)

-

Самостоятельная работа обучающихся над курсовой работой (проектом)

-

Всего:

102

Для характеристики уровня усвоения материала используются следующие обозначения:

1 - ознакомительный (узнавание ранее изученных объектов, свойств);

2 - репродуктивный (выполнение деятельности по образцу, инструкции или под руководством);

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

3. УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ

3.1. Требования к минимальному материально-техническому обеспечению
Реализация программы дисциплины требует наличия кабинета математических дисциплин.

Оборудование учебного кабинета:

• посадочные места по количеству обучающихся;

• рабочее место преподавателя;

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

• аудиторная доска для письма;

• компьютерные столы по числу рабочих мест обучающихся;

• вентиляционное оборудование, обеспечивающие комфортные условия проведения занятий.

Технические средства обучения:

• персональные компьютеры с лицензионным программным обеспечением;

• лазерный принтер;

• устройства вывода звуковой информации: звуковые колонки.

3.2. Информационное обеспечение обучения

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Основные источники:

Для преподавателей

1. Андерсон О. Дискретная математика и комбинаторика. Андерсон, Джеймс А. - Пер. с англ. - М. : Издатель- Издательский дом "Вильямс", 2004. - 960 с.

2. Аляев Ю.А. Дискретная математика и математическая логика. Аляев Ю.А. Тюрин С.Ф. - М.: Финансы и статистика, 2006. - 368 с.

3. Асанов М.О. Дискретная математика: Графы, матроиды, алгоритмы: Асанов М.О., Баранский В.А., Расин В.В. Учебное пособие. 2-е изд.- Лань, 2010. - 368 c.

4. Алескеров Ф.Т. Бинарные отношения, графы и коллективные решения. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные - М., ГУ ВШЭ, 2006. - 300с.

Для студентов

1. Зыков А.А. Основы теории графов.- М.: Вузовская книга, 2004.

2. Maкоха А. Н. Дискретная математика: Учеб. пособие. Maкоха А. Н., Сахнюк П. А., Червяков Н. И - М.: ФИЗМАТЛИТ, 2005. - 368 с.

3. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. - СПб.: Питер, 2007. - 364 с.

Дополнительные источники:

Для преподавателей

1. Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. - М.: Новое знание, 2005. - 288 с.

2. Соболева Т.С. Дискретная математика: учебник для студ. вузов / Т. С.Соболева, А. В.Чечкин; под ред. А. В.Чечкина. - М.: Издательский центр «Академия», 2006. - 256 с.

3. Тишин В. В. Дискретная математика в примерах и задачах. - СПб.: БХВ-Петербург, 2008. - 352 с.

4. Виленкин Н. Я. Рассказы о множествах. 3-е издание. - М.: МЦНМО,2005. - 150 с.

Для студентов

1. Соболева Т.С. Дискретная математика: учебник для студ. вузов / Т. С.Соболева, А. В.Чечкин; под ред. А. В.Чечкина. - М.: Издательский центр «Академия», 2006. - 256 с.

2. Тишин В. В. Дискретная математика в примерах и задачах. - СПб.: БХВ-Петербург, 2008. - 352 с.

3. Виленкин Н. Я. Рассказы о множествах. 3-е издание. - М.: МЦНМО,2005. - 150 с.

4. Контроль и оценка результатов освоения УЧЕБНОЙ Дисциплины

Результаты обучения
(освоенные умения, усвоенные знания, опыт деятельности)

Формы и методы контроля и оценки результатов обучения

Базовая часть

Уметь:

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

Текущий промежуточный контроль в форме:

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

применять законы алгебры логики;

Текущий промежуточный в форме: защита лабораторных и практических работ;

решения задач.

определять типы графов и давать их характеристики;

Текущий промежуточный в форме: защита лабораторных и практических работ; решение задач.

строить простейшие автоматы

Текущий промежуточный в форме: защита лабораторных и практических работ;

решение задач.

Знать:

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

Текущий контроль: тестирование в форме: устный опрос; письменный опрос.

логические операции, формулы логики, законы алгебры логики;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

основные классы функций, полнота множества функций, теорема Поста;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

основные понятия теории множеств, теоретико- множественные операции и их связь с логическими операциями;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

логика предикатов, бинарные отношения и их виды;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

элементы теории отображений и алгебры подстановок;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

основные понятия теории графов, характеристики и виды графов;

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

элементы теории автоматов

Текущий контроль в форме: тестирование; устный опрос; письменный опрос; фронтальный опрос.

Вариативная часть - не предусмотрено

ПРИЛОЖЕНИЕ 1

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

ПК 1.1. Разрабатывать схемы цифровых устройств на основе интегральных схем разной степени интеграции.

Уметь:

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

Тематика лабораторных/практических работ

Автоматы и операции с ними

Графы и способы их задания

Деревья и остовы.

Эйлеровы графы

Пути и циклы в графах

Знать:

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

• логические операции, формулы логики, законы алгебры логики;

Перечень тем:

Тема 1.1. Языки описания цифровых автоматов.

Тема 1.2. Логические функции и алгебра предикатов.

Тема 1.3. Алгоритмы и их сложность.

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

Тема 1.5 Линейные коды.

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

Тематика самостоятельной работы:

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

Создание тематических кроссвордов.

Создание тестов.

Оформление наглядных пособий.

Построение контактных схем

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

Уметь:

- определять типы графов и давать их характеристики;

- строить простейшие автоматы;

Тематика лабораторных/практических работ

Автоматы и операции с ними

Графы и способы их задания

Деревья и остовы

Эйлеровы графы

Пути и циклы в графах

Знать:

- метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

• основные понятия теории графов, характеристики и виды графов;

- элементы теории автоматов

Перечень тем:

Тема 1.1. Языки описания цифровых автоматов.

Тема 1.2. Логические функции и алгебра предикатов.

Тема 1.3. Алгоритмы и их сложность.

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

Тема 1.5 Линейные коды.

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

Тематика самостоятельной работы:

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

Создание тематических кроссвордов.

Создание тестов.

Оформление наглядных пособий.

Построение контактных схем

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

Уметь:

- применять законы алгебры логики;

- определять типы графов и давать их характеристики;

Тематика лабораторных/практических работ

Автоматы и операции с ними

Графы и способы их задания

Деревья и остовы

Эйлеровы графы

Пути и циклы в графах

Многочлен Жегалкина

Функциональная полнота. Замкнутые классы.

Критерий Поста функциональной полноты.

Знать:

- логика предикатов, бинарные отношения и их виды;

- элементы теории отображений и алгебры подстановок;

- метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

Перечень тем:

Тема 1.1. Языки описания цифровых автоматов.

Тема 1.2. Логические функции и алгебра предикатов.

Тема 1.3. Алгоритмы и их сложность.

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

Тема 1.5 Линейные коды.

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

Тематика самостоятельной работы:

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

Создание тематических кроссвордов.

Создание тестов.

Оформление наглядных пособий.

Построение контактных схем

ПРИЛОЖЕНИЕ 2

ТЕХНОЛОГИИ ФОРМИРОВАНИЯ ОК

Название ОК

Технологии формирования ОК (на учебных занятиях)

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

Демонстрировать интерес к будущей профессии.

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

ОК 2. Организовывать собственную деятельность, определять методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.

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

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

ОК 3. Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.

Поиск самостоятельного решения возникающих проблем в ходе выполнения лабораторных работ.

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

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

Поиск необходимой информации для выполнения рефератов, подготовки сообщений.

ОК 5. Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности.

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

Поиск необходимой информации для подготовки сообщений, докладов в сети. Подготовка предложенных бланков документов, посредством прикладных программных средств.

ОК 6. Работать в коллективе и команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.

Работать в групповом обсуждении. Аргументировано принимать и отвергать идеи, высказывать свою точку зрения. Оказание взаимопомощи при выполнении заданий лабораторной работы.

ОК 7. Ставить цели, мотивировать деятельность подчиненных, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий.

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

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

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

ОК 9. Быть готовым к смене технологий в профессиональной деятельности.

Выполнение лабораторных работ на компьютерах различной комплектации.

ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).

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

ЛИСТ ИЗМЕНЕНИЙ И ДОПОЛНЕНИЙ, ВНЕСЕННЫХ В РАБОЧУЮ ПРОГРАММУ

№ изменения, дата внесения изменения; № страницы с изменением;

БЫЛО

СТАЛО

Основание:

Подпись лица внесшего изменения