Appunti Algoritmica

Algoritmica 24. 02. 15

L’algoritmo deriva dal nome di un matematico arabo.

Lessico: arte di gestire lemmi e forme.

Lemma: voce canonica che si trova su vocabolario (leggere - casa - parlare).

Forma: tutte le declinazioni/le flessioni di un lemma.

Sintassi: livello in cui si guarda se la forma logica di una frase è costruita in maniera corretta.

Semantica: solo con forma sintetica corretta posso valutare la semantica... non è autocontrollabile, necessaria conoscenza più complessa.

Definizione algoritmo

Sequenza finita.

Stringa di passi discreti.

• Separabili (esclusa azione continua).
• Non ambigui.
• Comunicazione precisa.
• Che permette di risolvere problemi.

Teoria logica

Derivazione logica attraverso una concatenazione.

Postulato: verità date per scontato, assunte come ovvie.

Assioma: assunte a fondamento di una teoria, se due assiomi si contraddicono posso dimostrare qualsiasi cosa.

Corollario: semplice conseguenza del teorema dimostrato.

Lemma: teorema dimostrato allo scopo di semplificare la dimostrazione di un teorema successivo.

Complessità computazionale concreta 25.02.15

Complessità dipendente dai dati.

Complessità, nel caso peggiore: valuto il costo maggiore, possono essere molto diverse.

Complessità media.

La complessità può essere maggiorata o minorata.

La complessità dipende dalla limitazione imposta dall'output/dalla dimensione dell'input.

Sta a metà tra limitazione inferiore e superiore ogni volta che trovo algoritmo la complessità varia.

NB: la limitazione inferiore ≠ caso peggiore (complessità).

Algoritmica 24.02.15

L’algoritmo deriva dal nome di un matematico arabo.

Lessico: arte di gestire lemmi e forme.

Lemma: voce canonica che si trova su vocabolario (leggere - casa - parlare).

Forma: tutte le declinazioni / flessioni di un lemma.

Sintassi: livello in cui si guarda se la forma logica di una frase è costruita in maniera corretta.

Semantica: solo con forma sintattica corretta posso valutare la semantica. Non è autocontrollabile, necessaria conoscenza più complessa.

Definizione algoritmo

Sequenza finita.

Stringa di passi discreti.

• Separabili (escluse azioni continue).
• Non ambigui.
• Comunicazione precisa.
• Che permette di risolvere problemi.

Teoria logica

Dimostrazione logica attraverso una concatenazione.

Postulato: verità data per scontato, assunta come ovvia.

Assioma: assioma di fondamento di una teoria, se due assiomi si contraddicono posso dimostrare qualsiasi cosa.

Corollario: semplice conseguenza del teorema dimostrato.

Lemma: teorema dimostrato allo scopo di semplificare la dimostrazione di un teorema successivo.

Complessità computazionale concreta 25.02.15

Complessità dipendente dai dati.

Complessità nel caso peggiore: valutato il costo maggiore, possono essere molto diverse.

Complessità media.

• La complessità può essere maggiorata o minorata.
• La complessità dipende dalla limitazione imposta dall’input, dalla dimensione dell’input.

Sta a metà tra limitazione inferiore e superiore ogni volta che trovo algoritmo la complessità varia.

NB: limitazione inferiore ≠ caso peggiore (complessità).

Esempio

(p. 22)

3n² + n ∈ Θ(n)

3n² + n ∈ O(n)

3n² + n ∈ ω(n)

3n² + n ∈ o(n)

3n² + n ∈ Ω(n²)

n² cresce più rapidamente di n, quindi non potrà mai esistere minore.

O limitazione inferiore.

Ω limitazione superiore.

Approccio divide et impera

Risoluzione di problemi, scindendoli in problemi minori, in parti atomiche.

Atomico: in fisica, legato alla teoria atomica. In informatica, qualcosa che non può essere ulteriormente essere scisso.

• Qualunque problema che non sia di per sé atomico, è divisibile in altri problemi di continuo.
• L'approccio divide et impera divide il problema in sottoproblemi dello stesso tipo.
• Di solito si realizza con un programma ricorsivo.
• A seconda di quanto scende il problema, si riesce a calcolare la complessità.
• La limitazione inferiore è legata alla limitazione della risoluzione del problema.
• Ad esempio torre di Hanoi, se può essere capovolta risolvo problema in 2^n (da piccolo a grande).

Se i sottoproblemi sono io posso dare una comples