Висвітлено основні підходи щодо уточнення поняття алгоритму та теоретичні засади аналізу ефективності алгоритмів. Розглянуто та проаналізовано ряд алгоритмів сортування, зокрема, за квадратичний, лінійний і псевдолінійний час, а також за методами прямого вибирання, злиття, бульбашки. Наведено відомості щодо випадків застосування динамічного програмування.

Освещены основные подходы к уточнению понятия алгоритма и теоретические основы анализа эффективности алгоритмов. Рассмотрен и проанализирован ряд алгоритмов сортирования, в частности, за квадратичное, линейное и псевдолинейное время, а также при помощи методов прямого выбора, слияния, пузыря. Приведены данные о случаях применения динамического программирования.

Розглянуто основні поняття та проблеми теорії алгоритмів. Охарактеризовано класичні алгоритмічні системи: нормальні алгоритми Маркова, рекурсивні функції, машини Тьюрінга, поста, РАМ-машини, досліджено клас важкорозв'язуваних задач. Наведено методи розробки ефективних алгоритмів.

Рассмотрены основные понятия и проблемы теории алгоритмов. Охарактеризованы классические алгоритмические системы: нормальные алгоритмы Маркова, рекурсивные функции, машины Тьюринга, поста, РАМ-машины, исследован класс труднорешаемых задач. Приведены методы разработки эффективных алгоритмов.

Наведено основні визначення, правила та конструкції для створення алгоритмів. Охарактеризовано основні види алгоритмів і їх базові структури. Розглянуто основні етапи розв'язання задач за допомогою комп'ютера. Увагу приділено роботі в системі програмування Квік Бейсік, надано відомості про структуру цієї мови та основні її оператори.

Подано історичний екскурс для висвітлення етимології понять "алгоритм", "алфавітний оператор" і "алгоритмічні системи". Наведено основні засоби побудови алгоритмічних систем, спрямованих на вирішення фундаментальних проблем теорії алгоритмів, а саме доказу обчислюваності та розв'язаності. Увагу приділено прикладним питанням математичної лінгвістики - організації ефективного машинного оброблення природно-мовних текстів з урахуванням семантики мікро- і макроконтексту.

Систематизовано накопичені знання з теорії еволюційних обчислень (теоретичний, експериментальний і проміжний підходи до методів розробки й аналізу генетичних алгоритмів) і окремих її галузей (проблема передчасної збіжності, диплоїдність, налаштування параметрів керування, масштабування функції пристосованості, методи урізноманітнення популяції, способи паралельної реалізації тощо). Досліджено теоретичні можливості окремих класів еволюційних алгоритмів (з керуванням параметрами, комбінованих евристик), а також описано застосування еволюційних алгоритмів для розв'язання ряду науково-технічних задач, у тому числі задачі багатоекстремальної оптимізації (метод утворення ніш на основі розподілу рівня пристосованості, очищення, витиснення, кластеризації, обмежень на формування батьківської пари), задач комбінаторної оптимізації, комівояжера, упаковки та розкрою, оптимізації структури інтегральної схеми, планування шляху мобільного робота, розв'язання діофантових рівнянь, дилеми ув'язненого, головоломок. Розглянуто основні варіанти алгоритмів сучасного еволюційного програмування (мета, R-мета) та традиційного еволюційного програмування в задачах прогнозування.

Наведено базові поняття алгоритмів та їх складності. Розглянуто класичні алгоритмічні системи, зокрема, нормальні алгоритми Маркова, рекурсивні функції, абстрактні машини Тьюрінга і Поста, операторні алгоритмічні системи. Висвітлено питання існування універсального алгоритму та еквівалентності цих алгоритмічних систем. Розглянуто важливі класи мов Р та NP, співвідношення між ними та задачі, які до них належать, а також методи розробки ефективних алгоритмів.

Розглянуто основи теорії алгоритмів, формальні моделі алгоритмів і обчислюваних функцій, ефективні оператори на функціях і множинах. Подано інформацію про канторові нумерації, функцію Геделя, міри обчислювальної складності, співвідношення між класами елементарних і примітивно рекурсивних функцій. Увагу приділено рекурсивному ізоморфізму, релятивізації теорем, арифметичній ієрархії, абстрактній обчислюваності.

Викладено основи теорії алгоритмів, базові ідеї алгоритмізації задач. Висвітлено теоретичні засади розв'язання оптимізаційних задач і застосування числових методів у системах штучного інтелекту. Наведено методи наближеного розв'язання алгебричних і трансцендентних рівнянь, систем лінійних алгебричних рівнянь, інтерполяції, апроксимації та числового інтегрування функцій.

Розглянуто теоретичні та практичні аспекти побудови алгоритмів, методів і програмних засобів моделювання. На великій кількості практичних завдань показано застосування числових методів моделювання та оптимізації для обчислення різноманітних задач в програмному середовищі Matlab.

Розглянуто питання методики загальної побудови алгоритмів, структур даних, пошукових алгоритмів та сортування. Усі теми супроводжено питаннями для самоконтролю та завданнями, виконання яких дозволить закріпити новий матеріал. Зазначено, що перш ніж знайомитися з методами розв’язування прикладних задач, необхідно бути обізнаними з основами теорії алгоритмів як науки, зі структурами даних, уміти визначати, які саме пошукові алгоритми та алгоритми сортування необхідно застосувати у тій чи іншій конкретній задачі. Такі алгоритми можна назвати необчислювальними, оскільки вони є базовими для побудови алгоритмів, що обчислюють результат сформульованої задачі. Необчислювальні алгоритми є платформою для розв’язування задач на графи, лінійного та динамічного програмування тощо. Наведено велику кількість готових фрагментів програм, однак немає жодної готової програми, яка відповідає алгоритму, що вивчається. Велику увагу приділено виробленню навичок тестування розроблених алгоритмів. Поради щодо тестування алгоритмів розміщено або в теоретичній частині матеріалу, або у завданнях, які обов’язково супроводжують його.

Індекс рубрикатора НБУВ: В127.2 я73 + В127.3 я73

Рубрики:

Обчислювальні (рекурсивні) функції

Теорія алгоритмів

Шифр НБУВ: В359379/2 Пошук видання у каталогах НБУВ 

Розглянуто базові поняття сучасної теорії алгоритмів, способи задання алгоритмів, їхній аналіз, а також практичні аспекти використання алгоритмів: базові алгоритми пошуку, сортування, алгоритми на графах. Приділено особливу увагу оцінці складності алгоритмів, що зумовлює вибір алгоритму для вирішення конкретного завдання. Зазначено, що кожен вид алгоритмів супроводжується ілюстративним матеріалом, а також програмним забезпеченням. Рекомендовано для здобувачів першого (бакалаврського) рівня вищої освіти зі спеціальності 122 "Комп'ютерні науки", але також може бути використаний для підготовки здобувачів інших спеціальностей галузі знань 12 "Інформаційні технології", спеціалістам із розробки програмного забезпечення користувачам, які працюють у галузі комп'ютерних наук.