Cel mai bun răspuns
Clasificare după scop
Fiecare algoritm are un scop, de exemplu, scopul algoritmului de sortare rapidă este de a sorta datele în ordine crescătoare sau descendentă. Dar numărul de obiective este infinit și trebuie să le grupăm în funcție de scopuri.
Clasificare după implementare
Un algoritm poate fi implementat în conformitate cu diferite principii de bază.
- Recursiv sau iterativ Un algoritm recursiv este acela care se numește în mod repetat până când o anumită condiție se potrivește. Este o metodă comună programării funcționale. Algoritmii iterativi folosesc constructe repetitive, cum ar fi bucle. Unele probleme sunt mai potrivite pentru o implementare sau alta. De exemplu, turnurile problemei hanoi este bine înțeleasă în implementarea recursivă. Fiecare versiune recursivă are un iterativ echivalent iterativ și invers.
- Logic sau procedural Un algoritm poate fi privit ca deducție logică controlată. O componentă logică exprimă axiomele care pot fi utilizate în calcul și o componentă de control determină modul în care deducția este aplicată axiomelor. Aceasta este baza programării logice. În limbajele de programare logică pură, componenta de control este fixă și algoritmii sunt specificați furnizând doar componenta logică.
- Serial sau parallel Algoritmii sunt de obicei discutați cu presupunerea că computerele execută o instrucțiune a unui algoritm la un moment dat. Acesta este un algoritm serial, spre deosebire de algoritmi paraleli, care profită de arhitecturile computerului pentru a procesa mai multe instrucțiuni simultan. Ei împart problema în subprobleme și le transmit mai multor procesoare. Algoritmii iterativi sunt în general paralelizabili. Algoritmii de sortare pot fi paralelați eficient.
- Deterministic sau nedeterminist Algoritmii deterministi rezolvă problema cu un proces predefinit, în timp ce algoritmul nedeterminist trebuie să efectueze presupuneri despre cea mai bună soluție la fiecare etapă prin utilizarea euristicii.
Clasificare după paradigma de proiectare
O paradigmă de proiectare este un domeniu în cercetare sau clasă de probleme care necesită un tip dedicat de algoritm:
- Divide and conquer Un algoritm de divizare și cucerire reduce în mod repetat o instanță a unei probleme la una sau mai multe instanțe mai mici ale aceleiași probleme (de obicei recursiv), până când instanțele sunt suficient de mici să rezolve cu ușurință. Un astfel de exemplu de divizare și cucerire este sortarea prin îmbinare. Sortarea se poate face pe fiecare segment de date după împărțirea datelor în segmente și sortarea datelor întregi poate fi obținută în faza de cucerire prin combinarea acestora. Algoritmul de căutare binară este un exemplu de variantă de divizare și cucerire numită algoritm de scădere și cucerire , care rezolvă o subproblemă identică și utilizează soluția acestei subprobleme problema mai mare.
- Programare dinamică Cea mai scurtă cale dintr-un grafic ponderat poate fi găsită utilizând cea mai scurtă cale către obiectiv din toate cele adiacente vârfuri. Când soluția optimă pentru o problemă poate fi construită din soluții optime la subprobleme, utilizarea programării dinamice evită soluțiile recomputate care au fost deja calculate. – Principala diferență cu abordarea „împărțiți și cuceriți” este că subproblemele sunt independente în diviziune și cucerire, unde pe măsură ce suprapunerea subproblemelor apare în programarea dinamică. – Programarea dinamică și memoizarea merg împreună. Diferența cu recursivitatea simplă constă în memorarea în cache sau memorarea apelurilor recursive. Acolo unde subproblemele sunt independente, acest lucru este inutil. Utilizând memoizarea sau menținând un tabel de subprobleme deja rezolvate, programarea dinamică reduce natura exponențială a multor probleme la complexitate polinomială.
- Metoda lacomă Un algoritm lacom este similar cu un algoritm de programare dinamică, dar diferența este că soluțiile la subprobleme nu trebuie să fie cunoscute în fiecare etapă. În schimb, se poate face o alegere „lacomă” a ceea ce pare cea mai bună soluție pentru moment. Cel mai popular algoritm lacom constă în găsirea arborelui de întindere minim, așa cum este dat de Kruskal.
- Programare liniară Problema este exprimată ca un set de liniare inegalități și apoi se încearcă maximizarea sau minimizarea intrărilor. Acest lucru poate rezolva multe probleme, cum ar fi debitul maxim pentru graficele direcționate, în special prin utilizarea algoritmului simplex.O variantă complexă a programării liniare se numește programare întreagă, în care spațiul soluției este limitat la toate numerele întregi.
- Reducere numită și transformă și cucerește Rezolvă o problemă transformând-o într-o altă problemă. Un exemplu simplu: găsirea medianei într-o listă nesortată înseamnă mai întâi transpunerea acestei probleme în problemă de sortare și găsirea elementului de mijloc din lista sortată. Scopul principal al reducerii este găsirea celei mai simple transformări posibile.
- Utilizarea graficelor Multe probleme, cum ar fi jocul de șah, pot fi modelate ca probleme pe grafice. Se utilizează algoritmi de explorare a graficelor. Această categorie include, de asemenea, algoritmii de căutare și backtracking.
- Paradigma probabilistică și euristică Probabilistic Cei care fac unele alegeri la întâmplare. Genetic Încercați să găsiți soluții la probleme prin imitarea proceselor biologice evolutive, cu un ciclu de mutații aleatorii care generează generații succesive de „soluții”. Astfel, ele imită reproducerea și „supraviețuirea celui mai potrivit”. Euristic Al cărui scop general nu este să găsească o soluție optimă, ci o soluție aproximativă în care timpul sau resursele pentru a găsi o soluție perfectă nu sunt practice.
Clasificare după complexitate
Unii algoritmi se completează în timp liniar, iar unii se completează în timp exponențial și unele nu se completează niciodată.
Sursa: Clasificarea algoritmilor
Învățare supravegheată: clasificare
Răspuns
Următorul este un alt mod de clasificare a algoritmilor.
În programarea competitivă, există 4 probleme principale- paradigme de rezolvare.
Cu alte cuvinte, având în vedere o problemă, iată diferitele abordări / instrumente pe care ar trebui să le luați pentru a o rezolva.
- Forță brută / Căutare completă: O metodă care analizează toate posibilitățile și selectează cea mai bună soluție.
- Pro: simplu, ar trebui să găsească întotdeauna soluția, deoarece căutați toate posibilitățile
- Contra : infezabil ca numărul de posibilități crește exponențial pe măsură ce numărul de elemente crește
- Divide and Cucer: Metodă care împarte problema în părți mai mici și apoi rezolvă aceste părți. Gândiți-vă la căutarea binară.
- Abordare lacomă: Metodă care alege cea mai bună opțiune la momentul actual, fără nicio considerație pentru viitor.
- Pro: rapid, simplu, poate obține cea mai bună soluție sau se apropie cam
- Contra: de cele mai multe ori, nu vom obține cea mai bună soluție
- Programare dinamică: Metodă care creează o soluție utilizând sub-soluții găsite anterior. Cu siguranță una dintre tehnicile mai avansate, dar extrem de puternică și aplicabilă.
- Pro: găsește soluția optimă pentru multe probleme în timp polinomial ( întrucât forța brută ar lua exponențial)
- Contra : dificil de înțeles și aplicat, necesită timp pentru a înțelege diferitele stări și recurență
Surse
Halim, Steven și Felix Halim. Programare competitivă: noua limită inferioară a concursurilor de programare . Lulu, 2013.