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


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

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

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

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

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

Питання №4

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

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

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

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

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

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

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

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

Питання №5

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

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

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

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

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

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

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

Машина Т’юрінга.

Це гіпотетичний пристрій, який складається з: зовнішньої стрічки, яка розбита на комірки; пристрою зчитування, в якому є внутрішня пам’ять. Стрічка з одного боку являється зовнішньою пам’яттю, з іншого – пристроєм вводу-виводу. В цю стрічку заносяться умови задачі, яка буде вирішуватися. Кожна машина повинна мати свій певний алфавіт: для символьних задач – символи та символьні перетворювання; для алгебраїчних (2+2) – цифри від 0 до 9.

Приклад:

  +    

зчитувальний

Запам’ятовува-льний пристрій
пристрій

1 стан. Крайнє ліве положення в комірці 0, команда – зсунутися вправо.

2 стан. Зсунулися праворуч, в комірці 1, команда – стерти одиницю, запам’ятати її, та пересуватися праворуч до пустої комірки.

3 стан. Досягли пустої комірки, крайній правий стан, команда – одиницю з пам’яті переписати в цю пусту комірку.

4 стан. Рухаємося праворуч, якщо 0 в цій комірці, команда – почати рух ліворуч до пустої ячейки.

5 стан. Якщо в комірці знак «+», команда – «стоп».

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

Питання №6

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

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

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

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

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

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

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

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

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

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

Питання №7

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

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

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

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

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

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

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

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

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

Питання №8

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