ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Поняття алгоритму. Властивості.

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


План:

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. Генетичний алгоритм, головні операції.

 

Питання №1

Поняття алгоритму. Властивості.

Алгоритм – послідовність результативних кроків для вирішення задачі.

Властивості алгоритмів:

1. Дискретність алгоритму. Під дискретністю визначається поділення алгоритму на певну кількість елементарних детермінованих кроків.

2. Детермінованість. Кожен крок повинен бути елементарним та визначеним (детермінованим).

3. Результативність. Кожен крок повинен мати якийсь результат на вході та результат на виході. Цю властивість також називають направленістю.

4. Масовість. Певний клас алгоритмів можна застосувати для вирішення окремого класу задач.

5. Складність.

Питання №2

Складність алгоритму.

Під алгометричною складністю визначають кількість комп’ютерних ресурсів, які необхідні для реалізації певного алгоритму. Складність буває:

- Часова;

- Ємкісна.

Часова складність – кількість часу, який необхідне для вирішення задачі.

Ємкісна складність – кількість кроків алгоритму необхідних для вирішення задачі.

Питання №3

Класифікація алгоритмів по ємкісній складності.

За ємкісною складність всі задачі діляться на три групи.

1. Р-задачі (Поліноміальні). Це група задач, для вирішення яких існують алгоритми, які можна реалізувати за кінцеву кількість кроків. Поліном - многочлен n-ої степені. Найвищий ступінь поліному: a5+k*a4+b*a3+s*a2+x*a1.

2. Е-задачі (Експоненціальні). Це задачі, які можуть бути вирішені або не можуть бути вирішені. Експоненціальна складність означає, що кількість кроків велика, і не завжди вона може бути кінцевою. Щоб оцінити створюють логарифмічний вираз.

3. NP-задачі (Не поліноміальні). Задачі, які відносяться до класу не вирішуваних, або важко вирішуваних.

Питання №4

Головні групи алгоритмів.

Головні групи алгоритмів розділяються на:

- Алгоритми пошуку;

- Алгоритми сортування;

- Чисельні алгоритми;

- Алгоритми на графах;

- Комбінаторні алгоритми;

- Різні алгоритми.

Питання №5

Питання №6

Формальні моделі алгоритмів, «Машина Поста».

Формальні моделі алгоритмів:

1Машина Т’юрінга:

- Одно стрічкова;

- Багато стрічкова.

2Машина Поста;

3Алгоритм Маркова.

Машина Поста.

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

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

Питання №7

Формальні моделі алгоритмів, «Нормальний алгоритм маркова».

Формальні моделі алгоритмів:

1Машина Т’юрінга:

- Одно стрічкова;

- Багато стрічкова.

2Машина Поста;

3Алгоритм Маркова.

Нормальний алгоритм Маркова.

Базується на асоціативному зчисленні, яке складається з алфавіту, базових слів і правил перетворення. Алгоритм Маркова є універсальною моделлю алгоритмів яка відрізняється від машини Тюрінга і Поста тим, що існує базовий алфавіт, базові слова (оператори), базові підстановки (оператори) та існує задача отримання результату. Основу нормального алгоритму Маркова складає поняття асоціативного зчислення. Асоціативне зчислення складається з алфавіту , чітко визначених символів базових слів, які зформовані на цьому алфавіті , системи підстановок. Це система правил, яка застосовується до базових слів з метою створення нових слів і правилом використання підстановок.

Питання №8

Алгоритм пошуку, «Лінійний алгоритм».

Алгоритми пошуку - це алгоритми пошуку в масиві даних (або в якійсь структурі) певного елемента або елементів з визначеними параметрами, які називаються, параметрами пошуку.

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Лінійний пошук.

Існує певна структура даних (масив, список…) і треба знайти в цій структурі елемент з певними властивостями. Цей пошук простий, але не ефективний, коли ми маємо велику кількість даних.

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

Питання №9

Алгоритм пошуку, «Ймовірнісний пошук».

Алгоритми пошуку - це алгоритми пошуку в масиві даних (або в якійсь структурі) певного елемента або елементів з визначеними параметрами, які називаються, параметрами пошуку.

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Ймовірнісний пошук.

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

Переваги:

1. Скорочення часу пошуку;

2. Якщо кількість перевірених об’єктів в результаті пошуку пропорційна загальному обсягу масиву, то точність приблизно 80%.

Недоліки:

1. Наближена точність;

2. Не працює з відносно малими масивами даних.

Питання №10

Алгоритм пошуку, «Неявний пошук».

Алгоритми пошуку - це алгоритми пошуку в масиві даних (або в якійсь структурі) певного елемента або елементів з визначеними параметрами, які називаються, параметрами пошуку.

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Неявний пошук.

Неявний пошук..............

Питання №11

Алгоритм пошуку, «Евристичний пошук».

Алгоритми пошуку - це алгоритми пошуку в масиві даних (або в якійсь структурі) певного елемента або елементів з визначеними параметрами, які називаються, параметрами пошуку.

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Евристичний пошук.

Евристичний пошук, це пошук, який відбувається за допомогою евристики, евристичних припущень (чисельні або примусові параметри). Полягає в тому, що будується дерево майбутніх ходів.

Для алгоритму евристичного пошуку будується дерево майбутніх варіантів (станів), кожен з варіантів оцінюється за допомого евристичної функції: f(g)=g+h(g), де

g – поточний стан ситуації;

h(g) – евристична складова.

Питання №12

Стратегії пошуку на графах (пошук в довжину, пошук в ширину…).

Графи являються універсальним формальним описом будь-якої прикладної форми та задачі. Графи можуть представлятися матрицями суміжності та інцедентності. Ці графи дуже легко перетворити в необхідні структури даних. І відповідно дуже легко можливо перетворити в різні допоміжні структури (списки, дерева…). Існує багато типів алгоритмів на графах з пошуком оптимальних частин графа, частина пов’язана з побудовою нових графів на основі даних, які закладені в базовому графі.

А
В основу алгоритмів на графах покладена процедура пошуку відповідних вершин або ребер. Пошук цей здійснюється за допомогою різних стратегій:

- Пошук в ширину;

-

D
С
В
Пошук в глибину;

- Пошук з поверненням;

-

L
K
H
J
F
E
«Жадібний» пошук.

Пошук в ширину.

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

Пошук в глибину.

Починається з обирання глибини пошуку.

Пошук з поверненням.

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

«Жадібний» пошук.

Це пошук при якому, якщо знайдене рішення наближене до потрібного пошук припиняється.

Питання №13

Алгоритм Дейкстри.

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

Алгоритм Дейкстри – це послідовна ітераційна процедура, в основу якої покладений пошук в ширину, це перший крок. На наступному кроці процедура повторюється. Але для перевірки на другому кроці, використовують пошук в глибину, задаються глибиною 3-4 і обраховують довжину шляху до всіх вершин цього рівня. Обирають ту вершину цього рівня, шлях до якої є коротшим.

Питання №14

Алгоритм Прима-Краскала.

Каркас – це під-граф на базовому рівні графа, в якому не має циклів.

Алгоритм складається з двох частин:

- Виписуються всі ребра і сортуються за зростанням починаючи з мінімального;

- Починається будівництво каркасу, в якому починаючи з мінімального ребра, повинні бути охоплені всі вершини.

Питання №15

Питання №16

Питання №17

Питання №18

Питання №19

Питання №20

Питання №21

Сортування Шела.

Ідея алгоритму полягає у обміні елементів, що розташовані не тільки поряд, як у алгоритмі простих вставок, але й далеко один від одного. Це значно скорочує загальну кількість операцій переміщення елементів. Для прикладу візьмемо масив з 16 елементів. Спочатку переглядаються пари з кроком 8. Це пари елементів 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Якщо значення елементів у парі не впорядковані за зростанням, то ці елементи обмінюються місцями. Це етап сортування з кроком 8.

Наступний етап - сортування з кроком 4. На цьому етапі елементи масиву розділяються на четвірки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Виконується сортування в межах кожної четвірки. Це сортування може виконуватися методом простих вставок.

Наступний етап - сортування з кроком 2, коли елементи у масиві розподіляються на 2 групи по 8: 1-3-5-7-9-11-13-15 і 2-4-6-8-10-12-14-16. Виконується сортування в кожній групі. Нарешті весь масив впорядковується методом простих вставок. Оскільки більшість елементів вже розташовані біля своїх місць, то цей етап буде значно швидкішим.

Питання №22

Питання №23

Питання №24

Питання №25

Питання №26

Блочні.

При блочному шифруванні інформація розбивається на блоки фіксованої довжини і сама інформація шифрується по-блочно:

1) шифри перестановки;

2) шифри підстановки.

В шифрах покладений принцип ReadBook. Можуть бути: моно- та поліалфавітні.

В моноалфавітних шифрах (код Цезаря): перша літера фіксовано міняється на іншу.

В поліалфавітних шифрах: перша літера міняється на символ певного алфавіту послідовно.

Зіставні шифри.

Під «зіставними шифрами» визначають шифри, в яких можуть використовуватися в якості ключів різні типи підстановок і замін.

Головні алгоритми:

- Люцифер (фірма IBM);

- Death (Data Susciption);

- Idea;

- Бікрінт (ГОСТ СССР).

Питання №27

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


План:

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. Генетичний алгоритм, головні операції.

 

Питання №1

Поняття алгоритму. Властивості.

Алгоритм – послідовність результативних кроків для вирішення задачі.

Властивості алгоритмів:

1. Дискретність алгоритму. Під дискретністю визначається поділення алгоритму на певну кількість елементарних детермінованих кроків.

2. Детермінованість. Кожен крок повинен бути елементарним та визначеним (детермінованим).

3. Результативність. Кожен крок повинен мати якийсь результат на вході та результат на виході. Цю властивість також називають направленістю.

4. Масовість. Певний клас алгоритмів можна застосувати для вирішення окремого класу задач.

5. Складність.

Питання №2

Складність алгоритму.

Під алгометричною складністю визначають кількість комп’ютерних ресурсів, які необхідні для реалізації певного алгоритму. Складність буває:

- Часова;

- Ємкісна.

Часова складність – кількість часу, який необхідне для вирішення задачі.

Ємкісна складність – кількість кроків алгоритму необхідних для вирішення задачі.

Питання №3

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти