Appunti Algoritmica

Algoritmica  24. 02. 15

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: valutò 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

1. La complessità può essere maggiorata o minorata

2. 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.

1. 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.

2. di solito si realizza con un programma ricorsivo.

3. 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