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

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




Скачати 117.93 Kb.
НазваМіністерство освіти І науки україни
Дата13.07.2012
Розмір117.93 Kb.
ТипДокументи



МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Сумський державний університет

__________________ факультет ЕЛіт______________________

(повна назва інституту або факультету, для студентів якого викладається навчальна дисципліна)

_____________________________кафедра інформатики_______________________

(повна назва кафедри викладання навчальної дисципліни)

ЗАТВЕРДЖУЮ


Декан факультету ЕлІТ СумДУ


__________________ _С.І.Проценко___

( підпис) (прізвище, ініціали)

“____” ______________ 2009 р.

^

РОБОЧА ПРОГРАМА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ



________ТЕОРІЯ АЛГОРИТМІВ ТА МАТЕМАТИЧНА ЛОГІКА______

(назва навчальної дисципліни)

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


(бакалавр, спеціаліст, магістр)

^ Напрям підготовки (спеціальність) _________6.040302 інформатика_______________

_____________________________________________________________________

(шифр та назва напряму підготовки (із зазначенням за необхідності фахового спрямування) або шифр та назва спеціальності)

Форма навчання ________денна_______________


(денна, вечірня)

^

ХАРАКТЕРИСТИКА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ


_________ обов’язкова ________________

(обов’язкова, за вибором ВНЗ, за вибором студента)

^ Семестр викладання

Загальний

обсяг,

годин/кредит.

Аудиторні заняття, годин

^ Самостійна робота студента, годин

Форма

контролю ісп. (д/зал.)

Всього

Лекції

Практичні

(семі-нарські)

Лабораторні

Всього

тому числі

ІРС під керівн. викладача

Інд. завдання. вид / обсяг

^ Самостійне опрацювання матеріалу

4

216/6,0

90

40

50

-

126

12

РР/34

80

Д/з





































































Розробник: __доцент, к.ф.-м.н. Шаповалов С.П..________________________________


(вказати авторів, їх наукові ступені та посади)


Затверджено на засіданні кафедри, протокол № 12 від 23 червня 2009 р.


Суми – 2009 р.

МЕТА



^ Основною метою дисципліни є освоєння принципів побудови та аналізу алгоритмів, математичному обґрунтуванню їх застосування.

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

^ ЗНАННЯ:

побудови та застосуванні основних алгоритмів при програмуванні;

аналізу алгоритмів та вибору найбільш ефективного алгоритму;

ВМІННЯ :

згенерувати вхідні данні та запрограмувати застосування алгоритму;

складати та налагоджувати програми з застосуванням алгоритмів з аналізом;

Дисципліна “Теорія алгоритмів та математична логіка” є однією з базових дисциплін для напряму підготовки „ Прикладна математика” та забезпечує структурно-логічний зв’язок між іншими дисциплінами цього напряму. Базовими є розділи „ Аналіз та побудова алгоритмів”, „Динамічне програмування”, Алгоритми на графах”.

^ Перелік питань вхідного контролю :

складання структурних схем алгоритмів та їх програмна реалізація;

Основні поняття та розділи дисципліни „Дискретна математика”.


ПРОГРАМА



Вступ

Структура та задачі курсу. Місце дисципліни серед інформаційних досліджень.Основні властивості алгоритмів.Аналіз та побудова алгоритмів, запис на псевдокоді, принцип „ розподіляй та владарюй”, корисність швидких алгоритмів

Тема 1. Математичні основи теорії алгоритмів.

Теорія множин, відношення, функції та перетворення, алгебраїчні структури, асимптотичні позначення. Рекурсивні, рекурсивно перелічені множини, рекурсивні, частково рекурсивні предикати. Елементи математичної логіки, логіка висловлювань, логіки 1-го порядку, аксіоматичні системи, логіка та числення предикатів. Елементи теорії графів, маршрути, ланцюги та цикли, зв’язність, дерева, фарбування графа.

Тема 2. Алгоритми сортування.

Сортування злиттям, швидке сортування, ймовірності алгоритми, сортування купою, черги з пріоритетами, аналіз алгоритмів. Порівняльний аналіз алгоритмів за асимптотичними оцінками.

Тема 3. Основні парадигми в теорії алгоритмів.

Порівняльний аналіз алгоритмів за асимптотичними оцінками. «Жадібні стратегії» та динамічне програмування. Рекурсивні алгоритми. Жадібні алгоритми, теоретичні основи, застосування. Коди Хаффмена.

Тема 4. Алгоритми на графах.

Дерева та ліс. Бінарні дерева пошуку. Пошук в ширину та глибину. Топологічне сортування.Червоно-чорні дерева. Пошук остова графа. Алгоритми Прима та Крускала.Задачі про максимальний та мінімальний потоки в графах.

Тема 5. Класи складності алгоритмів.

Розподіл алгоритмів за класами складності. Співвіношення між класами. Вибрані алгоритми.

NP – повнота, наближені алгоритми, задача про комівояжера, задача про покриття множинами.


^

СТРУКТУРА ЗАЛІКОВИХ КРЕДИТІВ КУРСУ





Тема

Загальний обсяг,

годин

Лекції,

годин

Практичні

(семінарські)заняття,

годин

Лабораторні роботи, годин

Самостійне опрацювання матеріалу (у тому числі ІРС),

Годин

Індивід. завдання,

годин

Семестр 7

^ 1-й модульний цикл дисципліни

Вступ.

Тема1. Математичні основи теорії алгоритмів

34

10

4

-

20

-

Тема 2. Алгоритми сортування

36

10

4

-

22

-

Контрольний захід за модульний цикл: тестовий контроль

2

-

2


-







Всього по модульному циклу

72

20

10




42

-

2-й модульний цикл дисципліни

^ Тема 3. Основні парадигми в теорії алгоритмів.

34

4

10

-

20

-

Тема 4. Алгоритми на графах

36

6

8




22




^ Контрольний захід за модульний цикл: тестовий контроль

2




2










Всього по модульному циклу

72

10

20

-

42

-

3-й модульний цикл дисципліни

^ Тема 4. Алгоритми на графах

34

4

8

-

22

-

Тема 5. Класи складності алгоритмів

36

6

10




20




^ Контрольний захід за модульний цикл: тестовий контроль

2




2










Всього по модульному циклу

72

10

20

-

42

-

Всього за семестр

216

40

50

-

126

-

Всього з навчальної дисципліни

216

40

50

-

126

-



^ ТЕМИ ПРАКТИЧНИХ (СЕМІНАРСЬКИХ) ЗАНЯТЬ

1. Математичні основи теорії алгоритмів – 4 год.

1.1Теорія множин.

1.2 Математична логіка.

1.3 Теорія графів.

2.Алгоритми сортування – 4 год.

2.1 Запис алгоритмів на псевдокоді. Асимптотичні оцінки.

2.2 Порівняльний аналіз алгоритмів сортування.

3. Основні парадигми в теорії алгоритмів.– 10 год.

3.1«Жадібні стратегії» та динамічне програмування.

3.2 Рекурсивні алгоритми.

3.3 Жадібні алгоритми, теоретичні основи, застосування. Коди Хаффмена.

4. Алгоритми на графах. – 16 год.

4.1 Побудова бінарних дерев пошуку.

4.2Червоно-чорні дерева.

4.3Пошук остовних дерев графа.

4.4Основні алгоритми на графах.

5. Класи складності алгоритмів. – 10 год.

5.1 Розподіл алгоритмів за класами складності. Співвіношення між класами.

5.2 Вибрані алгоритми.


^ ЛАБОРАТОРНІ РОБОТИ


Лабораторні работи не передбачені.


ІНДИВІДУАЛЬНІ ЗАВДАННЯ


Індивідуальні завдання не передбачені .


Б. Навчальний проект


Навчальний проект не передбачен.

^ МЕТОДИ НАВЧАННЯ


Лекції: викладення теоретичного матеріалу; оглядові лекції з використанням опорного конспекту; лекції-дискусії; лекції-візуалізації із використанням мультимедійних технологій.

Практичні заняття: розв’язання типових завдань; робота над індивідуальними завданнями.


^ МЕТОДИ ОЦІНЮВАННЯ


Контроль навчальної роботи студента здійснюються тестуванням.


МЕТОДИЧНЕ ЗАБЕЗПЕЧЕННЯ


Для забезпечення навчальної роботи студентів на лекційних, практичних заняттях та також для виконня індивідуальних завдання використовуеться основна література [1-3] та додаткова – [4-6]/


ЛІТЕРАТУРА

А. Основна навчальна література


№ п/п

Назва навчальної літератури

Вид

Наявність,

примірників

1

Дистанційний курс з дисципліни „Теорія алгоритмів та математична логіка” – Суми: В-во СумДУ, 2007.

На електронних носіях інформації




2

Т.Кормен, Ч. Лейзерсон, Р.Риверст Алгоритмы: построение и анализ.-М.: МЦННМО, 2001.-960 с.

Книга

^ Та електронний файл

2

3

Р.Седжвик Фундаментальне алгоритмы на С++.- Киев:Диасофт, 2001.-688 с.

Книга

2



Б. Додаткова рекомендована література


№ п/п

Назва навчальної літератури

Вид

Наявність,

примірників

4

^ Соловей О.С.Математичні вказівки „Програмування алгоритмів сортування. Тестування алгоритмів.”-Суми, 2003.

Книга

50

5

Шаповалов С.П., Дзюба О.О. Методичні вказівки до лабораторних робіт з дисципліни «Теорія алгоритмів та математична логіка».- Суми, 2006.

Книга

50

6

Соловей О.С.Математичні вказівки „Вдосконалення алгоритму швидкого сортування”.- Суми, 2003.

Книга

50



Розробники програми ____________ С.П.Шаповалов

(підписи авторів робочої програми)

Завідувач кафедри ______________ А.С.Довбиш


(підпис)


Схожі:

Міністерство освіти І науки україни iconПоложення про нагородження нагрудним знаком "А. С. Макаренко" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconПоложення про нагородження нагрудним знаком "Василь Сухомлинський" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconПоложення про нагородження нагрудним знаком "Софія Русова" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconРішення про нагородження Нагрудним знаком ухвалюється Колегією Міністерства освіти І науки України, затверджується наказом Міністра І публікується в газеті "Освіта України"
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconРішення про нагородження Нагрудним знаком ухвалюється Колегією Міністерства освіти І науки України, затверджується наказом Міністра І публікується в газеті "Освіта України"
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconРішення про нагородження Нагрудним знаком ухвалюється Колегією Міністерства освіти І науки України, затверджується наказом Міністра І публікується в газеті "Освіта України"
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти І науки україни iconМіністерство освіти І науки україни 01135, м. Київ, проспект Перемоги
Міністерства освіти і науки України від 17. 04. 2009 року №341 «Про затвердження Плану дій щодо вдосконалення викладання дисципліни...
Міністерство освіти І науки україни iconПоложення про нагородження нагрудним знаком "Петро Могила" Міністерства освіти І науки України
Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської І севастопольської міських...
Міністерство освіти І науки україни iconМіністерство освіти І науки україни пр. Перемоги
Міністерство освіти і науки Автономної Республіки Крим, управління (департаменти) освіти і науки обласних, Київської і Севастопольської...
Міністерство освіти І науки україни iconМіністерство освіти І науки україни пр. Перемоги
Міністерство освіти і науки, молоді та спорту Автономної Республіки Крим, управління (департаменти) освіти і науки обласних, Київської...
Міністерство освіти І науки україни iconМіністерство освіти І науки україни пр. Перемоги
Міністерство освіти і науки, молоді та спорту Автономної Республіки Крим, управління (департаменти) освіти і науки обласних, Київської...
Додайте кнопку на своєму сайті:
Документи


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