Appunti Corso Algoritmi e Programmazione

01.ALGORITMI E CLASSI DI PROBLEMI

Algoritmo: sequenza finita di istruzioni per risolvere un problema.

Tipologie di Problemi:

• Decisione: nei quali la risposta è binaria (si o no).

o Decidibili: esiste algoritmo risolutivo.

▪ Trattabili: risolvibili in tempo ragionevole. Allora esiste un algoritmo polinomiale in

grado di risolvere questa sottocategoria di problemi (tesi di Edmonds-Cook-Karp).

Questi problemi si dicono di classe P.

▪ Intrattabili: non risolvibili in tempo ragionevole. [Torri di Hanoi per n elevato].

Solitamente in questa categoria ricadono quelli di classe NP.

o Indecidibili: non esiste algoritmo risolutivo. [congettura di Goldbach]

• Ricerca: nei quali si cerca la soluzione valida tra le n soluzioni possibili [n=0,1,…infinito].

• Verifica: nei quali si stabilisce se la risposta data sia valida.

• Ottimizzazione: nei quali si cerca la soluzione migliore ad un dato problema.

Classi di Problemi:

• P: sono problemi Polinomiali.

• NP: sono problemi Non-deterministico Polinomiali, ovvero

quelli per i quali non si può escludere che vi sia una

soluzione polinomiale anche se non si sia ancora trovata.

• NP-Completo: sono problemi costruiti in modo tale che

ogni altro problema NP sia riducibile ad esso attraverso

trasformazioni polinomiali.

• NP-Hard: un problema è di questa classe se ogni problema

NP è riducibile ad esso in tempo polinomiale.

02.ANALISI DI COMPLESSITA DEGLI ALGORITMI

Analisi di Complessità: indipendentemente dalla macchina e dalla tipologia o contenuto dei dati, è la

previsione delle risorse richieste dall’algoritmo per la sua esecuzione, tramite metodi empirici e analitici.

Classificazione degli Algoritmi:

•