Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati Algoritmi e...

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Algoritmi e Strutture Dati con Laboratorio(Modulo I)

Luciano Gualà

[email protected]

http://www.mat.uniroma2.it/~guala/


Copyright © 2004 - The McGraw - Hill Companies, srl2

int InC(int a[], int n){ int i, max; max = a[0]; for (i = 1; i < n; i++) if (a[i] > max) { max = a[i]; } return max;}

public static int InJava (int[] a){int max=a[0];for (int i = 1; i < a.length; i++) if (a[i] > max) max = a[i];return max;

function InPascal(var A: array[1…Nmax] of integer): integer; var k, max: integer;begin max:=A[1]; for k:= 2 to n do begin if A[k]>max then max:=A[k]; end; InPascal:=max;end;



…un possibile pseudo-codice…

Input: Sequenza di n numeri: <a1,a2,…, an>Output: valore massimo della sequenza

max=a1

per ogni i=2,…, nse (ai > max) allora aggiorna max= ai

restituisci max



• Un algoritmo è l’essenza computazionale di un programma, nel senso che fornisce il procedimento per giungere alla soluzione di un dato problema di calcolo

• Algoritmo diverso da programma– programma è la codifica (in un linguaggio di programmazione) di un

algoritmo

– un algoritmo è un programma distillato da dettagli riguardanti il linguaggio di programmazione, ambiente di sviluppo, sistema operativo

Algoritmi e programmi



Insieme di istruzioni, definite passo per passo, in modo da poter essere eseguite meccanicamente e

tali da produrre un determinato risultato

Definizione informale di algoritmo



etimologia

Il termine Algoritmo deriva da Algorismus, traslitterazione latina del nome di un matematico persiano del IX secolo, Muhammad al-Khwarizmi, che descrisse delle procedure per i calcoli matematici



Sequenza di passi ben definita che risolve un problema computazionale

Definizione di algoritmo

La definizione del problema specifica in termini generali la relazione di input/output desiderata



Problema: ricerca del minimo fra n numeri

• Input: una sequenza di n numeri A=<a1,a2,…,an>

• Output: un numero ai tale che ai aj j=1,…,n(stabilisce una relazione tra input e outut)

Minimo (A)

1. min= a1

2. for j=2 to n do

3. if (aj < min) then min=aj

4. return min

Algoritmo (descrive procedura computazionale per realizzare tale relazione)



Strutture dati

– Concetto di algoritmo è inscindibile da quello di dato

– Un algoritmo è una procedura che prende dei dati (input) e, dopo averli elaborati, li restituisce (output)

– I dati devo essere organizzati e strutturati in modo tale che la procedura che li elabora sia “efficiente”



Cosa impareremo?

…ad analizzare e progettare “buoni” algoritmi

…che intendiamo per “buoni”?



Due concetti fondamentali:

Correttezza ed efficienza

Vogliamo progettare algoritmi che:– Producano correttamente il risultato

desiderato

– Siano efficienti in termini di tempo di esecuzione ed occupazione di memoria



Analisi di algoritmi Correttezza:

– dimostrare formalmente che un algoritmo è corretto

– non è sempre facile

– Un algoritmo può essere complesso e/o non intuitivo (ai fini dell’efficienza)

Complessità:

– Stimare la quantità di risorse (tempo e memoria) necessarie all’algoritmo

– Misurata in complessità asintotica

– Non sempre è facile campire quale è la complessità di un algoritmo (es: algoritmi ricorsivi)



Analisi della complessità

– stimare tempo e memoria necessari

– stimare il più grande input gestibile in tempi ragionevoli

– confrontare due algoritmi diversi

– ottimizzare le parti “critiche”



Un’altra cosa che impareremo a fare:

…analizzare problemi (computazionali)

…cosa intendiamo con analizzare un problema?



Formalizzazione di un problema

• Trovare un modello formale/matematico che descrive in modo non ambiguo il problema e renda esplicita la relazione fra input ed output

• Qualche volta piuttosto difficile• Perché formalizzare?

– aiuta a comprendere meglio il problema

– una formalizzazione può suggerire un approccio risolutivo (possibilmente efficiente) per il problema



Formalizzazione: un esempio

• Vogliamo progettare un algoritmo che aiuti la segretaria di dipartimento ad assegnare i corsi ai docenti (lei quando lo fa a mano impiega troppo tempo).

• C’è un insieme di docenti, a ognuno dei quali deve essere assegnato un corso. Un docente sa insegnare solo alcuni corsi.



Una possibile formalizzazione: matching su grafi bipartiti

d1 d2 d3 d4 d5

c1 c2 c3 c4 c5

Grafo bipartitonodi: docenti + corsiarchi: (di,cj) se di sa insegnare cj

docenti

corsi

Trovare insieme di archi che “coprono” tutti i corsi tale che due archi non incidono su uno stesso nodo



Formalizzazione: un altro esempio

• Vogliamo progettare un algoritmo per un correttore ortografico di testi che, data una parola, controlla se essa è scritta bene e in caso di errore suggerisce una possibile correzione



Una possibile formalizzazione• Manteniamo un insieme D di parole dove • D è il nostro dizionario (di parole corrette)• Una parola x è corretta se x D• Definiamo un concetto di distanza tra parole• Se x non è in D, cerco una parola y in D che

minimizza la distanza da x

• Osservazioni:– Distanza fra due parole x e y deve essere piccola

quando x e y sono “simili”– Distanza fra due parole deve poter essere calcolata

(efficientemente)



Analisi di un problema: scoprire proprietà utili

• Scoprire proprietà strutturali di un problema in modo da trarne vantaggio nella progettazione di un algoritmo efficiente



Ragionare sulla complessità di un problema

• Ho progettato un algoritmo per un dato problema che usa una certa quantità di risorse di tempo e spazio

• Posso fare meglio?

• Quanto posso sperare di abbassare la mia complessità?



Prerequisiti del corso

Cosa è necessario sapere…– programmazione di base– strutture dati elementari – concetto di ricorsione– dimostrazione per induzione e calcolo

infinitesimale



Struttura del corso

• Corso strutturato in due moduli– Modulo I (vecchio Elementi di Algoritmi e

Strutture Dati)• 6 CFU• Ottobre – Gennaio

– Modulo II (vecchio Algoritmi e Strutture dati con Laboratorio)

• 6 CFU• Marzo – Giugno



Argomenti (Modulo I)

• Introduzione informale agli algoritmi• Modelli di calcolo e metodoligie di analisi• Strutture dati elementari • Algoritmi di ordinamento• Algoritmi su stringhe• Alberi binari di ricerca• Alberi bilanciati (AVL)



Informazioni utili

• Orario lezioni– Martedì: 12,15 – 14,00– Giovedì: 11,15 – 14,00

• Orario ricevimento– Giovedì: 14,30 – 16,00– Ufficio: dip. di matematica, piano 0, corridoio B0,

stanza 206



Libro di testo

C. Demetrescu, I. Finocchi, G. ItalianoAlgoritmi e Strutture dati

McGraw-Hill

Slide e materiale didattico

http://www.mat.uniroma2.it/~guala/



…altri testi utili…

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. SteinIntroduzione agli algortimi e strutture datiMcGraw-Hill

P. Crescenzi, G. Gambosi, R. GrossiStrutture di dati e algoritmiAddison-Wesley



Modalità d’esame

• L’esame consiste in una prova scritta e un’eventuale prova orale

• Quattro appelli– 2 giugno/luglio– 1 settembre– 1 gennaio/febbraio

• Prova parziale a febbraio• Per sostenere l’esame è obbligatorio prenotarsi

online (una settimana prima) su delphi.uniroma2.it



Buon inizio anno

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati Algoritmi e...

Documents

Transcript of Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati Algoritmi e...