Київський міжнародний університет
Теорія алгоритмів. Основна сторінка
The theory of algorithms. Main page.
Проф. Шпига Петро Семенович
Перший семестр
Лекція 1. Вступ до теорії алгоритмів.
Лекція 2. Властивості алгоритмів.
Лекція 3. Форми запису алгоритмів.
Лекція 4. Дані та величини.
Лекція 5. Семантика та синтаксис алгоритмів.
Лекція 7. Архітектура програмного забезпечення.
Лекція 8. .
Практична 1. Поняття та приклади найпростіших алгоритмів.
Практична 2. Приклади алгоритмів пошуку.
Практична 3.
Практична 4.
Практична 5. Теорія алгоритмів сортування.
Контрольні питання до заліку.
- Поясніть терміни алгоритм, задача, виконавець алгоритму,
- Призначення алгоритмів.
- Приклади алгоритмів.
- Зв'язок задачі та алгоритму.
- Історія виникнення теорії алгоритмів.
- Виконавець алгоритмів.
- Оцінка алгоритмів.
- Базові структури алгоритмів.
- Основні властивості алгоритмів.
- Форми запису алгоритму.
- Приклади алгоритмічних процедур.
- Необхідність уточнення поняття алгоритму. Проблеми алгоритмічної розв’язності та алгоритмічної нерозв’язності.
- Поняття алгоритмічної системи. Загальна схема побудови алгоритмічної системи.
- Граф-схеми і блок-схеми алгоритмів.
- Задавання нормальних алгоритмів Маркова за допомогою граф-схем Калужніна.
- Пояснити, що означає таке: нормальний алгоритм застосовний до певного вхідного слова.
- Сформулювати та пояснити принцип нормалізації.
- Основні способи композиції нормальних алгоритмів (суперпозиція, об’єднання, розгалуження, ітерація).
- Теорема про універсальний нормальний алгоритм і її значення.
- Поняття обчислюваної функції.
- Схема примітивної рекурсії для одномісної функції.
- Означення примітивно рекурсивної функції. Навести приклад.
- Означення частково рекурсивної функції.
- Чому будь-яка примітивно рекурсивна функція є частково рекурсивною?
- Структура і принцип функціонування машини Тьюрінга.
- Поняття команди, конфігурації і програми машини Тьюрінга.
- Проблема зупинки. Обґрунтувати твердження про алгоритмічну нерозв’язність проблеми зупинки.
- Зв’язок машин Тьюрінга і частково рекурсивних функцій.
- Інші моделі обчислень (РАМ-машина, РАЗП-машина, спрощений АЛГОЛ, недетермінована машина Тьюрінга).
- Побудова та оцінка алгоритмів. Оптимізація алгоритмів за різними показниками.
- Архітектура програмного забезпечення.
- Проблеми і мови. Поняття розмірності масової проблеми.
- Основні кількісні характеристики алгоритмів. Статична і динамічна складності алгоритмів.
- Залежність обчислювальної складності від використовуваної моделі обчислень.
- Сформулювати та обґрунтувати NP-повноту кількох проблем.
- Основні алгоритми пошуку в масивах та їх порівняльний аналіз.
- Порівняльний аналіз алгоритмів пошуку шляхів у графі.
- Алгоритм для реалізації обмеженого пошуку вглиб (АОПГ).
Джерела
Довідкові. References.
- Теория алгоритмов. Материал из Википедии [Текст російською].
- Theory of computation. From Wikipedia, the free encyclopedia. [Text].
- Теория алгоритмов. Викиверситет. [Текст російською].
- Algorithm Engineering. From Wikipedia, the free encyclopedia. [Text].
- Шпига П.С. Алгоритми. Стаття на сайті "Зерна".
Textbooks aimed at computer students.
- Яворський Б.І. Теорія алгоритмів / Конспект лекцій.— Тернопіль: ТДТУ імені Івана Пулюя, 2000.— 36 с. (текст pdf). У навчальному посібнику висвітлюються змістовні основи теорії алгоритмів для студентів технічних університетів, що навчаються за спрямуванням вищої освіти 6.0804 — комп’ютерні науки, спеціальності 7.080401 — інформаційні управляючі системи та технології.
- Теорія алгоритмів Олексія Молчановського. Перейти до курсу.
- Розробка та аналіз алгоритмів. Дистанційний курс навчання Олексія Молчановського (безкоштовний). Перейти до курсу.
- Алгоритмы: построение и анализ: Информация Автор: Даниил Швед | Московский физико-технический институт. Відео-лекції
- Введение в алгоритмы: Информация Автор: Виктор Иванников НОУ «ИНТУИТ», Відео-лекції.
- Тестирование математических алгоритмов. habrahabr.ru
- Cormen Introduction to Algorithms. Книга перекладена і видана російською мовою під назвою Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 стаття у википедия, рос
- Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. – стаття у wikipedia, англ.
- Algorithms, Part I (Coursera). Перейти до курсу.
- Algorithms, Part II (Coursera). Перейти до курсу.
- Algorithms: Design and Analysis, Part 1 (Coursera). Перейти до курсу.
- Algorithms: Design and Analysis, Part 2 (Coursera). Перейти до курсу.
- Introduction to Theoretical Computer Science (Udacity). Перейти до курсу.
Джерела на тему "Програмування"
- Програмування. Курс лекцій. (Зміст курсу)
- Лекція 15. Авторське право на програмний продукт (текст) .
- Хочешь научиться программировать? Получи доступ к десяткам бесплатных материалов.Общайся и учись на курсах от ведущих IT-специалистов. geekbrains.ru
- Peter Norvig. Teach Yourself Programming in Ten Years. (текст). Про легенди та справжні терміни навчання програмуванню.