Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆
  1. Реалізація алгоритму.

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

1) кроки алгоритму можуть не відповідати мовним конструкціям, наприклад, крок може вимагати ці­лої підпрограми для його реалізації;

2) потрібно побу­ду­вати цілу систему струк­тур даних для представлення важливих аспектів мо­делі, яка вико­ри­сто­вується.

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

  1. Аналіз алгоритму і його складності.

Необхідність цього етапу обумовлена як прак­тичними, так і теоретичними чинниками. Перші пов’язані із отриманням оцінок або меж для дорогих обчислювальних ресурсів – пам’яті чи часу ро­бо­ти, які потрібні алгоритму для оброблення конкретних даних, щоб видати результат, важливий для розв’язання практично корисної проблеми. Другі пов’язані з природним бажанням кількісно оцінити ресурси, які вимагаються різними алгоритмами – претендентами на розв’язання однієї й тієї ж проблеми – для вибору з них найефективнішого. Крім цього, так званого кількісного аналізу, потрібен і абсолютний аналіз, пов’язаний із обґрунтуванням оптимальності розв’язку проблеми. Інакше кажучи, абсолютний аналіз дозволяє встановити, коли наш алгоритм настільки гарний, що неможливо (незалежно від наших розумових здібностей) значно його покращити). Отже, необхідні чіткі критерії оцінки алгоритму.

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

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

Функцію f(n) визначимо як О[g(n)] і будемо говорити, що вона є функцією порядку g(n) для великих п, якщо

.

Будемо використовувати позначення f(n) = 0[g(n)].

Функцію f(n) визначимоо[g(n)] для великих n, якщо

.

Ці символи вимовляються відповідно, як «О велике» і «о ма­леньке». Інтуїтивно, якщо f(n) є 0[g(n)], то ці дві функції, по суті, зростають з однаковою швидкістю при n . Якщо f(n) є o[g{n)], то g(n) зростає значно швидше, ніж f(n).

Наприклад, поліном f(n) = 2n5+6n4+6n2+18 є O(n5), тому що , о(n5,1), о(еn), о(2n) і «о маленьким» від будь-якої функції, що зростає швидше, ніж поліном п’ятого ступеня. Функція f(n)=2n є о(n!), тому що . Однак 2n є 0(2n + 1) і о(5n-1). Функція f(n) = 1000 є о(n).

Отже, алгоритм поліноміальний, якщо fA(n) = 0(Pk (n)) або fA(n) = o(Pk(n)), де Рk(п) – деякий поліном від змінної п довільного фіксованого ступеня k. В супротивному випадку алгоритм є експоненціальним.

Очевидно, ми краще б уя­вляли дії алгоритму A, якби знали, що fA (n) = 2.5n2+3.7п-5.2, ніж якби нам було відомо тільки, що fA (n) = 0(n2). Але точні коефіцієнти fA (n) в загальному випадку залежать від реалізації, тоді як характеристика 0(n2) загалом властива алгоритму і не залежить від особливостей реалізації. Стосовно експоненціальних алгоритмів важливо знати також, що їх оцінка скажімо 0(2n), а не О(n!) чи О(nn). На жаль для багатьох практично важливих проблем відомі тільки експоненціальні алгоритми, серед них і задача комівояжера. Зазначимо, що ETS – експоненціальний алгоритм з оцінкою принаймні О(n!). Дійсно, число перестановок (п-1)!, що навіть за умови тільки одного кроку для кожної з них (груба недооцінка), буде вимагати 0(п-1)! кроків. Якщо для кожної перестановки можна знайти відповідний тур і його вартість за О(n) кроків, то будемо мати для будь-якої верхньої межі для загального часу роботи принаймні О(n!).

Для задачі комівояжера на 20 міст, припустивши існування феноменального алго­рит­му для кроку 1, який генерує нову перестановку тільки за один крок, і використання комп’ю­тера, який виконує кожний елементарний крок (наприклад, порівняння, додавання, пошук елементу матриці) за 10-7 с, розв’язок з застосуванням алгоритму ETS буде отримано трохи менше ніж за 70 століть, тому що 20!  2 1018.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]