Алгоритми і методи обчислення

Код модуля:

Тип модуля: обов’язковий

Семестри: другий, третій

Обсяг модуля:

Загальна кількість годин – 225 (кредитів ЕКТС – 7,5) аудиторні години – 108(лекції – 40, практичні заняття – 22, лабораторні заняття – 46)

Лектор: к.т.н., доцент Сидоренко Валерій Миколайович

Результати навчання:

знати:

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

вміти:

розробляти, аналізувати та застосовувати ефективні алгоритми для розв’язання професійних завдань в області комп’ютерної інженерії.

Спосіб навчання (аудиторне, дистанційне навчання): аудиторне

Необхідні обов’язкові попередні та супутні модулі:

  • вища математика, теорія ймовірностей та математична статистика, обчислювальна техніка,  програмування, дискретна математика.

 Зміст навчального модуля:

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

Аналіз алгоритмів та алгоритмічні стратегії

Математичні основи аналізу алгоритмів. Алгоритмічні стратегії. Основи теорії обчислюваності. Класи складності Р і NP.

Фундаментальні алгоритми та їх побудова.

Алгоритми сортування, злиття та пошуку. Алгоритми хешування: хеш-функції та методи розв’язання колізій. Фундаментальні алгоритми на деревах: АВЛ-дерева, В-дерева. Алгоритми пошуку в рядках та їх обробки. Методи розробки алгоритмів.

Лінійне програмування.

Графічний та симплекс-методи розв’язку задачі лінійного програмування. Двоїста задача. Метод штучного базису. Методи розв’язку транспортної задачі та задачі про призначення.

Нелінійне програмування.

Методи розв’язку задач одновимірної нелінійної оптимізації. Методи розв’язку багатовимірної нелінійної безумовної і умовної оптимізації.

Методи обчислень.

Елементи теорії обчислень. Застосування алгоритмів і методів для розв’язання інженерних задач на ПК. Поняття про наближенні обчислення. Похибки та їх джерела. Розв’язання СЛАР. Розв’язання нелінійних рівнянь та їх систем. Інтерполяція та апроксимація функцій.

Методи чисельного інтегрування функцій. Методи розв’язання задачі Коші для диференціальних рівнянь. Чисельне інтегрування визначних інтегралів. Розв’язання диференціальних рівнянь та їх систем. Тема 7. Чисельне диференціювання

Рекомендована література:

1. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест и др. – М. : ИД "Вильямс", 2011. – 1296 с.

2. Ахо А. Структуры данных и алгоритмы: учебн. пособ. / А. Ахо, Д. Хопкрофт, Д. Ульман; пер. с англ. – М. : ИД "Вильямс", 2000. – 384 с.

3. Седжвик Р. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных / Р. Седжвик. – М. : ИД "Вильямс", 2011. – 1056 с.

4. Турчак Л. И. Основы численных методов: Учеб. Пособие. – М.: «Наука»,1987. – 320 с.

5. Заварыкин В.М. Численные методы: Учеб. пособие для студ. физ.-мат. спец. пед. инст / В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик.– М.: Просвещение, 1990. –176 с.

4. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. – М. : Мир, 1979. – 536 с.

5. Вирт Н. Алгоритмы и структуры данных / Н. Вирт; пер с англ. – М.: Мир, 1989. – 360 с.

6. Кнут Д. Є. Сортировка и поиск: учебн. пособ. / Д. Э. Кнут ; пер. с англ. 2-е изд. – М.: ИД "Вильямс", 2000. – 832 с.

7. Марков А. А. Теория алгоритмов / А. А. Марков, Н. М. Нагорный. – М.: Наука, 1984. – 432 с.

8. Техніка обчислень і алгоритмізація / І. Ф. Следзінський, А. М. Ломакович, Ю. С. Рамський та ін. – К. : Вища шк., 1991. – 199 с.

6. Фурунжиев Р. И. Применение математических методов и ЭВМ: Практикум: Учеб. пособие / Р. И. Фурунжиев, Ф. М. Бабушкин, В. В. Варавко. – Минск: Вышэйшая школа, 1988. – 189 с.

7. Мудров А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль.– Томск: МП "РАСКО", 1991.– 272 с.

Форми та методи навчання:

Лекції, практичні та лабораторні заняття, самостійна робота

Методи та критерії оцінювання:

Поточний контроль та підсумковий контроль:

  • лекції усіх змістовних модулів (10%);
  • модульний контроль (50%);
  • робота на практичних та лабораторних заняттях (20%);
  • залік (2 семестр), іспит(3 семестр) (20%)

Мова навчання: українська 

Викладачі: 
Зображення користувача vmsidorenko.

Сидоренко Валерій