Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки icon

Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки




Скачати 117.67 Kb.
НазваОсвітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки
Дата19.09.2012
Розмір117.67 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Програма фахового вступного випробування для вступу на навчання за освітньо-професійною програмою «бакалавр» на базі здобутого освітньо-кваліфікаційного рівня молодшого спеціаліста Напрям підготовки: 050701 «Електротехніка та електротехнології»
Згідно з нормативними документами вища освіта на Україні має наступні рівні: бакалавр, спеціаліст та магістр з послідуючим переходом...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки icon"Затверджую" Ректор В. М. Бабаєв
Транспортні технології (за видами транспорту)", спеціальності 07010104 "Організація І регулювання дорожнього руху" для прийому на...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки icon"Затверджую" Ректор В. М. Бабаєв
Транспортні технології (за видами транспорту)", спеціальності 07010102 "Організація перевезень І управління на транспорті" для прийому...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconОсвітньо-кваліфікаційний рівень – бакалавр Напрям підготовки
Напрям підготовки – 040106 – екологія, охорона навколишнього середовища та збалансоване природокористування
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки icon"Затверджую" Ректор В. М. Бабаєв
Транспортні технології (за видами транспорту)", спеціальності 07010101 "Транспортні системи " для прийому на навчання осіб, які здобули...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconМіністерство освіти І науки, молоді та спорту України Харківська національна академія міського господарства
Менеджмент", спеціальності 03060107 "Логістика" для прийому на навчання осіб, які здобули освітньо-кваліфікаційний рівень "бакалавр",...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconПрограма фахового вступного випробування для вступу на навчання за освітньо-кваліфікаційним рівнем «спеціаліст»
Міністра освіти і науки від 28. 10. 2004 р., №823 освітньо-кваліфікаційний рівень – бакалавр; напрям підготовки 0925 “Автоматизація...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconПрограма фахових вступних випробувань на здобуття освітньо-кваліфікаційного рівня «магістр» зі спеціальності
Спеціальність «Управління фінансово-економічною безпекою» відноситься до специфічних категорій. За цією спеціальністю можуть навчатися...
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconОсвітньо-кваліфікаційний рівень «бакалавр»
Напрям підготовки: 020303. Філологія (українська мова та література)*. Спеціалізація: документзнавство
Освітньо-кваліфікаційний рівень бакалавр (бакалавр, спеціаліст, магістр) Напрям підготовки iconОсвітньо-кваліфікаційний рівень «бакалавр» (заочна форма)
Напрям підготовки: 020303. Філологія (українська мова та література)*. Спеціалізація: документзнавство
Додайте кнопку на своєму сайті:
Документи


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