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

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




Скачати 135.9 Kb.
НазваПрактикум на эвм, базы данных. Компетенции обучающегося, формируемые в результате освоения дисциплины
Дата конвертації28.12.2012
Розмір135.9 Kb.
ТипПрактикум


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


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

Факультет прикладной математики и кибернетики


УТВЕРЖДАЮ


Декан ФПМК А.М.Горцев


" 1 " марта 2011 г.


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


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


Направление подготовки

080100 Экономика

Профиль: Математические методы в экономике


Квалификация выпускника

Бакалавр


Форма обучения

очная


Томск

2011

^ 1. Цели освоения дисциплины:


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


^ 2. Место дисциплины в структуре ООП бакалавриата


Дисциплина вариативной части математического цикла Б.2. для студентов 1-го года обучения, читается во 2-м семестре.

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

Данная дисциплина необходима для изучения следующих дисциплин: основы информатики, пакты прикладных программ, практикум на ЭВМ, базы данных.


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


Владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК–1); способен логически верно, аргументировано и ясно строить устную и письменную речь (ОК-6); способен выбрать инструментальные средства для обработки экономических данных в соответствии с поставленной задачей, проанализировать результаты расчетов и обосновать полученные выводы (ПК-5); способен на основе описания экономических процессов и явлений строить стандартные теоретические и эконометрические модели, анализировать и содержательно интерпретировать полученные результаты (ПК-6).


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

• Знать: основные понятия дискретной математики, основные алгоритмы.

• Уметь: использовать полученные знания при решении практических задач.

• Владеть: математическим аппаратом дискретной математики.


^ 4. Структура и содержание дисциплины


Общая трудоемкость дисциплины составляет 2,6 зачетных единицы, 93часа.


4.1. Распределение часов курса по темам и видам работ



№№

п/п

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

Семестр

Неделя семестра

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

(в часах)

Формы текущего контроля успеваемости

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

Лекции

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

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

1.

Функции алгебры логики

2

1

2

2

2

Тест

2.

Принцип двойственности


2

2

2

2

2

Тест

3.

Полнота и замкнутость

2

3-4

4

2

4

Тест

4.

Исчисление высказываний

2

5-6

4

2

4

Тест

5.

Исчисление предикатов

2

7,8

4

2

2

Тест

6.

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

2

9

2

2

2

Тест

7.

Типы графов, раскраска вершин графов

2

10-14

10

4

8

Тест

8.

Сети

2

15

2

2

2

Тест, зачет




ИТОГО:







30

14

20

29



^ 4.2. Перечень разделов курса


Тема 1. Функции алгебры логики (Булевы функции). Табличное представление. Число функций от n переменных. Элементарные функции. Индуктивное определение формулы над множеством булевых функций. Формулы над множеством элементарных функций. Соседние наборы. Существенные и фиктивные переменные. Добавление и исключение фиктивных переменных. Равенство функций и эквивалентность формул. Основные тождества алгебры логики. Операции поглощения и склеивания.

Тема 2. Принцип двойственности. Теорема о двойственной функции. Разложение функции по подмножеству переменных. Теорема о разложении по m переменным. Частные случаи разложения по одной и всем переменным. Вывод формул СДНФ и СКНФ.

Тема 3. Полнота и замкнутость. Определение полной системы. Теорема о полной системе. Примеры полных систем. Определение замыкания. Свойства замыканий. Определение полной системы через замыкание. Определение замкнутого класса. Свойства замкнутых классов, сохраняющих константы. Замкнутый класс самодвойственных функций и его свойства. Сравнимые наборы. Замкнутый класс монотонных функций и его свойства. Полином Жегалкина. Теорема о единственности полинома для функции. Линейный полином. Замкнутый класс линейных функций и его свойства. Теорема о необходимых и достаточных условиях полноты систем булевых функций. Теорема о числе функций полных систем.

Тема 4. Исчисление высказываний. Алфавит, синтаксис и семантика исчисления высказываний. Проблема вывода. Дерево частичных интерпретаций и его построение. Анализ КНФ на невыполнимость методом частичного обхода Free BDD-графа и резольвентным методом. Связь метода Блейка и резольвентного метода.

Тема 5. Исчисление предикатов. Алфавит, синтаксис и семантика исчисления предикатов. Предваренная нормальная форма. Проблема вывода. Хорновские дизъюнкты.

Тема 6. Основные понятия теории графов. Определения простого, общего, ориентированного графов. Смежность вершин и ребер. Степень вершины. Лемма о рукопожатиях и ее следствие. Матрицы смежности и инциденций. Связность графов. Операции объединения и соединения графов. Простейшие типы графов. Пустой и полный графы. Регулярные графы. Двудольные графы. Полные двудольные графы. Циклические графы. Колесо. Реберный граф.

Тема 7. Маршрут, цепь, простая цепь, цикл. Определение связности графов с использованием понятия простой цепи. Диаметр и обхват графа. Радиус и центры графа. Разделяющее множество, разрез, мост. Лемма о существовании цикла в графе. Определение Эйлерова графа, примеры. Теорема о необходимых и достаточных условиях графа быть Эйлеровым. Алгоритм Флери построения Эйлерового цикла. Ормаршрут, орцепь, простая орцепь, орцикл. Эйлеров орграф. Необходимые и достаточные условия орграфа быть Эйлеровым. Гамильтоновы графы. Теорема Дирака. Деревья и их свойства. Остовное дерево. Циклический ранг графа. Алгоритм Краскала. Плоские и планарные графы. Примеры непланарных графов. Гомеоморфные графы. Операция стягивания вершин в графе. Две теоремы о необходимых и достаточных условиях непланарности графов. Толщина графа. Теорема об укладке графа в трехмерном пространстве. Жорданова кривая. Определение грани плоского графа. Теорема Эйлера о соотношении вершин, ребер и граней в плоском графе. Обобщение теоремы на несвязные графы. Теорем о числе ребер в плоском графе. Теорема о степени вершины в плоском графе. Двойственные графы. Теорема. Раскраска вершин графов. Правильная раскраска. Хроматическое число. Хроматические числа для простейших типов графов. Теоремы о раскраске произвольного графа. Теорема о раскраске плоского графа в 6 цветов. Теорема о 5 красках. Алгоритм минимальной раскраски. Понятие соцветного подмножества. Поиск всех максимальных соцветных подмножеств. Сведение задачи нахождения хроматического числа к покрытию столбцов булевой матрицы. Построение всех безызбыточных покрытий. Определение кратчайшего покрытия.

Тема 8. Сети. Определение сети. Изоморфизм сетей. Исток и сток в сети. Последовательное и параллельное соединение сетей. Алгоритм Дейкстры. Потоки в сетях. Определение потока. Величина потока. Сечение и простое сечение. Пропускная способность простого сечения. Теорема Форда-Фалкерсона. Алгоритм Форда-Фалкерсона поиска максимального потока в сети.


^ 4.3. Лабораторный практикум на ЭВМ


Лабораторный практикум не предусмотрен.


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


Тема 1. Булевы функции. Существенные и фиктивные переменные.

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

Тема 2. СДНФ и СКНФ. Двойственные функции. Полином Жегалкина.

Тема 3. Полнота и замкнутость систем булевых функций.

Тема 4. Исчисление высказываний.

Тема 5. Исчисление предикатов.

Тема 6.Определения и основные понятия теории графов.

Тема 7. Цепи и циклы. Эйлеровы и Гамильтоновы графы. Деревья. Планарные графы. Раскрашивание графов.

Тема8. Нахождение максимального потока в сети.


^ 4.5. Курсовой проект (курсовая работа)


Курсовой проект не предусмотрен.


5. Образовательные технологии


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


6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины


Все необходимое учебно-методическое обеспечение по дисциплине представлено в печатном или электронном виде в библиотеке ТГУ, а также в электронном виде в сети Интернет на сайте кафедры программирования или ИДО ТГУ.

В качестве текущего контроля успеваемости в конце каждой темы проводиться тестирование по материалам темы. В середине семестра (8 неделя) и в конце семестра (14 неделя) проводятся письменные контрольные работы. В конце второго семестра сдается экзамен.


^ 6.1. Примерный перечень вопросов к зачету во втором семестре:


  1. Определение булевой функции табличное задание, число функций от n переменных. Элементарные функции. Существенные переменные. Равенство функций.

  2. Понятие формулы, эквивалентные формулы. Основные тождества алгебры логики.

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

  4. Определение полной системы, примеры полных систем. Теорема о полных системах.

  5. Замыкание. Свойство замыканий. Замкнутые классы. Свойства классов T0, T1.

  6. Класс самодвойственных функций и его свойство.

  7. Класс монотонных функций, его замкнутость.

  8. Лемма о немонотонной функции.

  9. Полином Жегалкина. Теорема о единственности полинома.

  10. Класс линей ных функций и его замкнутость

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

  12. Теорема о числе функций полных систем.

  13. Алфавит исчисления высказываний

  14. Синтаксис исчисления высказываний

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

  16. Общезначимые, невыполнимые и нейтральные формулы.

  17. Полная и частичная интерпретация. Модель. Дерево интерпретаций.

  18. Проблема вывода. Ее сведение к анализу КНФ на невыполнимость.

  19. Анализ КНФ на невыполнимость методом сокращенного обхода Free BDD графа.

  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. Теорема о раскраске произвольного графа. Теорема о раскраске планарного графа в 6 цветов.

  46. Теорема о 5 красках.

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

  48. Сети. Изоморфизм сетей. Параллельно-последовательные сети.

  49. Алгоритм Дейкстры.

  50. Определение потока в сети. Простое сечение и величина его потока. Теорема Форда, Фалкерсона.

  51. Алгоритм нахождения максимального потока в сети.



^ 7. Учебно-методическое и информационное обеспечение дисциплины


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

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

3. Новиков Ф.А. Дискретная математика для программистов. -СПБ:Питер, 2000.-304.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. -М: Наука, 1977. -268 с.

5. Останин С.А. Матросова А.Ю. Функции алгебры логики (учебное пособие). Из-во ТГУ. -2004. – 36с.

6. Останин С.А. Элементы теории графов (учебное пособие). Из-во ТГУ. -2005. – 38с.

7. С.А.Останин, А.Ю. Матросова, Дискретная математика. Методические указания для педагогов. 2007 (http://ido.tsu.ru/iop_res1/testirovaniepo/)


б) Дополнительная литература:

  1. Судоплатов С.В, Овчинникова Е.В.Элементы дискретной математики. Москва ИНФРА-М, Новосибирск, НГТУ, 2002.



в) Перечень иных информационных источников:

  1. R.Murgai, R.Brayton, A.Sangiovani-Vincetelli. Logic Synthesis for Field Programmable Gate Arrays. Cluver Academic Publisher,1995,425 p.


^ 8. Материально-техническое обеспечение дисциплины


8.1. Требования к аудиториям (помещениям, местам) для проведения занятий

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


^ 8.2. Требования к специализированному оборудованию

Специализированное оборудование не требуется.


8.3. Требования к специализированному программному обеспечению

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


Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки 080100 Экономика


Автор: д.т.н., профессор А.Ю. Матросова.

Рецензент: к.т.н., доцент С.А. Останин.


Программа одобрена на заседании Ученого совета ФПМК

от «24» февраля 2011 г., протокол № 282.




Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації