Geum.ru

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

Вид материалаПрограмма

Содержание


Всего аудиторных занятий 72 часа
Обязательный минимум
Дополнительные требования ТПУ
1.2. Задачами изложения и изучения дисциплины
2.1. Теория множеств.
2.3. Математическая логика.
2.4. Теория алгоритмов.
3. Содержание практического раздела дисциплины
Подобный материал:

Министерство образования Российской Федерации

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

______________________________________________


УТВЕРЖДАЮ:

Декан факультета автоматики

и вычислительной техникиТПУ
_________Ю. С. Мельников


____________

(дата)


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




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

071900 "Информационные системы в бизнесе"


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


Обеспечивающая кафедра – автоматики и компьютерных систем (АиКС)


Курс 2

Семестр 3

Учебный план набора 1999 года


Распределение учебного времени


Лекции 36 часов (ауд,)

Практические (семинарские) занятия 36 часов (ауд,)

Курсовой проект в _______семестре нет часов

Курсовая работа в _______семестре нет часов

Всего аудиторных занятий 72 часа

Самостоятельная (внеаудиторная) работа 54 часа

Общая трудоемкость 126 часов

Зачет в 3 семестре

Зачет в _____________семестре

Дифзачет в ____________семестре

2000 г.


Предисловие


1 Рабочая программа составлена на основе ГОС ВПО для специальности "Информационные системы в бизнесе”, утвержденного ___________, и ОС ТПУ для специальности "Информационные системы в бизнесе", рассмотрена и одобрена на заседании обеспечивающей кафедры АиКС "___"______ 2000 г. протокол № _____ .


2. Разработчик

доцент кафедры АиКС АВТФ Барковский А.Н..


3. Зав. обеспечивающей

кафедрой АиКС АВТФ Цапко Г.П.


4 Рабочая программа СОГЛАСОВАНА с факультетом, СООТВЕТСТВУЕТ действующему плану.


АННОТАЦИЯ

Рабочая программа учебной дисциплины "Дискретная математика" предназначена для подготовки бакалавров ТПУ по специальности 071900 "Информационные системы в бизнесе".

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

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

Программа разработана доцентом кафедры АиКС АВТФ Барковским А.Н.


1. Цели и задачи учебной дисциплины

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

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

понимать:
  • общие принципы теоретико-множественного описания математических объектов;
  • сущность основных проблем теории графов;
  • методологию использования аппарата математической логики;
  • принципиальные методы решения основных задач теории алгоритмов;
  • что требуемые знания и умения студент реализует только в результате формирования у себя активной познавательной деятельности;

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

1.2. Задачами изложения и изучения дисциплины являются:
  • организация учебного процесса, обеспечивающего активизацию познавательной деятельности студента за счет выполнения заданий с элементами научно-технического творчества, по возможности исключающих инерцию мышления;
  1. Содержание теоретического раздела дисциплины (лекции)


Введение, основные понятия и определения. Цели и задачи курса

2.1. Теория множеств.

Множества и действия над ними. Соответствия, функции, отображения; отношения.

2.2. Графы.

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

2.3. Математическая логика.

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


2.4. Теория алгоритмов.

Интуитивное понятие алгоритма. Машины Тьюринга. Композиция машин Тьюринга. Примитивно -рекурсивные функции и примитивно-рекурсивные операторы Частично и обще-рекурсивные функции. Формулировка проблем теории алгоритмов.

3. Содержание практического раздела дисциплины


3.1. Множества и действия над ними. Отношение эквивалентности (4 часа).

3.2. Граф, мультиграф, псевдограф. Матрицы смежности и инциденций. (4 часа).

3.3. Маршруты, цепи, циклы (2 часа).

3.4. Эйлеровы цепи и циклы (2 часа).

3.5. Алгебра высказываний (2 часа).

3.6. Способы задания булевых функций (4 часа).

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

3.8. Машины Тьюринга и их композиция (4 часа).

3.9.Примитивно-рекурсивные, частично-рекурсивные и общерекурсивные функции (4 часа).


4. Программа самостоятельной познавательной деятельности

( 54 ч.)

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

Самостоятельная работа студента организована в двух формах:
  • аудиторной (на практических занятиях при решении индивидуальных задач (18 часов)4
  • внеаудиторной (проработка лекций, в том числе разделов, выделенных на самостоятельное изучение) (18 часов); подготовку к практическим занятиям (12 часов); выполнение индивидуальных заданий (6 часов).



  1. Текущий и итоговый контроль результатов изучения дисциплины
    1. В дисциплине используются следующие виды контроля
  • на каждом практическом занятии для оценки самостоятельной работы студента при подготовке к занятиям и контроль эффективности работы на занятиях;
  • проверка индивидуальных заданий.
  • По результатам проведенных контролей формируется допуск студента к итоговому контролю – зачету.
    1. Рейтинг-лист дисциплины.
      1. Виды учебной нагрузки:
  • лекции (36 часов) – Барковский Александр Николаевич;
  • практические занятия (36 часов) – Барковский Александр Николаевич.
      1. Основные положения по рейтингу дисциплины
        1. На дисциплину выделено 1000 баллов, которые распределены следующим образом:
  • на текущий контроль – 850 баллов;
  • на итоговый (зачет) – 150 баллов.
        1. Текущий контроль в семестре предполагает следующее распределение баллов:
  • контроль посещения лекций 18х10=180 баллов;
  • контроль работы на практических занятиях 18х30=540 баллов;
  • контроль выполнения индивидуальных заданий 130 баллов;
        1. Для получения зачета сумма баллов по всем видам контроля должна быть не менее 550 баллов при этом обязательно выполнение индивидуальных заданий и отработка тем практических занятий.
        2. Студентам, допустившим по результатам текущего контроля отставание в освоении учебной дисциплины для ликвидации задолженностей в течение семестра: при наличии уважительных причин (утверждается деканом) предоставляются дополнительные занятия или консультации; в случае неуважительной причины предлагается, согласно действующему в ТПУ "Положению", дополнительные платные образовательные услуги.
        3. Если по результатам текущей успеваемости студент набрал менее 45% от баллов текущего контроля, то есть меньше 390 баллов, то он не допускается к итоговому контролю – зачету.
        4. После двух неудовлетворительных оценок итогового контроля решается вопрос или об отчислении из университета, или переводе на коммерческое отделение.
    1. Образцы контролирующих материалов.
      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. Учебно-методическое обеспечение дисциплины
    1. Перечень рекомендуемой литературы

Основная
      1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988. - 480с.:ил.
      2. Шевелев Ю.П. Дискретная математика. В двух частях. Учебное пособие. – Томск: Изд.ТГУСУР, 1998. - 228с.: ил.
      3. Основы кибернетики. Под ред. К.А. Пупкова. Учеб. пособие для втузов. - М.: Высшая школа, 1984.- 413с.:ил.
      4. Корниенко А.В. Дискретная математика. Учебное пособие. - Томск.: Изд. ТПУ, 1996. - 96с.: ил.

Дополнительная
      1. Горбатов В.А. Основы дискретной математики. Учеб. пособие. - М.: Высшая школа, 1986. – 311с.: ил.
      2. Коршунов Ю.М. Математические основы кибернетики. 2-е изд. - М.: Энергия, 1980. – 424с.: ил.
      3. Сборник задач по дискретной математике. – М.: Наука, 1977. - 368с.: ил.