Quali sono i paradigmi algoritmici?

Question

Quali sono i paradigmi algoritmici?

#1 da (9 voti)
#2 da (2 voti)

8

Generalmente parliamo di paradigmi di programmazione come funzionali, procedurali, orientati agli oggetti, imperativi ecc., ma cosa dovrei rispondere quando mi verranno chiesti i paradigmi degli algoritmi?

Ad esempio, Problema del commesso viaggiatore, Algoritmo del percorso più breve di Dijkstra, Algoritmo GCD euclideo, Ricerca binaria, Albero spanning minimo di Kruskal, Paradigmi algoritmici della Torre di Hanoi? O forse i paradigmi sono le strutture dati che userei per progettare questi algoritmi?

algorithms terminology paradigms

posta Vaibhav Agarwal 11.10.2012 - 08:26

fonte

2 risposte

2

Common design Algorithmic Paradigms:

Dividere e conquistare : suddivisione ricorsiva di un problema in due o più sotto-problemi dello stesso (o relativo) tipo.
Programmazione dinamica : scomposizione in una raccolta di sottoproblemi più semplici. Esempio: puzzle Torre di Hanoi
Algoritmo avido : l'euristica di risoluzione dei problemi per rendere la scelta localmente ottimale in ogni fase. Esempio: problema del commesso viaggiatore
Backtracking : è un algoritmo generale per trovare tutte (o alcune) soluzioni per alcuni problemi computazionali Esempio: Sudoku risolto con il backtracking.
Brute Force : una tecnica di risoluzione dei problemi molto generale che consiste nell'elencare sistematicamente tutti i possibili candidati per la soluzione e verificare se ogni candidato soddisfa la dichiarazione del problema.

Puoi trovare il numero di esempi su geeksforgeeks

risposta data 04.02.2016 - 05:01

fonte

Leggi altre domande sui tag algorithms terminology paradigms

Dove si trova il posto migliore per memorizzare il codice su un Mac? [chiuso] Come gestisco un articolo utente che completo, ma con compromessi e necessità di rivisitare?

score 9 · Accepted Answer

I paradigmi algoritmici sono :

General approaches to the construction of efficient solutions to problems

Qualsiasi approccio di base e comunemente usato nella progettazione di algoritmi potrebbe essere considerato un paradigma algoritmico :

Divide and Conquer

Idea: Divide problem instance into smaller sub-instances of the same problem, solve these recursively, and then put solutions together to a solution of the given instance.

Examples: Mergesort, Quicksort, Strassen’s algorithm, FFT.

Greedy Algorithms

Idea: Find solution by always making the choice that looks optimal at the moment — don’t look ahead, never go back.

Examples: Prim’s algorithm, Kruskal’s algorithm.

Dynamic Programming

Idea: Turn recursion upside down.

Example: Floyd-Warshall algorithm for the all pairs shortest path problem.

La parola paradigma si traduce in esempio, ma non è così che viene utilizzato in un contesto scientifico . I tuoi esempi sono tutti esempi di algoritmi (eccetto il problema del commesso viaggiatore, che è un problema NP-difficile), nessuno dei quali è abbastanza banale da essere considerato un paradigma algoritmico.