МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

«Кемеровский государственный университет»

в г. Анжеро-Судженске

«1» марта 2013 г.

РАБОЧАЯ ПРОГРАММА

по дисциплине «Дискретная математика» (ФТД.1) для специальности 080801.65 «Прикладная информатика в экономике»

факультет информатики, экономики и математики курс: 1 семестр: 1 зачет: 1 семестр лекции: 36 часов самостоятельная работа: 34 часов всего часов: 70 Составитель: канд. физ.-мат. наук, доцент кафедры математики Токарева Е.Г.

Анжеро-Судженск Рабочая программа составлена на основании:

«ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ» (2000г.) Рабочая программа обсуждена На заседании кафедры математики Протокол №6 «31» января 2013г.

Зав. кафедрой_ Якупов Р.Т.

(Ф.И.О., подпись) Одобрено методической комиссией Протокол №8 «26» февраля 2013г.

Председатель Якупов Р.Т.

(Ф.И.О., подпись) 1. Пояснительная записка Актуальность и значимость учебной дисциплины. Курс «Дискретная математика»

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

Рабочая программа составлена на основании Учебного плана специальности 080801- «Прикладная информатика» (по областям) и соответствует Государственному образовательному стандарту высшего профессионального образования.

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

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

Место дисциплины в профессиональной подготовке специалиста. Курс опирается на школьный курс алгебры и математического анализа, связан с такими разделами математики, как уравнения и неравенства и их решениями. Изучив раздел «Основы дискретной математики» студенты смогут на предварительном этапе так подготовить задачу, чтобы свести к минимуму как, время решения задачи, так и объем используемой оперативной памяти ЭВМ.

Структура учебной дисциплины. Программа курса состоит из следующих разделов: Множества и операции над ними. Декартово произведение множеств. Бинарные соответствия и операции над ними. Упорядоченные множества. Метод математической индукции. Отображения. Отношение эквивалентности. Правило суммы и произведения.

Перестановки без повторений. Перестановки с повторениями. Размещения без повторений и с повторениями. Сочетания. Бином Ньютона, его свойства. Треугольник Паскаля.

Высказывания и логические операции над ними. Формулы и их виды. Логические равносильности. Приведенные формулы. Системы логических связок. Полные системы операций. Нормальные формы. Совершенные нормальные формы. Тавтология и логические следования. Понятие формальной системы. Исчисление высказываний.

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

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

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

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

Объем и сроки изучения дисциплины Курс «Дискретная математика» предназначен для студентов дневной формы обучения факультета информатики, экономики и математики специальности 080801- «Прикладная информатика» (по областям). Практические занятия проводятся в 1 семестре в объеме часов, лекций по предмету не запланировано. По каждой теме предусмотрены вопросы для самостоятельного изучения, общий объем самостоятельной работы 36 часов. Всего:

72 часа.

Вид контроля знаний студентов и их отчетности Система контрольных мероприятий по дисциплине «Элементарная математика»

включает в себя:

– опрос студентов;

- домашние задания;

– самостоятельные и контрольные работы;

Критерии оценки знаний студентов По итогам изучения дисциплины проводится зачет.

Для успешной сдачи зачета студенты должны освоить материал курса в соответствии с его программой, выполнить и сдать на проверку все домашние, контрольные и индивидуальные работы. При выставлении зачета учитывается работа студента в течение семестра (как на аудиторных занятиях, так и самостоятельно). Студент допущен к зачету только при наличии всех домашних, контрольных и индивидуальных работ, выполненных на положительную оценку. Билет на зачете содержит теоретический вопрос и 2 практических задания из разных разделов курса. Оценка «зачтено» ставится за правильно решенное 1 практическое задание и частичный ответ на теоретический вопрос или за 2 верно выполненных практических задания

2. ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

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

Декартово произведение множеств.

Отображения.

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

математической индукции.

произведения.

Перестановки без повторений.

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

Сочетания.

Паскаля.

Высказывания и логические операции Приведенные формулы.

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

нормальные формы.

Тавтология и логические следования.

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Множества и операции над ними. Декартово произведение множеств. Бинарные соответствия и операции над ними.

Отображения. Отношение эквивалентности.

Упорядоченные множества. Метод математической индукции.

Правило суммы и произведения.

Перестановки без повторений. Перестановки с повторениями.

Размещения без повторений и с повторениями. Сочетания.

Бином Ньютона, его свойства. Треугольник Паскаля.

Высказывания и логические операции над ними.

Формулы и их виды. Логические равносильности. Приведенные формулы. Системы логических связок. Полные системы операций. Нормальные формы. Совершенные нормальные формы. Тавтология и логические следования Понятие формальной системы. Исчисление высказываний.

Доказательства и теоремы. Связь между Алгеброй высказываний и Исчислением высказываний.

Непротиворечивость, разрешимость и независимость Исчисления высказываний.

Основные понятия алгебры предикатов. Логические операции над предикатами.

Кванторные операции над предикатами.

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

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

1. Мальцев И. А. Дискретная математика: Учебное пособие. 2 е изд., испр. — СПб.:

Издательство «Лань», 2011. — 304 с.: ил. — (Учебники для вузов. Специальная http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 2. Редькин Н. П. Дискретная математика. — М.: ФИЗ МАТЛИТ, 2009. — 264 с. Режим доступа: http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 3. Куликов В.В. Дискретная математика : учеб. пособие / В.В. Куликов. - М.: РИОР, 2010.

- 174 с.

1. Алгоритмы теории графов: Методические указания к практическим и индивидуальным занятиям/ С.Ю. Белецкая, Л.Д. Кретова, Н.Б. Ускова. Воронеж: ВГТУ, 2000.

2. Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966.

3. Виленкин Н.Я. Комбинаторика. М.:Наука, 1969.

4. Вересова Е.Е., Денисова Н.С., Полякова Т.Н. Практикум по решению математических задач. - М.: Просвещение, 1979.

5. Гусев В.А., Литвиненко В.Н., Мордкович А.Г. Практикум по решению математических задач. – М.: Просвещение, 1999.

6. Ивлев Ю.В. Логика. Изд-во 2-е. М.: Логос, 1998.

7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.:

Энергоатомиздат, 1988.

8. Куликов Л.Я. Алгебра и теория чисел. М.: Высшая школа, 1979.

9. Леденева Т.М. Специальные главы математики. Дискретная математика: Учебное пособие. Воронеж. Гос. техн. унив-т, Воронеж, 1997.

10. Кузнецов О.П. Дискретная математика для инженера. - 5-е изд., стереотип. - СПб.:

Лань, 2007. - 396 с.

11. Шапорев С.Д. Дискретная математика: курс лекций и практ. занятий : учеб. пособие / С.Д. Шапорев. - СПб.: БХВ- Петербург, 2009. - 396 с.

12. Галушкина Ю.И. Конспект лекций по дискретной математике: с упражнениями и контрольными работами / Ю.И. Галушкина, А.Н. Марьямов. - 2-е изд. - М.: Айрис-пресс, 2008. - 175 с.

13. Москинова Г.И. Дискретная математика: математика для менеджера в примерах и упражнениях : учеб. пособие / Г.И. Москинова; [Кафедра менеджмента Моск. гос. ун-та коммерции]. - М.: Логос, 2007. - 239 с.

14. Нефедов В.Н. Курс дискретной математики: Учебное пособие, М.: Изд-во МАИ, 1992.

15. Стол Р.Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968.

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

17. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.

18. Кофман А. Введение в прикладную комбинаторику. М.: Радио и связь, 1982.

19. Потапенко А.А. Элементы алгебры логики. Учебное пособие- Л.: СЗПИ, 1977.

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

5. ФОРМЫ ТЕКУЩЕГО, ПРОМЕЖУТОЧНОГО И ИТОГОВОГО КОНТРОЛЯ

Текущий контроль осуществляется в формах:

– опрос студентов;

– домашние работы;

– самостоятельная работа студентов.

Промежуточный контроль:

– коллоквиумы;

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

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

1. Множество. Способы задания множеств.

2. Понятие подмножества. Равные множества.

3. Объединение, пересечение, разность множеств.

4. Теорема о свойствах операций над множествах.

5. Декартово произведение множеств. Упорядоченная пара.

6. Теорема о свойствах декартова произведения множеств.

7. Бинарные соответствия. Область определения и множество значений бинарного соответствия.

8. Обратные соответствия и их свойства.

9. Свойства произведений бинарных соответствий.

10. Отображение. Инъективное и сюръективное отображение.

11. Бинарные отношения.

Антирефлексивность.

Антисимметричность и асимметричность.

14. Транзитивное бинарное отношение. Признак транзитивности.

15. Связное бинарное отношение. Признак связности.

16. Отношение эквивалентности. Теорема о свойствах классов эквивалентности.

17. Понятие разбиения множества. Фактор- множество. Теорема о фактор- множестве.

18. Теорема о методе математической индукции.

19. Правило суммы и произведения. Перестановки без повторений и с повторениями.

20. Размещения с повторениями и без повторений. Сочетания.

21. Схема для решения комбинаторных задач.

22. Треугольник Паскаля. Бином Ньютона.

23. Свойства Бинома Ньютона.

24. Высказывания. Истинность и ложность высказывания.

25. Конъюнкция. Таблица истинности.

26. Дизъюнкция. Таблица истинности.

27. Импликация и эквиваленция. Таблицы истинности.

28. Понятие формулы в алгебре высказываний. Подформула.

29. Выполнимая формула.

30. Опровержимая формула.

31. Противоречивая формула.

32. Тавтология.

33. Понятие равносильности. Теорема об основных равносильностях.

34. Приведенная формула.

35. Понятие системы логических связок.

36. Полная система операций. Теорема о полных системах операций.

37. Нормальные формы (формулы).

38. Конъюнктивная и дизъюнктивная формула.

39. Критерий тождественно-истинной формулы.

40. Теорема о КИФ.

41. Теорема о ДНФ.

42. Критерий тождественно-ложной формулы.

43. Совершенная конъюнктивная совершенная форма. Теорема о СКИФ.

44. Теорема о СДНФ.

45. Правило приведения формулы к СДНФ, 46. Правило приведения формулы к СКНФ.

47. Тавтология. Признак тавтологии.

48. Признак формул.

49. Признак логического следования.

50. Понятие формальной системы.

51. Исчисление высказываний. Синтаксис и аксиоматика исчисления.

52. Правило вывода.

53. Теорема и ее доказательство.

54. Связь между АВ и ИВ.

55. Непротиворечивость, независимость и разрешимость ИВ.

56. Понятие предиката. Его виды.

57. Множество истинности предиката.

58. Логические операции над предикатами.

59. Кванторные операции над предикатами.

60. Понятии графа, его виды.

II. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Советы по планированию и организации времени, необходимого для изучении дисциплины.

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

Изучение теоретического материала по учебнику -1 час в неделю.

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

Самостоятельное решение заданий дома – 2 часа в неделю.

Тогда общие затраты времени на освоение курса Дискретной математики составят около 4 часа в неделю.

2. Описание последовательности действий студента. При изучении данной дисциплины следует внимательно слушать и записывать решение заданий в тетрадь.

Для наилучшего усвоения дисциплины рекомендуется следующая последовательность действий:

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

2.2. В течение недели выбрать время для работы с необходимой литературой в библиотеке.

2.3. При подготовке к практическому занятию повторить основные понятия и формулы по теме домашнего задания, изучить примеры. Решая задание, предварительно понять, какой теоретический материал нужно использовать, наметить план решения, попытаться на его основе решить 1-2 аналогичных задания.

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

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

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

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

При подготовке к практическим и лекционным занятиям необходимо повторять ранее изученный материал. Обычно придерживаются следующей схемы: изучение материала лекции по конспекту в тот же день, когда была прослушана лекция (10- минут); повторение материала накануне следующей лекции (10-15 минут), проработка учебного материала по конспектам лекций, учебной и научной литературе, подготовка ответов на вопросы, предназначенных для самостоятельного изучения (1 час неделю), подготовка к практическому занятию, решение задач (1 час). Важно добиться понимания изучаемого материала, а не механического его запоминания. При затруднении изучения отдельных тем, вопросов, следует обращаться за консультациями к лектору или преподавателю, ведущему практические занятия.

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

5. Советы по подготовке к зачету. При подготовке к зачету нужно освоить теорию:

разобрать определения всех понятий, рассмотреть примеры и самостоятельно решить несколько типовых заданий по каждой теме. При решении задач всегда необходимо комментировать свои действия и не забывать о содержательной интерпретации Итоговой формой контроля является зачёт. Студент может получить зачёт по результатам текущей работы в течение семестра, если выполнены все индивидуальные задания, получены положительные оценки по всем коллоквиумам. В случае отрицательной характеристики такой работы зачёт проводится в экзаменационной форме: студенту предлагается ответить на вопросы билета (по каждому из разделов). В этом случае зачет выставляется при удовлетворительном ответе.

Изменения и дополнения, вносимые в рабочую программу по итогам ее ежегодного рассмотрения на кафедре и переутверждения в установленном порядке, указываются в специальном Приложении 2, составленном согласно форме:

Дополнения и изменения к рабочей программе учебной дисциплины Сведения о переутверждении РП на текущий учебный год и