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 / 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 è automatizzabile

Definizione Algoritmo

• Sequenza finita
• Stringa separabile (escluse azioni continue)
• di passi discreti
• no ambiguità
• comunicazione precisa
• che permette di risolvere problem

Teoria logica: derivazione logica attraverso una concatenazione

Postulato: verità date per scontato; assunte come auree

Assioma: assunta a fondamento di una teoria; se due assiomi si contraddicono, posso dimostrare qualcosa falsa

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 peggiorie: valuto 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

3n² + n ∈ O(n)

• 3n² < cn
• 3n < c(n-1)
• n < (c-1)/3

NO

3n² + n ∈ Ω (n)

• 3n² > cn
• 3n > c(n-1)
• n > (c-1)/3

SÌ

3n² + n ∈ O(n²)

• 3n² < cn²
• 3 < c

SÌ

3n² + n ∈ Ω (n²)

• 3n² ≥ cn²
• 3 ≤ c - 1/n

SÌ

n³ cresce più rapidamente di n, quindi non potrae mai essere minore

• Ο limitazione inferiore
• Ω limitazione superiore

ALGORITMO

DESCRIZIONE PRECISA DELLE AZIONI DA SVOLGERE PER RISOLVERE UN PROBLEMA DI QUALSIASI GENERE.

• PROBLEMA
• PROCEDIMENTO
• AGENTE DI CALCOLO

PASSI INDICAZIONI DA ESEGUIRE - UNITÀ ESEGUIBILI

AMBIENTE DI CALCOLO AMBIENTE IN CUI SI OPERA (NUMERI…)

SEQUENZA FINITA DI PASSI DISCRETI NON AMBIGUI CHE PERMETTE LA RISOLUZIONE DI UN PROBLEMA

1. LUNGHEZZA FINITA
   • Sequenza finita di passi elementari tra loro distinti
2. STRUTTURA IN PASSI DISCRETI
   • DISCRETI: separabili, distinti, non continui. Nozioni certe
3. NON AMBIGUITÀ
   • Passi devono essere comprensibili per l'agente di calcolo. Comunicazione PRECISA. Si deve ottenere una sola tra le scelte possibili.
4. NON CASUALITÀ
   • Risultato è CERTO e RIPETIBILE
5. DETERMINISMO
   • DOVER EFFETTUARE UNA SOLA TRA LE SCELTE POSSIBILI

Per descrivere un algoritmo è necessario utilizzare un LINGUAGGIO FORMALE.

COMPLESSITÀ COMPUTAZIONALE CONCRETA

STUDIA EFFICIENZA DEGLI ALGORITMI E IL COSTO DELLA RISOLUZIONE DEI PROBLEMI

DATO UN PARTICOLARE PROBLEMA SI ASSOCIA A QUESTO UNA QUANTITÀ, DETTA

DATO UN MODELLO DI CALCOLO CI SONO VARIE QUANTITÀ DETTE MISURE DI COSTO CHE INDICANO QUANTITÀ DI UNA PARTICOLARE RISORSA UTILIZZATA PER RISOLVERE UN’ORA

Tempo di elaborazione, Byte di memoria utilizzati, Numero istruzioni eseguite.

COMPLESSITÀ DI UN ALGORITMO

FUNZIONE CHE ASSOCIA ALLA DIMENSIONE DEL PROBLEMA IL COSTO DELLA SUA RISOLUZIONE IN BASE ALLA MISURA DI COSTO SCELTA. FUNZIONE NON NEGATIVA, NON DECRESCENTE

TUTTAVIA LA COMPLESSITÀ DI UN ALGORITMO PUÒ ESSERE DIPENDENTE OLTRE CHE DALLA DIMENSIONE ANCHE DAL DATO SPECIFICO D’INGRESSO.

UNO STESSO ALGORITMO CON DATI DIVERSI, HA DELLA STESSA DIMENSIONE PUÒ AVERE DIVERSA COMPLESSITÀ A SECONDA DELL’INPUT. SI PARLA QUINDI DI

COMPLESSITÀ NEL CASO PEGGIORE CASO PIÙ SFAVOREVOLE DI TUTTI QUELLI POSSIBILI

COMPLESSITÀ NEL CASO MEDIO MEDIA DEI CASI POSSIBILI

COMPLESSITÀ DEL PROBLEMA

DATO UN PROBLEMA LA COMPLESSITÀ È UNA FUNZIONE CHE ASSOCIA ALLA DIMENSIONE DEL P.

IL MINIMO COSTO DELLA RISOLUZIONE IN BASE AD UNA MISURA DI COSTO SCELTA.

Se la complessità dipende non solo dalla dimensione dei dati in ingresso, ma anche dai dati stessi, si parla di complessità nel caso peggiore o complessità media.

PER DETERMINARE LA COMPLESSITÀ DI UN PROBLEMA, NON POSSO VALUTARE TUTTI ALGORITMI CHE LO RISOLVONO, SCEGLIENDO IL PIÙ EFFICIENTE.

STIMO LA COMPLESSITÀ DI UN PROBLEMA DETERMINANDO FUNZIONI CHE LA LIMITINO DALL’ALTO E DAL BASSO.

Se per un problema P trovo un algoritmo A di complessità f(n) che lo risolve si dice che f(n) È UNA LIMITAZIONE SUPERIORE ALLA COMPLESSITÀ DI P.

Se non si trova nessun algoritmo con complessità minore di g(n) che risolve il problema P, g(n) È UNA LIMITAZIONE INFERIORE ALLA COMPLESSITÀ DI P.

Se per uno stesso problema P, f(n) e g(n) sono una limitazione superiore ed una inferiore della complessità di P, allora la complessità di P è θ(f(n)).

ALBERO BINARIO DI RICERCA

ALBERO IN CUI OGNI NODO HA AL PIÙ 2 FIGLI

OGNI NODO CONTIENE UNA CHIAVE CON EVENTUALI INFORMAZIONI ASSOCIATE

ORDINAMENTO TOTALE → PROPRIETÀ PER LA QUALE DATE DUE CHIAVI POSSO STABILIRE QUALE MAGGIORE/MINORE

LE CHIAVI DEVONO ESSERE ORDINABILI (NUMERI, BANALER, ALFABETO, COMPLESSO)

LA CHIAVE PRESENTE IN OGNI NODO DELL'ALBERO

• SEGUE TUTTE LE CHIAVI DEL SOTTOALBERO SINISTRO
• PRECEDE TUTTE LE CHIAVI DEL SOTTOALBERO DESTRO

STRUTTURA CHE PERMETTE DI MANTENERE COMPLESSITÀ O(log n) DI RICERCA E

RENDERE EFFICIENTI ALGORITMI DI INSERZIONE E CANCELLAZIONE.

→RICERCA IN ALBERI BINARI

SIMILE A RICERCA BINARIA IN UN ARARY

CONTROLLO RADICE → RESTRINGO RICERCA IN SOTTOALBERO DESTRO O SINISTRO

COMPLESSITÀ DIPENDE DALLA STRUTTURA DELL'ALBERO

CASO PEGGIORE ALBERO TOTALMENTE SBILANCIATO

RELAZIONE DI RICORRENZA PER IL COSTO

DI RICERCA IN UN ALBERO CON n CHIAVI

CIOÈ CAMMINO PIÙ LUNGO DELL’ALBERO

PROFONDITÀ MASSIMA

CASO MEDIO ALBERO QUASI PERFETTAMENTE BILANCIATO, OGNI NODO CONTENGA QUASI

LO STESSO NUMERO DI NODI (SOLO SE I VALORI DELLE CHIAVI SONO BEN DISTRIBUITI)

PER OGNI NODO CALCOLO LA MEDIA DELLE LUNGHEZZE DEL CAMMINO

O(log n)

→INSERZIONE IN ALBERI BINARI

SE ALBERO VUOTO COSTRUISCO UNA FOGLIA

SE ELEMENTO > RADICE SOTTOALBERO A SINISTRA, SE < RADICE A DESTRA

COMPLESSITÀ DIPENDE DALLA STRUTTURA

CASO PEGGIORE ALBERO TOTALMENTE SBILANCIATO O(n)

CASO MEDIO VALORI DELLE CHIAVI BEN DISTRIBUITI O(log n)

→CANCELLAZIONE IN ALBERI BINARI

LA COMPLESSITÀ VARIA A SECONDA DEI CASI, DATO IL NODO q DA CANCELLARE CI SONO 3 CASI

• q È UNA FOGLIA LA CANCELLO O(1)
• q HA UN FIGLIO SOSTITUISCO q CON FIGLIO O(1)
• q HA DUE FIGLI SOSTITUISCO q CON MASS DX O MIN DI DX SE SBILANCIATO O(n)