Ateneo - UPO

Metodi di analisi degli algoritmi. Strutture dati fondamentali. Algoritmi fondamentali (ricerca e ordinamento).

Tecniche algoritmiche greedy e programmazione dinamica, nozione di grafo e algoritmi su grafi

Algoritmi e strutture dati 3/ed, Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, MC Graw Hill

oppure in alternativa, per il modulo di Algoritmi 2:

P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi, Seconda edizione, Pearson

oppure Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduzione agli algoritmi e strutture dati, terza edizione, McGraw-Hill, 2010

Il modulo Algoritmi 1 si propone di insegnare a:

• enunciare la definizione delle strutture dati fondamentali essendo in grado di adottarle in problemi proposti;
• analizzare un algoritmo dato, sia esso ricorsivo che iterativo;
• descrivere gli algoritmi di ricerca e di ordinamento, applicare un algoritmo specifico, tra quelli visti, ad un problema dato, darne un'implementazione in C.

Il modulo Algoritmi 2 si propone di:

• introdurre grafi, insegnare come modellare problemi con grafi e fornire strumenti per gestirli;
• insegnare strategie algoritmiche greedy e di programmazione dinamica, e introdurre tecniche di approssimazione di soluzioni di algoritmi di ottimizzazione;
• affinare le capacità nel problem solving e nella valutazione della complessità delle soluzioni.

Prerequisiti formali: Non è possibile accedere alle prove d'esame senza aver già sostenuto e verbalizzato gli esami di Programmazione 1 e Programmazione 2.

Prerequisiti sostanziali: Nozioni di programmazione insegnate nei corsi di Programmazione 1 e 2. Principi e linguaggi di programmazione insegnati nei corsi di semestri precedenti.

Lezioni in aula (eventualmente in modalità blended) e in laboratorio.

Nelle lezioni in aula vengono esposte le nozioni fondamentali, corredate di esempi. Vengono confrontate diverse strutture dati e diversi algoritmi mirati a risolvere problemi della stessa classe. Le dimostrazioni vengono presentate come strumento di analisi del problema per la progettazione degli algoritmi e come strumento di approfondimento delle tecniche, facendo leva sull'analogia tra gli algoritmi che utilizzano una stessa tecnica. Viene discussa l'utilità ai fini pratici dei diversi algoritmi per risolvere specifiche tipologie di problemi. Sulla piattaforma DIR sono indicati i libri di testo suggeriti ed è a disposizione del materiale che ricalca gli argomenti trattati a lezione, risultando di aiuto anche per chi non fosse stato presente. Sono inoltre forniti alcuni esercizi ed esempi di temi d’esame. In laboratorio le persone presenti vengono guidate nell'implementazione degli algoritmi visti a lezione, realizzando per ciascun algoritmo alcune varianti, come esercizio propedeutico all'uso degli algoritmi per la soluzione di problemi. Sul DIR sono a disposizione, per ogni argomento trattato nelle lezioni in laboratorio, delle slide come riferimento e guida sia per chi ha seguito la lezione che per chi era assente.

L'attività in laboratorio richiede una partecipazione attiva e individuale, che consente in tal modo di sviluppare abilità pratiche (le capacità di realizzare un programma). Inoltre, il coinvolgimento attivo induce le persone che seguono a porsi dei quesiti (e spesso di conseguenza a porne alla docente); in tal modo si realizza una regolare verifica del modo in cui gli argomenti vengono recepiti. In aggiunta, le domande poste tramite Wooclap permettono un costante monitoraggio delle difficoltà.

Le persone con disabilità o con Disturbi Specifici dell’Apprendimento (DSA) o con Bisogni Educativi Speciali (BES) possono richiedere servizi e strumenti specifici a loro dedicati rivolgendosi allo Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti e consultando la pagina dedicata del sito di Ateneo: https://uniupo.it/it/servizi/servizi-studenti- disabili-e-dsa Le persone con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo, possono contattare la docente titolare dell'insegnamento in relazione alla declinazione delle modalità di esame, in merito agli aspetti didattici.

La votazione finale si basa sulle conoscenze, competenze e capacità dimostrate in sede d'esame, e viene determinata in modo collegiale, pesando i risultati coerentemente con il numero di CFU di ciascun modulo.

• inferiore a18: Lacune importanti nei contenuti, mancate risposte o risposte non adeguate
• 18–22: Preparazione accettabile, ma con lacune significative o argomenti non studiati adeguatamente. Sufficiente capacità di applicazione. Utilizzo basilare del lessico tecnico
• 23-25: Conoscenze appropriate con alcune lacune, discreta capacità di applicazione; presentazione articolata e utilizzo appropriato del linguaggio tecnico
• 26–28: Buona conoscenza dei contenuti e capacità di stabilire collegamenti fra le diverse parti del programma. Utilizzo solido del linguaggio tecnico.
• 29–30 e lode: Preparazione completa e approfondita, con visione chiara e coerente degli argomenti trattati. Utilizzo preciso del linguaggio tecnico.

Modulo Algoritmi 1:

Teoria: Esame scritto, eventualmente in forma di quiz. Possibilità di orale. I dettagli sono nella parte dedicata allo specifico modulo.

Laboratorio: Esame pratico. L'esame prevede due esercizi in cui si richiede l'implementazione di due programmi in linguaggio C. I dettagli sono nella parte dedicata allo specifico modulo.

La votazione finale terrà conto dei risultati finali ottenuti nelle prove d'esame di Teoria e di Laboratorio, pesando 2/3 la parte di teoria, consistentemente con il numero di crediti erogati.

Modulo Algoritmi 2:

L'esame è orale con una prima parte in laboratorio. I dettagli sono nella parte dedicata allo specifico modulo.

È possibile, in alternativa, svolgere l'esame unicamente tramite quiz a correzione automatica in laboratorio. I dettagli sono nella parte dedicata allo specifico modulo.

Modulo Algoritmi 1:

• Introduzione agli algoritmi.
• Modelli di analisi. notazioni asintotiche (notazioni O, Omega e Theta), limiti inferiori, teorema Master.
• Tipi di dati astratti: pile, code, alberi.
• Algoritmi di ordinamento: insertion sort, selection sort, merge sort, quicksort, heap sort, integer sort, radix sort
• Alberi binari di ricerca. alberi AVL, alberi 2-3.
• Tabelle hash.
• Code con priorità.

Tali aspetti sono poi meglio studiati in pratica durante le esercitazioni tenute in laboratorio. In particolare in laboratorio verranno implementati esercizi relativi ai seguenti argomenti:

• Ricerca binaria e Algoritmi di ordinamento: Insertion sort, selection sort, merge sort, heap sort, quicksort;
• Strutture dati dinamiche: liste, code, pile;
• Strutture dati per problemi di ricerca: alberi binari di ricerca, Tabelle hash.

Modulo Algoritmi 2:

Grafi:

• definizioni e terminologia: grafi non orientati, grafi orientati, archi pesati, cammini, cicli, componenti connesse e fortemente connesse: significato e utilizzo delle diverse varianti per modellare diverse situazioni;
• rappresentazioni di grafi: matrici e liste di adiacenza e loro impatto dal punto di vista dell'implementazione
• visita di grafi in ampiezza e in profondità, caratteristiche comuni e differenze delle varie visite proposte e loro applicazioni

Tecnica golosa (greedy):

• introduzione e algoritmi di esempio;
• cammini minimi su grafo pesato da un nodo sorgente: algoritmo di Dijkstra e applicazioni
• minimo albero ricoprente: algoritmi di Prim e Kruskal e loro utilizzo per risolvere problemi pratici
• tecniche di dimostrazione di correttezza e loro funzione in relazione alla progettazione di algoritmi greedy
• limiti della tecnica golosa

Tecnica di programmazione dinamica

• introduzione alla tecnica e proprietà della sottostruttura ottima; confronto con la tecnica golosa e con il divide et impera
• aspetti e scelte di impementazione: algoritmi ricorsivi e iterativi, memoization
• utilizzo dei teoremi della sottostruttura ottima per l'analisi di problemi e la progettazione di algoritmi di programmazione dinamica; analisi di problemi classici (massimo sottoinsieme indipendente, zaino, sottosequenza comune di lunghezza massima);
• cammini minimi da un nodo sorgente: algoritmo di Bellman-Ford
• cammini minimi da tutti i nodi: algoritmo di Floyd-Warshall

Cenni sui problemi intrattabili:

• classi P, NP ed NP completezza
• algoritmi di complessità pseudopolinomiale
• introduzione alle tecniche per affrontare i problemi difficili.

Conoscenza e capacità di comprensione: familiarità con l’analisi degli algoritmi, delle strutture dati di base, e di algoritmi fondamentali, con particolare riferimento agli algoritmi di ricerca ed ordinamento; familiarità con il concetto di grafo, visita di grafo, tecnica greedy e di programmazione dinamica, e con alcuni problemi classici sui grafi.

Capacità di applicare conoscenza e comprensione:

• sapere applicare le tecniche di analisi negli esercizi,
• saper scrivere un algoritmo fondamentale o una sua variazione ideando soluzioni nuove in maniera tecnicamente corretta.
• modellare problemi utilizzando grafi
• risolvere problemi tramite l'implementazione di algoritmi classici di visita di grafi
• risolvere problemi utilizzando tecniche greedy e di programmazione dinamica, anche implementando algoritmi classici

Come aspetto collaterale il corso sviluppa le competenze di programmazione (in particolare nei linguaggi C e Java)

Autonomia di giudizio:

• analizzare correttezza e costo di algoritmi ricorsivi
• analizzare correttezza e costo di algoritmi greedy e di programmazione dinamica
• saper affrontare con spirito critico gli algoritmi e gli esercizi proposti, distinguendo i diversi gradi di difficoltà e proponendo soluzioni corrette in modo autonomo
• apprezzare la necessità di utilizzare tecniche avanzate (appena accennate in questo corso) per problemi per i quali non si conoscono algoritmi polinomiali
• riconoscere gli ingredienti comuni delle le strategie per la progettazione di algoritmi greedy o di programmazione dinamica per i problemi studiati.

Abilità comunicative: aver acquisito e saper utilizzare la terminologia formale specifica relativa alle aree citate, saper giustificare le scelte fatte e comunicarle in modo chiaro anche a utenti meno esperti.

Capacità di apprendere: Essere in grado di intraprendere con profitto studi successivi sugli elementi di algoritmica; la comprensione delle tecniche algoritmiche e dei meccanismi di ragionamento e analisi relativi permetterà di comprendere e apprendere algoritmi per problemi diversi che utilizzano le tecniche algoritmiche presentate.