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

Теорія алгоритмів 23.07.2014 09:17

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

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

 

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

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

 

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

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

 

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

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

 

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

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

 

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

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

 

Тема7.  Обчислення висловлювань. (Алгебра висловлювань).

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

 

Тема8. Логіка предикатів.

Поняття квантору, квантори існування і загальності. Формули в логіці предикатів. Закони і тотожності в логіці предикатів. Розв’язність формул в логіці предикатів. Нормальні форми в логіці предикатів та логічний вивід. Похідні правила виводу в обчисленні предикатів: правила перейменування зв’язаних змінних, правила уведення і видалення кванторів загальності та існування.

 

Тема9. Проблеми, які неможливо вирішити алгоритмічно. Складність алгоритму.

Проблема розпізнавання можливості виводу в математичній логіці. Проблема розпізнавання самозастосування. Проблема еквівалентності слів для асоціативних обчислень. Індивідуальна та масова задачі. Складність алгоритму.

 

Тема10 Побудова алгоритмів.

Алгоритми на графах, пошук у глибину, пошук найкоротшого шляху. Алгоритми сортування та пошуку даних. Еврістичні алгоритми. Генетичні алгоритми.

 

4. Плани семінарських (практичних, лабораторних) занять

 

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

1. Неформальне поняття і визначення алгоритму.

2. Основні властивості алгоритмів

3. Форми подання алгоритмів.

 

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

1. Основні етапи розробки алгоритму.

2. Основні інформаційні структури даних.

3. Методи розробки алгоритмів.

 

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

1. Поняття рекурсивних  функцій. Визначення рекурсивних функцій за

Черчем.

2 .Базові рекурсивні функції.

3. Тезис Черча

4. Приклади побудови рекурсивних функцій.

 

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

1.Уточнення поняття “алгоритм”. Поняття алфавіту, букви, слова.

 2. Визначення машини Т’юринга

 3. Опис машини Т’юринга. Композиція машин Т’юринга.

 4. Операції над машинами Т’юринга.

 5. Універсальна машина Т’юринга.

 

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

1.Поняття абстрактної машини Поста.

2.Система команд абстрактної машини Поста.

3. Приклади схем машини Поста.

4. Порівняльний аналіз машини Т’юринга  та машини Поста.

 

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

1. Нормальні алгоритми Маркова. Базові поняття.

2. Порядок дії алгорифму Маркова

3. Еквівалентність машин Т’юринга та нормальних алгоритмів Маркова.

 

Тема7.  Обчислення висловлювань. (Алгебра висловлювань).

1. Мова, системи аксіом, основні правила виводу обчислення висловлювань.

2. Теорема дедукції.

3.Правила логічного висновку. Дедуктивні та індуктивні висновки.

4. Метод резолюцій в обчисленні висловлювань.

5 Проблеми аксіоматичного обчислення висловлювань.

 

Тема8. Логіка предикатів.

1.Поняття квантору, квантори існування і загальності.

2.Поняття формули в логіці предикатів.

3.Закони і тотожності в логіці предикатів.

4. Нормальні форми в логіці предикатів та логічний вивід.

5. Похідні правила виводу в обчисленні предикатів.

 

Тема9. Проблеми, які неможливо вирішити алгоритмічно. Складність алгоритму.

1. Характеристика неформалізованого класу задач.

2. Проблема розпізнавання можливості виводу в математичній логіці.

3. Проблема розпізнавання самозастосування.

4. Проблема еквівалентності слів для асоціативних обчислень.

5. Індивідуальна та масова задачі. Складність алгоритму. Класи Р та NP задач.

 

Тема10 Побудова алгоритмів.

1.Алгоритми на графах, пошук у глибину, пошук найкоротшого шляху.

2.Алгоритми сортування та пошуку даних.

3. Еврістичні алгоритми.

4. Генетичні алгоритми.