Algoritmi

a.a. 2013/14

Classe 2: matricole dispari

Presentazioni

• Marcella Anselmo

• Info: http://www.di.unisa.it/professori/anselmo/

• Orario ricevimento: • Lunedì 15-17 • Giovedì 12-13

• Il mio studio è il n° 57 al 4° piano (5° ed ultimo livello) della Stecca 7 (fra l'aula F8 e la Facoltà di Farmacia).

Pagina del corso

• Pagina del corso: http://www.di.unisa.it/professori/anselmo/algo1314.htm

Troverete: orario lezioni, ricevimento, programma, avvisi, calendario aggiornato via via, slides, prove di esame: date e compiti degli appelli precedenti, syllabus …

Svolgimento del corso 6 CFU di lezione frontale ed esercitazioni = 48 ore

• Il corso prevede 48 ore di lezione frontale che saranno svolte secondo l’orario previsto, oppure in eventuali ore di recupero, di cui si darà notizia in classe e sulla pagina web.

• Inoltre, quest’anno sono previste altre 12 ore di esercitazioni extra, da svolgersi alcuni lunedì dalle 16 alle 18 in aula P3, secondo modalità e in date da stabilire.

• Ultima lezione prevista: 11 dicembre 2013, a meno di…

• Eventuali ore di recupero: 17, 18 dicembre, e venerdì dalle 15 alle 18 in aula P3.

Prerequisiti

Non vi sono propedeuticità formali. Lo studente dovrebbe avere acquisito la capacità di sviluppare ragionamenti di tipo logico. Dovrebbe altresì aver appreso e padroneggiato i concetti di base di un corso introduttivo di Programmazione. Nonché padroneggiare nozioni di Matematica acquisite nei precedenti anni scolastici (logaritmi, diseguaglianze, polinomi, sommatorie,… )

Modalità di frequenza

Lo svolgimento delle esercitazioni e la frequenza del corso sono fortemente consigliate.

Gli studenti devono essere preparati a trascorrere una congrua quantità di tempo nello studio al di fuori delle lezioni.

Come studiare?

• Lezioni (domande «stupide» non esistono)

• Slides, appunti, ma… libri!

• Esercizi (da soli, a gruppi,…); su http://www.di.unisa.it/professori/anselmo/didattica.html

trovate tutte le prove di esame degli anni scorsi

• Ricevimento

• Organizzare gli esami dei vari corsi

• Non dimenticare obiettivi e motivazioni

Libri di testo Il libro di testo di riferimento è:

[KT] Kleinberg, Tardos.

Algorithm Design.

Pearson Addison Wesley.

Purtroppo non è ancora disponibile una versione in italiano.

Altri libri di consultazione sono: [CLR1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduzione agli Algoritmi, prima edizione, McGraw Hill.

[CLRS2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione agli Algoritmi, seconda edizione, McGraw Hill.

[DFI] C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati , Mc-Graw Hill, 2004.

Esami (!) • L’esame consiste di una prova scritta e di una orale (cui si

accede solo dopo il superamento di quella scritta).

• Non sono previste prove intercorso, ma … .

• Gli studenti interessati alle prove di esame devono prenotarsi su Esse3 entro il termine utile. Ricordo inoltre che è possibile e doveroso cancellare la propria prenotazione qualora si decida di non partecipare, per evitare un inutile spreco di risorse.

• Durante lo svolgimento del compito scritto NON è consentito consultare libri, appunti o altro materiale di nessun tipo.

Date esami

• Pre-appello nel periodo 7 - 17 Gennaio 2014.

• Primo appello nel periodo 20 Gennaio 2014 - 7 Febbraio 2014.

• Secondo appello nel periodo 10 - 28 Febbraio 2014.

• Appello straordinario in Aprile 2014.

Attenzione: l’appello è riservato esclusivamente agli studenti

che abbiano conseguito almeno 135 CFU e tutti gli studenti di

ordinamenti disattivati (matr. diverse da 05121). Le

prenotazioni saranno gestite da Esse3.

• Primo appello nel periodo 23 Giugno 2014 –11 Luglio 2014.

• Secondo appello nel periodo 14 – 31 Luglio 2014.

• Appello nel periodo 1 - 19 Settembre 2014.

• Appello straordinario in Novembre 2014?

Tantissime…

Contenuto del corso 1. Introduzione alla analisi asintotica degli algoritmi (6 ore frontali)

2. La tecnica di progetto di algoritmi Divide et Impera e relativi esempi di applicazione: Mergesort, Quicksort; Ricorrenze; Moltiplicazione di interi e matrici. (8 ore frontali).

3. La tecnica di progetto di algoritmi Programmazione Dinamica e relativi esempi di applicazione: Calcolo di numeri di Fibonacci, Combinazioni; Problemi di ottimizzazione: Scheduling di risorse, Zaino intero, Problemi su stringhe, Cammini minimi su grafi. (12 ore frontali).

4. La tecnica di progetto di algoritmi Greedy e relativi esempi di applicazione: Scheduling di intervalli; Scheduling con deadline; Compressione Dati e Codici di Huffman. (8 ore frontali).

5. Algoritmi su grafi. Connettività e visita di grafi; DAG e ordinamento topologico. Calcolo di Cammini Minimi (algoritmo di Dijkstra). Calcolo di alberi ricoprenti minimi (algoritmi di Prim e Kruskal). (8 ore frontali).

6. Calcolo di flusso su grafi e loro applicazioni. (6 ore frontali).

Cos’è un algoritmo?

Primi algoritmi “Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing.”

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms.

Perché studiare algo

C’è pure una conferenza annuale «FUN with algorithms»: http://www.dsi.unive.it/~fun2012/

E ne esistono tantissime altre dedicate agli algoritmi: ESA, SODA,…

Obiettivi

Abbiamo bisogno di algoritmi ogni qual volta vogliamo scrivere un programma.

Obiettivo finale: programmare in maniera consapevole

Dal problema al programma che lo risolve:

1. Formalizzazione del problema

2. Scelta della tecnica per progettare algoritmo

3. Correttezza

4. Analisi risorse usate / efficienza

Riprendiamo il «programma» in breve

1. Analisi asintotica degli algoritmi

2. Tecniche di progetto di algoritmi: Divide et Impera, Programmazione Dinamica, Greedy

3. Algoritmi su grafi.

4. Calcolo di flusso su grafi e loro applicazioni.

Esempio

Problema reale / concreto:

In una scuola c’è 1 sala computer e più classi che vogliono accedervi ognuna in certi orari.

Come accontentare il maggior numero di classi?

Formalizzazione del problema

Problema computazionale: Scheduling di attività

• Input / Dati: S = { 1, 2, … , n } insieme delle classi Per ogni classe i :

• si tempo di inizio • fi tempo di fine

• Output / Soluzione:

S’ sottoinsieme di S di attività compatibili (= orari non si accavallano) tale che Card(S’) massima S’ = soluzione ottimale Card(S’) = valore ottimo

Esempio

1

2

3

4

5

6

9 10 11 12 13 15 16 17 18 19 14

S = {1, 2, 3, 4, 5, 6} s1 = 9, f1 = 12 s2 = 10, f2 = 14 s3 = 13, f3 = 15 ….

Soluzioni ammissibili : S1 = {1, 3, 6} S2 = {1, 6} S3 = {2, 4, 6} S4 = {5}

Soluzioni ottimali: S1 = {1, 3, 6} S3 = {2, 4, 6} Valore ottimo = 3

Varianti

• Nell’input : Scheduling di attività pesato

Ad ogni classe è associato un valore

Cerco S’ il cui valore totale sia massimo (non necessariamente la cardinalità)

• Nell’output

– Cerco soltanto valore ottimo

– Cerco tutti S’

Scelta della tecnica per Scheduling di attività

1) Ricerca esaustiva/ Forza bruta / naif • Considero tutti i sottoinsiemi di S • Per ognuno verifico compatibilità • Fra i sottoinsiemi di attività compatibili restituisco quello di cardinalità

massima Q: Quanti sono tutti i sottoinsiemi di {1, 2, …. , n}? Cardinalità insieme delle parti di {1, 2, …. , n} Quanti sono tutti i sottoinsiemi di {1, 2, …. , 6}? Quante sono le stringhe binarie di lunghezza 6?

{1, 3, 6} 1 0 1 0 0 1

Sono 2n Analisi: il tempo di esecuzione di tale algoritmo è esponenziale! Esponenziale = non accettabile Altra soluzione?

Tecniche di programmazione

2) Programmazione dinamica lo risolve in O(nlogn)

3) Tecnica greedy lo risolve in O(nlog n)

Tempo O(nlog n) è accettabile

Confronto efficienza

n logn vs 2n

Altra soluzione

Grafo della compatibilità: ogni nodo è un intervallo; due nodi collegati se si accavallano

1

2

3

4

5 6

9 10 11 12 13 15 16 17 18 19 14

1 2 3 4

5

6

Soluzione S1 = {1, 3, 6}

Insieme di nodi indipendenti = tale che ogni coppia di nodi NON è collegata

Problema più generale Problema dell’insieme indipendente

Input: grafo

Output: insieme indipendente di cardinalità massima

Una soluzione del problema dell’insieme indipendente

fornisce una soluzione del problema dello scheduling di attività.

Purtroppo però il problema dell’insieme indipendente è un problema «difficile»

Concludendo

• Dal problema reale al problema computazionale

• Bisogna conoscere più tecniche di progettazione di algoritmi

• Necessario saper analizzare l’efficienza

• Dimostrare correttezza

• Molti problemi si possono esprimere con i grafi