Ефективність алгоритмів в різних випадках

Вступ

Теорія алгоритмів – наука, що вивчає задані властивості закономірності алгоритмів та різноманітні формальні моделі їх представлення.

Ст-ра да-х – спосіб зберігання та організація даних, що полегшує доступ до цих даних і їх модифікацію.

Мета.

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

Задача.

- Ознайомлення з основами теорії алгоритмів, з методами оцінки складності алгоритмів та методами розробки ефективних алгоритмів.

- Дослідження формальних алгоритмічних систем.

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

- Одержання функції трудомісткості з метою порівняльного аналізу алгоритму.

- Ознайомлення з базовими алгоритмами.

МОДУЛЬ 1

Основи аналізу алгоритму

Тема1:Алгоритми та структура даних,основні поняття та види.

1.Вступ.

Розглянемо дві точки зору:

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

· Існують класи задач для яких не має алгоритмів і такі задачі потребують творчого внеску

2. Основні поняття.

Алгоритм:

· Послідовність чітко визначених інструкцій призначених для розв’язку деякої задачі

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

Алгоритм вважається правильним якщо при будь-яких допустимих обставинах він закінчує роботу і видає результат, що задовольняє вимоги задачі.

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

Числовий алгоритм – зводить розв’язання задачі до арифметичних дій над числами.

Логічним алгоритмом – називається алгоритм що містить розпорядження, але стосується не цифр, а об’єктів будь-якої природи.

Виділяють 3 класи алгоритмів:

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

· Інформаційні - представляють собою набір невеликих процедур, фле працюють з великими обсягами інформації.

· Керуючі – дані до них надходять від зовнішніх процесів якими вони керуються.

Способи опису алгоритмів:

· Словесний

· Графічний

· Табличний

· ***Пивдоход***

Виділяють 3 основні процеси оброблення інформації:

· Лінійний

· Циклічний

· Розгалужений

3. Базові Алгоритми

До них відносяться :

· Алгоритми роботи зі ?????????******** - визначають базові принципи і методологію, що використовується для аналізу, реалізації і порівняння алгоритмів:списки,дерева,стеки, черги

· Алгоритми сортування – упорядкування масивів і фактів.

· Алгоритмічний пошук – пошук конкретних елементів у великих колекціях елементів.

· Алгоритми на графах – застосовується для розв’язку складних задач: пошук найкоротшого шляху; побудова лінійного остовного дерева, обхід графів, топологічні сортування.

· Алгоритми обробки рядків – включає методи обробки послідовності *****

· Геометричні алгоритми – методи розв’язування задач з використанням точок, ліній і будь-яких інших геометричних об’єктів.

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

· Детурмінованість- визначення кроків алгоритму, тобто після кожного кроку або зазначається який крок буде наступним або дається команда на зупинку, після чого робота алгоритму вважається ****

· Масовість – алгоритм можна використати для розв’язання цілого типу задач одного типу.

· Результативність – (скінченність,****) – виконання алгоритму настає або закінчується (?*рівнянням*?) або інформацією про те чому не може бути одержаний результат при цьому множина кроків алгоритму є скінченною

· Зрозумілість – алгоритм має бути зрозумілим конкретному виконанню , який повинен виконати кожну команду алгоритму у строгій відповідальності з її призначенням.

· Дискретність – можливість *** алгоритму на скінченну кількість етапів при чому результати попереднього етапу є вхідними для наступного.

5. Основи рішення алгоритмічних задач.

Алгоритм можна вважати процедурним рішенням даних.

Послідовність етапів проектування і аналіз алгоритму.

1)Розуміння задачі

2)Вибір: · Обчислювальні засоби · Точний або наближений розвязок · Стирання даних · Методика проектування алгоритму

3)Розробка алгоритму

6)Реалізація

5)Аналіз алгориму

4)Оцінка коректності

1)Розуміння задачі - ознайомлення з предметною областю. Прорахування декількох прикладів. Виявлення часткових випадків. Перевірка застосування **** алгоритмів.(Якщо є то порівняння переваг та недоліків).

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

Наближений метод вибирається для задач, яких не можна вирахувати ****:квадратний, *** рівняння, визначити інтеграли.

Немає універсальної структури даних її обирають виходячи з предметної області.

3)Поділяється на 2 етапи: Представлення і проектування.

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

4)Доведення, що обраний алгоритм за обмежений проміжок часу видає необхідний результат для будь-яких коректних значеня вхідних даних.

Універсальним методом доведення *** - метод математичної індукції.

5)Оцінка його ефективності: часова і просторова.

Часова – індикатор швидкості алгоритму .

Просторова - кількість додаткової оперативної пам’яті необхідної для роботу алгоритму.

Характеристика алгоритму є його простота.

6)Перенесення алгоритму в (?*конкретну*?) програму.

Основи аналізу

Час виконання алгоритму залежить від розміщення вхідних даних. Тому ефективність алгоритму можна описати як функцію від деякого *** N пов’язаного з розміром вхідних даних. На вибір системи розміру *** можуть впливати дії, які виконує алгоритм.

Часова ефективність визначається як функція від розміру даних шляхом підрахунку області виконаних *тезових* операцій.

Базова операція робить основний внесок в загальний час програми. Зазвичай це операція з найбільшим часом роботи в найбільш глибоко вкладеному циклі.

В залежності від впливу вхідних даних на функцію ефективності алгоритми бувають:

ü Кількісно-залежні по ефективності алгоритми — функція ефективності яких залежить тільки від розмірності вхідних даних і не залежить від їх значень: для операцій з масивами, матрицями.

ü Параметрично залежні по ефективності алгоритми — ефективність яких визначається не розмірністю, а конкретних її значень.

ü Кількісно-параметричні — функції, ефективності яких залежать і від кількості і від значень: алгоритми чисельних методів.

ü Порядково-залежні — належать до параметрично-залежних, але кількість операцій залежить від порядку розташування вхідних даних: пошук мінімуму, максимуму.

Ефективність алгоритмів в різних випадках

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

Ефективність найгіршого випадку — для найгіршої сукупності вхідних даних розміром n, при цьому час роботи виконання алгоритму – найбільший.

Ефективність найкращого випадку — для найкращої сукупності вхідних даних розміром n, при цьому час роботи виконання алгоритму – найменший.

Приклад. Розглянемо задачу послідовності пошуку.

Program search — вхідні дані: масив типу A[0…n-1], ключ k.

Вихідні дані: індекс 1-го елементу масиву А, який = k, або -1, якщо такого числа не знайдено.

i<-0 While I<n and A[i] <> k do I<-i+1 If i<n Return I else return -1

Для даного прикладу найгіршим випадком буде коли шуканий елемент буде на останньому місці, або взагалі немає. C(n) – кількість разів. C_worst( w)= n які виконує алгоритм при своїй роботі.

Найкращий випадок — коли елемент знаходиться на 1му місці. C_best ( n )=1.

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

Припущення: 1) ймовірність успішного пошуку p; 0<=p<=1.

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

Якщо співпадання з ключем знайдено, ймовірність того, що це вийшло саме на і-тому елементі списку = p/n для будь-якого і.

При цьому кількість операцій порівняння які виконує алгоритм =і, якщо спів падання з ключем не знайдено кількість операцій =n, а ймовірність цієї події 1-р.

Якщо р=1(шуканий елемент точно присутній в списку) тоді .

Якщо р=0(шуканий елемент відсутній — найгірший випадок) .

Основні класи ефективності

Клас	Назва	Примітка
1.	Константа	При нескінченному збільшенні розмірів вхідних даних час виконання алгоритму також прямує до нескінченності
Log n	Логарифмічна	Така залежність виникає в результаті зменшення розміру задачі на постійне значення на кожному кроці операції алгоритмів
n	Лінійна	До такого класу належать алгоритми роботи зі списками
n Log n	n Log n	Алгоритми деко…….. (сортування, злиття, швидке сортування)
n²	Квадратична	Два вложених цикли (прості алгоритми сортування, робота з матрицями(?) )
n³	Кубічна	Характеризує ефективність. Три вложених цикли
2ⁿ	Експоненціальна	Така залежність типова для алгоритмів які виконують обробку всіх підмножин деякої множини що містить n елементів
n!	Факторіальна	Обробка перестановок деякої множини що містить n елементів

Тема 2

Структура даних

№1 Класифікація Структури даних

Структура даних поділяється на:

· Прості базові структури

1. Числові

2. Символьні

3. Логічні перелік

4. Інтервал

5. Показчик

· Статичні структури

1. Вектор

2. Масив

3. Множина

4. Запис

5. Таблиця

· Напівстатичні структури

1. Стеки

2. Черги

3. Деки

4. Рейди(?)

· Динамічні структури

1. Лінійні зв’язні списки

2. Розгалуження

3. Зв’язний список

4. Дерева

5. Графи

· Файлові структури

1. Послідовні

2. Прямого доступу

3. Комбінованого доступу

4. Організовані розділами

Структура даних – множина елементів і множина їх зв’язків між ними.

Класифікація структури даних:

ü Фізична – відображає спосіб фізичного подання даних у пам’яті машини і ще називають структурою зберігання внутрішньою структурою або структурою пам’яті.

ü Логічна – структура даних без врахування її подання в машинній пам’яті.

ü Прості (базові, примітивні) і інтегровані (складні, структуровані, композитні)

Прості – не можуть бути розподілені на складові частини більше ніж біти.

Інтегровані – складовими частинами яких є інші структури даних, прості або інтегровані.

ü Залежно від наявності або відсутності явно заданих зв’язків ніж елементи даних розрізняють:

1. Незв’язні (вектори, масиви , рядки стеки, черги)

2. Зв’язні (зв’язні списки)

ü За ознакою можливості зміни розміру (кількості елементів) розрізняють:

1. Статичні (не замінюють розмір під час виконання програми)

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

3. Динамічні (можуть змінювати розмір, для них не відводяться на початку робоча пам’ять)

ü В залежності від упорядкованості структури діляться на лінійні і нелінійні.

ü Залежно від характеру взаємного розташування елементів у пам’яті лінійні розподіляються на : структури з послідовним розподілом елементів у пам’яті (вектори, рядки, масиви, черги) і структури з довільним зв’язним розподілом елементів у пам’яті (однозв’язні та двозв’язні списки).

До нелінійних належать багатозв’язні списки, дерева, *****.

Інформація з кожного типу визначає:

· Структуру зберігання даних зазначеного типу(виділення пам’яті і подання даних у ній та інтерпретацію двійкового подання)

· Множину припустимих значень які може мати об’єкт описуваного типу

· Множину припустимих операцій які застосовні до об’єкту описуваного типу

№2 Операції над структурамими даних

Над будь-якими ст-ми да-х виконують 4 операції:

ü Створення

ü Вибір або доступ

ü Зниження !

ü Відновлення

Тема 4

Дерева

Основні операції з деревами

№1

Дата добавления: 2022-01-22; просмотров: 25; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!