В. О. Леонтьєв програма дисципліни icon

В. О. Леонтьєв програма дисципліни




Скачати 87.23 Kb.
НазваВ. О. Леонтьєв програма дисципліни
Дата30.06.2012
Розмір87.23 Kb.
ТипДокументи

Міністерство освіти і науки України

Вінницький національний технічний університет
Інститут автоматики, електроніки та комп’ютерних систем управління
Факультет автоматики та комп’ютерних систем управління

ЗАТВЕРДЖЕНО

Вченою радою ВНТУ

Протокол № _________

від "____" __________________ 2006 р.

Проректор з навчальної та

науково-методичної роботи


В.О. Леонтьєв


ПРОГРАМА ДИСЦИПЛІНИ

Основи дискретної математики”


Напрям підготовки ^ 0914 – “Системи управління і автоматика”

Освітньо-кваліфікаційний рівень – бакалавр

6.091401 – “Комп`ютеризовані системи автоматики та управління"


Автор ___________ Штовба С.Д., доцент кафедри комп’ютерних систем управління.

Розглянуто і схвалено на засіданні кафедри комп’ютерних систем управління, протокол № ___ від "___" __________  2006 р.
Завідувач кафедри КСУ _______________________ Дубовой В.М.

Програма прорецензована доцентом кафедри ______________________________
та схвалена на засіданні кафедри __________, протокол № _____ від "___" __________ 2006 р.
Завідувач кафедри _____________________________

Програма розглянута та схвалена на засіданні Методичної комісії Інституту автоматики, електроніки та комп’ютерних систем управління, протокол № ___ від "___" __________ 2006 р.

Голова Методичної комісії ІнАЕКСУ ____________________ Васюра А.С.

Розглянуто і схвалено на засіданні Вченої ради ІнАЕКСУ, протокол № ___ від "   " __________ 2006 р.

Голова Вченої ради ІнАЕКСУ _________________________ Васюра А.С.

Розглянуто і схвалено на засіданні Методичної ради ВНТУ, протокол №____ від “___” ____________ 2006 р.
Голова Методичної ради _____________________________ Леонтьєв В.О.

Дисципліна “Основи дискретної математики”





Стац. нав.

Заоч. нав.

Курс

2

2

Триместр

5

3

Лекції (год.)

32

8

Лабораторні роботи (год.)

24

8

Практичні заняття (год.)

 

 

Семінари (год.)

 

 

Курсовий проект або КР (триместр / год. /кредитів)

 

 

РГР (триместр / СРС год. )





Контрольні роботи на які виділяється навантаження
(триместр, кільк., год.),

 

 

СРС (год.)

52

92

ВСЬОГО (год. / кредитів)

108 / 3

108 / 3

Підсумковий модульний контроль / кредити

М1 / 1.5

М2 / 1.5



Підсумковий триместровий контроль

Іспит

Іспит


1. Мета та задачі дисципліни

Дисципліна “Основи дискретної математики” надає студентам базові теоретичні знання та сприяє набуттю практичних навичок із теорії множин, теорії алгоритмів, формальних систем, графів та дискретних екстремальних задач, які необхідних для розуміння студентами місця та ролі дискретної математики в майбутній фаховій діяльності.

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


^ 1.1 Зв’язок з іншими дисциплінами

При вивченні дисципліни студентам знадобляться знання з “Вищої математики” та “Алгоритмічних мов та програмування”. Отримані знання використовуватимуться при вивченні дисциплін “Методи оптимізації”, “Дослідження операцій”, “Теорія автоматичного управління”, “Теорія інформації та кодування”, “Автоматизовані системи управління технологічними процесами”, “Штучний інтелект та розпізнавання образів” в дипломному проектуванні та при підготовці магістрів.


^ 1.2 Завдання вивчення дисципліни

В результаті вивчення дисципліни студенти знатимуть:

  • місце і роль дискретної математики в сучасній фаховій діяльності інженерів-електриків;

  • термінологію дискретної математики;

  • основи теорії алгоритмів;

  • базові понятті теорії графів;

  • популярні задачі дискретної оптимізації.

На основі набутих знань студенти вмітимуть:

  • застосовувати апарат дискретної математики розв’язанні практичних задач.
2. Зміст дисципліни


Вступ

Мета і задача курсу. Структура дисципліни. Неперервність та дискретність математики. Історичні передумови сучасної дискретної математики. Видатні науковці. Місце і роль дискретної математики в інженерній діяльності. Книжки, журнали та інтернет-ресурси з дискретної математики. Електроні бази даних статей та підручників з дискретної математики.

^ Множини та операції над ними

Множини та підмножини. Потужність множини. Способи завдання множин. Теоретико-множини операції: об’єднання, перетин, доповнення. Добуток множин. Характеристична функція. Алгебра множин.

^ Нечіткі множини.

Визначення нечіткої множини. Ступінь належності. Функція належності. Зв’язок функції належності та характеристичної функції. Теоретико-множини операції об’єднання, перетину та доповнення над нечіткими множинами. Синглтоні нечіткі множини.

^ Відображення і функції

Відображення. Образ. Прообраз. Функціональне відображення. Функції. Багатомісні функції. Способи завдання функцій. 13-та проблема Гільберта.

Відношення

Визначення. Способи завдання відношень. Бінарне відношення. Приклади. Властивості відношень: рефлексивність, симетричність, транзитивність. Операції над відношеннями: об’єднання, перетин, доповнення, композиція, транзитивне замикання. Відношення еквівалентності. Відношення порядку.

^ Основи теорії графів

Поняття графу. Основні терміни і визначення. Неорієнтовані і орієнтовані графи. графи. Поняття вершин, ребер і дуг графа. Суміжні вершини і ребра. Графічне і матричне представлення графів. Матриця суміжності і матриці інцидентності. Представлення відображення графом.

^ Основи теорії алгоритмів

Основні поняття і властивості алгоритмів. Основні вимоги до алгоритмів. Формалізація алгоритму рекурсивними функціями та машиною Тюрінга. Операції над машиною Тюрінга.

^ Основи теорії формальних систем

Визначення формальної системи. Вимоги до формальних систем: інтерпретуємість, несуперечність, повнота, аксіоматизуємість. Принципи побудови формальних систем. Формальні граматики. Контексно-вільна граматика.

^ Складність алгоритмів

Поняття складності алгоритму. Етапи визначення складності алгоритму: точний опис алгоритму; визначення розмірності задачі; визначення кількості операцій. Класифікація алгоритмів за складністю: P- та NP-алгоритми. Розрахунок складності алгоритмів сортування.
^

Задача про Кенігсбергські мости


Обходи графа. Маршрути, ланцюги, шляхи і цикли. Властивості зв'язних графів. Вершинна і реброва зв'язність. Дерева. Ліси. Цикли і дерева. Остов дерева. Властивості дерев. Задача про Кенігсбергські мости. Ейлерові та гамільтонові цикли. Алгоритми знаходження ейлерового циклу.
^

Задача про найкоротший шлях на орієнтованому графі


Орієнтовані графи. Орієнтовані маршрути, ланцюги, шляхи і цикли. Способи завдання орієнтованих графів. Знаходження найкоротшого шляху на графі: постановка задачі, алгоритм розв’язання, приклад.

^ Задача про розфарбування графу

Розбиття вершин графу на класи. Помічені вершини. Задача розфарбування вершин графу. Проблема чотирьох фарб.

Задача про комівояжера

Змістовна та формалізована постановки задачі. Розв’язання задачі методом динамічного програмування. Приклад. Бібліотека тестових задач TSPLIB. Експериментальні дослідження часу розв’язання тестових задач TSPLIB.

^ Популярні екстремальні задачі дискретної оптимізації

Задача маршрутизації вантажівок. Квадратична задача про призначення. Задача про рюкзак. Задача про мінімальне остовне дерева. Задача про максимальний потік. Складність задач. Огляд евристичних алгоритмів їх розв’язання. Розв’язання означених задач методом гілок та меж.

^ Мурашині алгоритми розв’язання задач дискретної оптимізації

Основні принципи функціонування колонії мурах: додатній та від’ємний зворотній зв’язки, випадковість та багатократність дій. Стигмержі та феромони. Мурашиний алгоритм оптимізації маршруту комівояжера. Алгоритм мурашиної колонії. Порівняння з іншими метаевристичними алгоритмами оптимізації.
3. Практичні заняття

^ Множини та операції над ними

Множини та підмножини. Потужність множини. Характеристична функція Теоретико-множини операції: об’єднання, перетин, доповнення.

^ Нечіткі множини.

Представлення невизначеної інформації нечіткими множинами. Параметричні функції належності. Теоретико-множини операції об’єднання, перетину та доповнення над нечіткими множинами.

Відношення

Бінарне відношення. Перевірка рефлексивності, симетричності, транзитивності відношення. Операції над відношеннями: об’єднання, перетин, доповнення, композиція, транзитивне замикання.

^ Основи теорії графів

Неорієнтовані і орієнтовані графи. графи. Знаходження суміжних вершин і ребер графу. Графічне і матричне представлення графів. Матриця суміжності і матриця інцидентності.

^ Основи теорії алгоритмів

Перевірка основних властивостей алгоритмів. Запис алгоритма блок-схемою та псевдокодом. Формалізація алгоритму машиною Тюрінга.

^ Формальні граматики

Розробка формальної породжувальної граматики: алфавіту термінальних символів; алфавіту нетермінальних символів; аксіом; множини правил виведення.

^ Складність алгоритмів

Визначення складності алгоритмів з невеликою кількістю операторів та логічних умов. Класифікація алгоритмів за складністю: P- та NP-алгоритми. Профілювання програм.
^

Задача про Кенігсбергські мости


Знаходження маршрутів, ланцюгів, шляхів і циклів графу. Розв’язання задачі про Кенігсбергські мости: постановка задачі; алгоритм; контрольний приклад.

^ Задача про розфарбування графу

Розбиття вершин графу на класи. Розв’язання задачі розфарбування вершин графу: постановка задачі; алгоритм; контрольний приклад. Проблема чотирьох фарб.

^ Задача про комівояжера

Розв’язання задачі про комівояжера різними методами Порівняння складності алгоритмів розв’язання задачі про комівояжера

^ Задача про рюкзак

Змістовна та формалізована постановки задачі. Алгоритм розв’язання. Контрольний приклад. Розрахунок складності алгоритму.

Квадратична задача про призначення

Змістовна та формалізована постановки задачі. Алгоритм розв’язання. Контрольний приклад. Розрахунок складності алгоритму.
4. Література
Основна література

  1. Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища школа, 2002. – 287с.

  2. Глушков В.М. Введение в АСУ. К.: Техніка – 1974.

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

  4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. – 512 с.

  5. Biggs N. L. Discrete Mathematics. – Oxford: Oxford University Press, 2nd eds., 2002. – 425p.


Додаткова література

  1. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир, 1976. – 165 с.

  2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергия, 1972.

  3. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001.

  4. Ротштейн А.П. Интеллектуальные технологии идентификации: нечеткая логика, генетические алгоритмы, нейронные сети. – Винница: УНІВЕРСУМ–Вінниця, 1999. – 320 с.

  5. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Радио и связь.- 1981.- 286с.

  6. Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. – 2005. – №4.– C. 1–16.

  7. Zimmerman H.-J. Fuzzy Sets Theory and Its Applications.3rd ed. – Kluwer Academic Publisher, 1996. – 435 p.

Схожі:

В. О. Леонтьєв програма дисципліни iconВ. О. Леонтьєв програма дисципліни
Розглянуто І схвалено на засіданні кафедри комп’ютерних систем управління, протокол № від " "    2006 р
В. О. Леонтьєв програма дисципліни iconВ. О. Леонтьєв Навчальна програма дисципліни
Метою вивчення дисципліни є теоретична та практична підготовка бакалаврів, що включає вивчення фундаментальних принципів автоматичного...
В. О. Леонтьєв програма дисципліни iconВ. О. Леонтьєв Навчальна програма дисципліни
Дисципліна “Комп’ютерні мережі в системах управління” є однією з дисциплін спеціалітету, в рамках вивчення якої майбутні спеціалісти...
В. О. Леонтьєв програма дисципліни iconВ. О. Леонтьєв Навчальна програма дисципліни Вступ в інтелектуальні технології управління
Комп’ютеризовані системи, автоматика І управління”. Адже інтелектуальні технології є тими засобами моделювання систем управління,...
В. О. Леонтьєв програма дисципліни iconВ. О. Леонтьєв Навчальна програма дисципліни Проектування комп’ютеризованих систем управління
Дисципліна „Проектування комп’ютеризованих систем управління” є однією з фундаментальних дисциплін спеціалітету, оскільки одним з...
В. О. Леонтьєв програма дисципліни iconЛ. А. Сіробаба програма навчальної дисципліни та робоча програма навчальної дисципліни
Програма навчальної дисципліни І робоча навчальна програма з дисципліни «Бухгалтерський облік туристичної діяльності» (для студентів...
В. О. Леонтьєв програма дисципліни iconД. В. програма навчальної дисципліни та робоча програма навчальної дисципліни
Програма навчальної дисципліни та робоча програма навчальної дисципліни «Економічна діагностика» для студентів 3 курсу денної форми...
В. О. Леонтьєв програма дисципліни iconМіського господарства тараруєв Ю. О. Програма навчальноі дисципліни та робоча програма навчальноі дисципліни
Програма навчальної дисципліни та робоча програма навчальної дисципліни «Оцінка бізнесу» для студентів 5 курсу денної форми навчання...
В. О. Леонтьєв програма дисципліни iconМіського господарства тараруєв Ю. О. Програма навчальноі дисципліни та робоча програма навчальноі дисципліни
Програма навчальної дисципліни та робоча програма навчальної дисципліни «Фінансування будівництва» для студентів 5 курсу денної форми...
В. О. Леонтьєв програма дисципліни iconЛ. Г. програма навчальної дисципліни та робоча програма навчальної дисципліни
Програма навчальної дисципліни та робоча програма навчальної дисципліни «Управління капіталом» для студентів 6 курсу заочної форми...
Додайте кнопку на своєму сайті:
Документи


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