Тема5 . Машина Поста.

Вступ

Метою вивчення науки є ”Теорія алгоритмів” є опанування фундаментальними поняттями теорії алгоритмів, формування практичних навичок розробки алгоритмів розв’язання прикладних задач а також формування математичної та інформаційної культури студентів напрямку підготовки “Комп’ютерні науки”.

Предметом науки є основні поняття та методи математичної логіки та теорії алгоритмів..

Основні завдання науки. є засвоєння теоретичних знань і формуваня практичних навичок з основ теорії алгоритмів і математичної логіки у

студентів, що спеціалізуються в галузі "Комп’ютерні науки".

Місце науки в учбовому плані. Вивчення науки базується на знаннях курсів “Вища математика” та “Інформатика”. Знання, здобуті під час вивчення науки використовуються в курсах: “Алгоритмізація та програмування”,“Інтелектуальні системи”, “Системи підтримки прийняття рішень”.

Перелік компетенцій, яких набуде студент після опанування даної науки. Після опанування науки студенти повинні:

- мати навички вільного володіння такими об’єктами теорії алгоритмів та математичної логіки як логічні висловлювання, предикати, машина Т’юринга, алгоритми Маркова, рекурсивні функції;

- вміти розпізнавати та конструювати висловлення, предикати, доводити істинність або хибність висловлювань та предикатів;

- вміти розробляти алгоритми розв’язання задач та оцінювати точність одержаних результатів.

2. Тематичний план дисципліни

3. Зміст науки за темами

Тема 1. Алгоритми та їх властивості.

Неформальне поняття і визначення алгоритму. Алгоритм як формальна математична система. Основні властивості алгоритмів: функціональність, результативність, визначеність, елементарність. Форми подання алгоритмів. Проблемні (не результативні) алгоритми.

Тема 2 Прикладна теорія алгоритмів.

Основні етапи розробки алгоритму: постановка завдання і побудова моделі, розробка і реалізація алгоритму, доведення правильності та тестування алгоритму, аналіз складності алгоритму, підготовка документації. Основні інформаційні структури даних: масиви, списки, черги, стеки. Методи розробки алгоритмів.

Тема 3. Рекурсивні функції.

Поняття рекурсивних функцій. Визначення рекурсивних функцій за Черчем. Базові рекурсивні функції. Оператор суперпозиції. Правило суперпозиціїї. Оператор примітивної рекурсіїї.. Правило примітивної рекурсіїї. Оператор мінімізації. Правило мінімізації. Тезис Черча. Приклади побудови рекурсивних функцій.

Тема 4. Машина Т’юринга.

Словникові функції. Визначення машини Т’юринга. Опис машини Т’юринга. Композиція машин Т’юринга. Операції над машинами Т’юринга. Тезис Т’юринга. Правило зупинки.

Тема5. Машина Поста.

Опис машини Поста. Функціонування машини Поста. Гіпотеза Поста. Порівняльний аналіз машини Т’юринга та машини Поста.

Тема6. Нормальні алгорифми Маркова.

Визначення нормального алгорифму Маркова. Марковська підстановка. Етапи розв’язку задач. Порядок дії алгорифма Маркова. Еквівалентність машин Т’юринга та нормальних алгоритмів Маркова.

Не нашли, что искали? Воспользуйтесь поиском: