Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- Св-во.
| Видове алгоритми: Според структурата: Неразклонени (линейни), Разклонени (нелинейни) – делят се на циклични и нециклични Според броя на иструкциите: последователни, паралелни
Според спазването на условието за детерминираност – Детерминирани и недетерминирани. Според оптималността на резултата-точни и евристични(приблизителни)Точният алгоритъм дава винаги оптимален резултат. Евристичните алгоритми за дадени входни данни дават резултат близък до оптималният или пък въобще не дава резултат. Примерна задача –свързаност на обекти.Дефиниране на абстрактни операции в задачата.Начален алгоритъм.Алгоритъм за бързо намиране, програмна реализация. Представяне в дърво.Дадена е послед.от цели числа, всяко число представлява някакъв обект. Записът p – q означава p e свързано с q. Връзката е тран-зитивна,т.е ако p - q и q – r, то p - r. Иска се да премахнем ненужните двойки от множ., т.е.когато в прог.се въведе двойка p – q, тя трябва да я изведе само ако според досега въведените двойки p не е свърз. с q. Зад. е да се направи прог.която помни дост. инф. за постъпилите двoйки до момента и може да прецени дали има нова връзка м/у обекти.В зад.се иска да знае дали опр.двойка е свързана,а не да покаже 1 или всички пътища, които я свързват.Намира важни прил.напр. връзки в компютърна,ел.мрежа и др. От теорията на графите => N обекта са свързани ⬄,когато има точно N – 1 изведени двойки в алг.на свързаност. Св-во. Алг.с бързо намиране изпълнява поне MN инструкции,за да реши зад за свърз с N обекта,която вкл. M обединения Намиране и Обединение: След като прочетем нова двойка p – q от входа,изпълн.опер.намиране за всеки член на двойката. Ако те са в едно множество, минаваме на следв.двойка. Ако не са, правим опер.обединение и извежд. двойката Изтегляне 1.47 Mb. Сподели с приятели:
|