34. Поняття алгоритму. Властивості алгоритмів. Стійкість, коректність алгоритмів. Аналіз складності та ефективності алгоритмів. Види алгоритмів.

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

Взагалі всі типи задач мають три однакові етапи:

1. Введення даних;

2. Обробка даних;

3. Видача результату.

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

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

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

Алгоритм повинен відповідати певним вимогам, мати такі властивості:

1. Масовість – властивість алгоритму, яка дозволяє отримати очікуваний коректний результат при довільному виконавці.

2. Визначеність – (детермінованість) послідовність інструкцій є фіксованою і визначеною до початку його виконання.

3. Складність – кількість важких операцій для даної задачі.

4. Стійкість – властивість незначно змінювати вихідний результат при значній зміні вхідних даних.

5. Коректність – отримання за скінчений час виконання єдиного стійкого розв’язку.

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

34. Структурний підхід до побудови алгоритмів. Базові структурні елементи алгоритмів.

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

Взагалі всі типи задач мають три однакові етапи:

1. введення даних;

2. обробка даних;

3. видача результату.

Складання алгоритму починається з розбиття описуваного процесу на послідовність окремих кроків. Властивість розбивки алгоритму на окремі кроки називається дискретністю алгоритму. Кожний крок алгоритму формулюється у вигляді інструкцій (команд), тобто визначених розпоряджень виконавцю.

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

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

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

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

Схема проходження складається з двох блоків S₁ i S₂ , кожний з яких у найпростішому випадку може бути арифметичним оператором. Ця структура означає, що два блоки алгоритму можуть бути розміщені один за одним. Наприклад: sum:=0 n:=100

Схема розгалуження відповідає умовному оператору. Ця схема складається з логічного елемента з перевіркою умови Р і блоків S₁ i S₂. Якщо один із блоків відсутній, то отримуємо неповний умовний оператор.

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

.37. Методи розробки алгоритмів: „розділяй і володарюй”, послідовних наближень, найшвидшого спуску, динамічного програмування, пошуку в глибину та в ширину, моделювання.

Метод послідовних наближень. Багато задач не можна розв’язати точно. це може бути із-за неточності вхідних даних, використання спрощень в математичній моделі, а також тому, що точний розв’язок просто не можна отримати. Зміст методу наступний:

 певним чином будується алгоритмічна залежність виду (1), тут відповідно наступне та попереднє наближення;

 певним чином обирається початкове наближення розв’язку. В одних випадках це довільний вибір в інших є цілком визначений алгоритм;

 Згідно із алгоритмічним відображенням (1) будується послідовність наближень розв’язків: до тих пір, поки не буде досягнута необхідна точність результату. В якості умови зупинки послідовних уточнень розв’язку використовується оцінка абсолютної похибки такого наближення розв’язку , де - це невідомий точний розв’язок згідно до теореми Банаха послідовність наближених розв’язків буде збіжною до точного, якщо для алгоритмічного відображення має місце умова стиснення .

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

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

Метод найшвидшого спуску. Алгоритм здійснюється таким чином, щоб кожен крок здійснювався в напрямку досягнення кінцевого розв’язку. Найчастіше цей метод застосовують до так званих напрямлених задач у яких є визначеним положення початкового та кінцевого розв’язку, або у випадку вибору оптимального варіанту серед кількох можливих. Характерною особливістю методу є те, що напрям кожного кроку може бути різним. Головне, щоб черговий крок здійснювався в напрямку найшвидшого досягнення бажаного результату. Це «жадний» метод – значні успіхи на початку можуть призвести до тупікових ситуацій в кінці розв’язку , або до малоефективних останніх кроків, які псують загальний результат.

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