Migliore risposta
Classificazione per scopo
Ogni algoritmo ha un obiettivo, ad esempio, lo scopo dellalgoritmo di ordinamento rapido è ordinare i dati in ordine crescente o decrescente. Ma il numero di obiettivi è infinito e dobbiamo raggrupparli in base al tipo di finalità.
Classificazione per implementazione
Un algoritmo può essere implementato secondo diversi principi di base.
- Ricorsivo o iterativo Un algoritmo ricorsivo è uno che chiama se stesso ripetutamente finché una certa condizione non corrisponde. È un metodo comune alla programmazione funzionale. Gli algoritmi iterativi utilizzano costrutti ripetitivi come i cicli. Alcuni problemi sono più adatti per unimplementazione o per laltra. Ad esempio, il problema delle torri di hanoi è ben compreso nellimplementazione ricorsiva. Ogni versione ricorsiva ha un equivalente iterativo iterativo e viceversa.
- Logico o procedurale Un algoritmo può essere visto come una deduzione logica controllata. Una componente logica esprime gli assiomi che possono essere utilizzati nel calcolo e una componente di controllo determina il modo in cui la deduzione viene applicata agli assiomi. Questa è la base della programmazione logica. Nei linguaggi di programmazione logica pura il componente di controllo è fisso e gli algoritmi vengono specificati fornendo solo il componente logico.
- Seriale o parallelo Gli algoritmi vengono solitamente discussi assumendo che i computer eseguano unistruzione di un algoritmo alla volta. Questo è un algoritmo seriale, al contrario degli algoritmi paralleli, che sfruttano le architetture dei computer per elaborare più istruzioni contemporaneamente. Dividono il problema in sotto-problemi e li passano a diversi processori. Gli algoritmi iterativi sono generalmente parallelizzabili. Gli algoritmi di ordinamento possono essere parallelizzati in modo efficiente.
- Deterministico o non deterministico Gli algoritmi deterministici risolvono il problema con un processo predefinito mentre lalgoritmo non deterministico deve eseguire ipotesi della migliore soluzione in ogni fase attraverso luso delleuristica.
Classificazione per paradigma di progettazione
Un paradigma di progettazione è un dominio di ricerca o una classe di problemi che richiede un tipo di algoritmo dedicato:
- Dividi e conquista Un algoritmo di divisione e conquista riduce ripetutamente unistanza di un problema a una o più istanze più piccole dello stesso problema (di solito in modo ricorsivo), finché le istanze non sono abbastanza piccole da risolvere facilmente. Uno di questi esempi di divide et impera è lordinamento di unione. Lordinamento può essere effettuato su ogni segmento di dati dopo aver diviso i dati in segmenti e lordinamento di interi dati può essere ottenuto in fase di conquista unendoli. Lalgoritmo di ricerca binaria è un esempio di una variante di divide et impera chiamata algoritmo di decremento e conquista , che risolve un sottoproblema identico e utilizza la soluzione di questo sottoproblema per risolvere il problema più grande.
- Programmazione dinamica Il percorso più breve in un grafico ponderato può essere trovato utilizzando il percorso più breve per lobiettivo da tutti gli adiacenti vertici. Quando la soluzione ottimale a un problema può essere costruita da soluzioni ottimali a sottoproblemi, lutilizzo della programmazione dinamica evita di ricalcolare soluzioni che sono già state calcolate. – La principale differenza con lapproccio “divide et impera” è che i sottoproblemi sono indipendenti in divide et impera, mentre la sovrapposizione dei sottoproblemi si verifica nella programmazione dinamica. – La programmazione dinamica e la memorizzazione vanno insieme. La differenza con la ricorsione diretta è nella memorizzazione nella cache o nella memoizzazione delle chiamate ricorsive. Quando i sottoproblemi sono indipendenti, questo è inutile. Utilizzando la memoizzazione o mantenendo una tabella di sottoproblemi già risolti, la programmazione dinamica riduce la natura esponenziale di molti problemi alla complessità polinomiale.
- Il metodo avido Un algoritmo avido è simile a un algoritmo di programmazione dinamica, ma la differenza è che le soluzioni ai sottoproblemi non devono essere conosciute in ogni fase. Invece una scelta “avida” può essere fatta su quella che sembra la migliore soluzione per il momento. Lalgoritmo avido più popolare è trovare lo spanning tree minimo fornito da Kruskal.
- Programmazione lineare Il problema è espresso come un insieme di disuguaglianze e quindi si tenta di massimizzare o minimizzare gli input. Questo può risolvere molti problemi come il flusso massimo per i grafi diretti, in particolare utilizzando lalgoritmo simplex.Una variante complessa della programmazione lineare è chiamata programmazione intera, dove lo spazio della soluzione è limitato a tutti i numeri interi.
- Riduzione chiamata anche trasforma e conquista Risolvi un problema trasformandolo in un altro problema. Un semplice esempio: trovare la mediana in un elenco non ordinato significa prima tradurre questo problema in un problema di ordinamento e trovare lelemento centrale in un elenco ordinato. Lobiettivo principale della riduzione è trovare la trasformazione più semplice possibile.
- Utilizzo di grafici Molti problemi, come giocare a scacchi, possono essere modellati come problemi sui grafici. Vengono utilizzati algoritmi di esplorazione del grafico. Questa categoria include anche gli algoritmi di ricerca e il backtracking.
- Il paradigma probabilistico ed euristico Probabilistico Quelli che fanno alcune scelte in modo casuale. Genetica Tenta di trovare soluzioni ai problemi imitando i processi evolutivi biologici, con un ciclo di mutazioni casuali che producono generazioni successive di “soluzioni”. Così, emulano la riproduzione e la “sopravvivenza del più adatto”. Euristico Il cui scopo generale non è trovare una soluzione ottimale, ma una soluzione approssimativa in cui il tempo o le risorse per trovare una soluzione perfetta non sono pratici.
Classificazione per complessità
Alcuni algoritmi vengono completati in tempo lineare e altri in una quantità esponenziale di tempo e alcuni non vengono mai completati.
Fonte: Classificazione degli algoritmi
Apprendimento supervisionato: classificazione
Risposta
Il seguente è un altro modo per classificare gli algoritmi.
Nella programmazione competitiva, ci sono 4 problemi principali: risolvere i paradigmi.
In altre parole, dato un problema, ecco i diversi approcci / strumenti che dovresti adottare per risolverlo.
- Forza bruta / Ricerca completa: un metodo che esamina tutte le possibilità e seleziona la soluzione migliore.
- Pro: semplice, dovresti sempre trovare la soluzione dato che stai esaminando ogni possibilità
- Contro : irrealizzabile come numero di possibilità cresce in modo esponenziale allaumentare del numero di elementi
- Dividi e conquista: metodo che divide il problema in parti più piccole e poi risolve quelle parti. Pensa alla ricerca binaria.
- Approccio avido: metodo che sceglie lopzione migliore al momento attuale, senza alcuna considerazione per il futuro.
- Pro: veloce, semplice, può ottenere la soluzione migliore o avvicinarsi un po
- Contro: la maggior parte delle volte non otterremo la soluzione migliore
- Programmazione dinamica: Metodo che si basa su una soluzione utilizzando sotto-soluzioni trovate in precedenza. Sicuramente una delle tecniche più avanzate, ma estremamente potente e applicabile.
- Pro: trova la soluzione ottimale a molti problemi in tempo polinomiale ( considerando che la forza bruta richiederebbe esponenziale)
- Contro : difficile da comprendere e applicare, richiede tempo per comprendere i vari stati e ricorrenza
Fonti
Halim, Steven e Felix Halim. Programmazione competitiva: il nuovo limite inferiore dei concorsi di programmazione . Lulu, 2013.