|
Teor_alg_osn
Київський міжнародний університет
Теорія алгоритмів. Основна сторінка
The theory of algorithms. Main page.
Проф. Шпига Петро Семенович
Перший семестр
Лекція 8. .
Практична 1. Поняття та приклади найпростіших алгоритмів.
Практична 2. Приклади алгоритмів пошуку.
Практична 3.
Практична 4.
Контрольні питання до заліку.
- Поясніть терміни алгоритм, задача, виконавець алгоритму,
- Призначення алгоритмів.
- Приклади алгоритмів.
- Зв'язок задачі та алгоритму.
- Історія виникнення теорії алгоритмів.
- Виконавець алгоритмів.
- Оцінка алгоритмів.
- Базові структури алгоритмів.
- Основні властивості алгоритмів.
- Форми запису алгоритму.
- Приклади алгоритмічних процедур.
- Необхідність уточнення поняття алгоритму. Проблеми алгоритмічної розв’язності та алгоритмічної нерозв’язності.
- Поняття алгоритмічної системи. Загальна схема побудови алгоритмічної системи.
- Граф-схеми і блок-схеми алгоритмів.
- Задавання нормальних алгоритмів Маркова за допомогою граф-схем Калужніна.
- Пояснити, що означає таке: нормальний алгоритм застосовний до певного вхідного слова.
- Сформулювати та пояснити принцип нормалізації.
- Основні способи композиції нормальних алгоритмів (суперпозиція, об’єднання, розгалуження, ітерація).
- Теорема про універсальний нормальний алгоритм і її значення.
- Поняття обчислюваної функції.
- Схема примітивної рекурсії для одномісної функції.
- Означення примітивно рекурсивної функції. Навести приклад.
- Означення частково рекурсивної функції.
- Чому будь-яка примітивно рекурсивна функція є частково рекурсивною?
- Структура і принцип функціонування машини Тьюрінга.
- Поняття команди, конфігурації і програми машини Тьюрінга.
- Проблема зупинки. Обґрунтувати твердження про алгоритмічну нерозв’язність проблеми зупинки.
- Зв’язок машин Тьюрінга і частково рекурсивних функцій.
- Інші моделі обчислень (РАМ-машина, РАЗП-машина, спрощений АЛГОЛ, недетермінована машина Тьюрінга).
- Побудова та оцінка алгоритмів. Оптимізація алгоритмів за різними показниками.
- Архітектура програмного забезпечення.
- Проблеми і мови. Поняття розмірності масової проблеми.
- Основні кількісні характеристики алгоритмів. Статична і динамічна складності алгоритмів.
- Залежність обчислювальної складності від використовуваної моделі обчислень.
- Сформулювати та обґрунтувати 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. (текст). Про легенди та справжні терміни навчання програмуванню.
|
Календар
« Березень 2024 » | Пн | Вт | Ср | Чт | Пт | Сб | Нд | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
Статистика
Онлайн всього: 5 Гостей: 5 Зареєстрованих: 0
|