Algoritmi

a.a. 2014/15

Classe 2: matricole dispari

Presentazioni

• Marcella Anselmo

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

• Orario ricevimento: • Lunedì 14:30-16:30 • Giovedì 11-12

• Il mio studio è il n° 57 al 4° piano (ultimo piano) della Stecca 7 (fra l'aula F8 e Farmacia).

Pagina del corso

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

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

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.

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

• Eventuali ore di recupero: 16, 17 dicembre, e lunedì dalle 15 alle 18 in aula F8 o lab P13.

Prerequisiti

Non vi sono propedeuticità formali, ma….. Lo studente dovrebbe avere acquisito la capacità di sviluppare ragionamenti di tipo logico (teorema, ipotesi, tesi, dimostrazioni per assurdo, induzione..) Dovrebbe altresì aver appreso e padroneggiato i concetti di base di un corso introduttivo di Programmazione. (cicli, iterazione, ricorsione?,…) 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 brevi test di valutazione dell’apprendimento (per me, per voi).

• 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

1. Pre-appello nel periodo 7 - 16 Gennaio 2015: 15 gennaio ore 15 aula P4. 2. Primo appello nel periodo 19 Gennaio 2015 - 6 Febbraio 2015: 29 gennaio ore 15 aula P4. 3. Secondo appello nel periodo 9 - 27 Febbraio 2015: 19 febbraio ore 15 aula P4. 4. Appello straordinario nel periodo 8 – 21 Aprile 2015. Attenzione: l’appello è riservato esclusivamente (è inutile chiedere) 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. Gli studenti sono pregati di portare con sé un certificato attestante il numero di CFU conseguite. 5. Primo appello nel periodo 22 Giugno 2014 –10 Luglio 2015. 6. Secondo appello nel periodo 13 – 31 Luglio 2015. 7. Appello nel periodo 1 - 19 Settembre 2015. 8. Appello straordinario in Novembre 2015.

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.

La frittata con le uova…. Un algoritmo è un procedimento per risolvere un problema mediante una sequenza finita di operazioni elementari. Il procedimento deve essere descritto in maniera precisa e univoca allo scopo di essere eseguito automaticamente dall’esecutore.

Input: 4 uova Output: una frittata Ricetta: 1. Rompere le uova 2. Sbattere le uova 3. Cuocere

Posso eseguire questa ricetta senza pensarci? Questo è un algoritmo? Non proprio! Non è un metodo generale, una ricetta per ogni frittata (la frittata secondo Marcella è un input particolare). Algoritmo per moltiplicare due numeri (non 4+5) Accendere fornello, prendere padella, … Separare gusci, aggiungere sale etc, cuocere come? L’esecutore sa rompere le uova?

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

Perché studiare algo

C’è pure una conferenza annuale «FUN with algorithms»: http://www.di.unipi.it/fun14/

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

In pratica

Il nostro obiettivo sarà: risolvere un problema (reale, computazionale)

Nostro compito: Progettare un algoritmo che lo risolva

Tre aspetti importanti della soluzione:

1. Tempo impiegato

2. Costo delle risorse (memoria)

3. Qualità : funziona bene? Sempre?

Se non mi fossi spiegata bene….

• Guardiamoci un breve video (un po’ più incisivo….)

Morale

Obiettivo: risolvere un problema (reale, computazionale)

Nostro compito: Progetto di un algoritmo che lo risolva

Tre aspetti importanti della soluzione:

1. Tempo impiegato: analisi T(n)

2. Costo delle risorse (memoria): analisi S(n)

3. Correttezza : funziona bene? Sempre?

Nota: si può applicare anche al vostro obiettivo: Laurea!

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.

Problemi…

Un algoritmo risolve un problema, ma…

… cos’è un problema?

Un sempio

Problema reale / concreto:

Scheduling di attività:

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: è definito da input e output

Esempio (continua)

• 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

accettabile non accettabile

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 (tempo/spazio)

• Dimostrare correttezza

• Molti problemi si possono esprimere con i grafi

Ascoltate «Digito ergo sum» http://digitoergosum.unimi.it/static/media/digitoergosum-3.mp3