Ateneo - UPO

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

C. Demetrescu, I.Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, Seconda Edizione, McGraw-Hilloppure in alternativa: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 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; le nozioni base di algoritmica insegnate nel modulo di Algoritmi 1. Principi e linguaggi di programmazione insegnati nei corsi di semestri precedenti.

Il corso è insegnato in aula e in laboratorio.
Nelle lezioni in aula vengono esposte le nozioni fondamentali, corredate di esempi, anche utilizzando un software di simulazione di algoritmi. 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 integrativo aggiuntivo. Inoltre dopo ogni lezione, vengono indicati sul DIR gli argomenti trattati, con riferimento bibliografico, per chi non avesse seguito la lezione (ma anche per le persone presenti).
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 le persone assenti.
Durante la lezione viene usato lo strumento wooclap in modalità anonima per porre domande volte a verificare la comprensione degli argomenti e per stimolare la partecipazione.
Sul DIR sono disponibili dei quiz di esercizio e autovalutazione (identici agli esercizi d'esame, presentano di volta in volta istanze diverse di domande di ciascun tipo) che forniscono un modo di misurarsi con gli argomenti presentati, in modo da scoprire eventuali proprie lacune o dubbi e poter quindi rivolgersi per tempo alla docente per chiarimenti. Inoltre, allo stesso scopo, sono fornite le specifiche di quesiti di programmazione d'esame usati in passato.
Sul DIR sono disponibili anche link a registrazioni di lezioni, tenute dalla docente, divise per argomento, per agevolare coloro che non possono seguire le lezioni e come complemento e supporto anche per le persone che seguono.

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.

L'esame si articola in quattro domande: la prima (in laboratorio) è un semplice problema da risolvere con l'implementazione di uno degli algoritmi visti a lezione; le successive tre sono domande orali. La parte orale si svolge nella stessa giornata (compatibilmente con il numero di persone iscritte) ed è tesa a verificare la comprensione della teoria alla base degli algoritmi insegnati nel corso, del funzionamento degli algoritmi classici presentati a lezione. Inoltre, nel corso della discussione si verifica che la persona abbia acquisito la terminologia formale, che sia in grado di spiegare i ragionamenti alla base della progettazione e della dimostrazione di correttezza degli algoritmi e che abbia acquisito capacità di analisi. Il numero di domande può variare a seconda del modo in cui vengono date le risponde (formalità, chiarezza, completezza, precisione,...) e della qualità del programma implementato.Si ottiene la sufficienza mostrando la padronanza della terminologia tecnica, e di conoscere le definizioni e gli algoritmi insegnati con loro complessità, e di restituire almeno una dimostrazione di correttezza. Si raggiunge l'eccellenza mostrando capacità di illustrare le dimostrazioni, mostrando comprensione dei ragionamenti, con una presentazione ragionata che non segue nei dettagli la presentazione fatta a lezione, e competenze per risolvere problemi.È possibile svolgere l'esame unicamente tramite quiz a correzione automatica in laboratorio. Si tratta di due quiz per un totale di 20 domande e non è richiesta conoscenza di dimostrazioni. Il primo quiz, di 10 domande, valuta conoscenze teoriche e il secondo quiz di 10 domande valuta la conoscenza del funzionamento degli algoritmi. La sufficienza si ottiene rispondendo in modo corretto complessivamente al 70% delle domande. Il voto massimo è 22/30, e si ottiene rispondendo correttamente al 90% delle domande.La preferenza per la modalità d'esame prescelta deve essere espressa all'atto dell'iscrizione.

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'implementazionevisita di grafi in ampiezza e in profondità, caratteristiche comuni e differenze delle varie visite proposte e loro applicazioniTecnica golosa (greedy):introduzione e algoritmi di esempio;cammini minimi su grafo pesato da un nodo sorgente: algoritmo di Dijkstra e applicazioniminimo albero ricoprente: algoritmi di Prim e Kruskal e loro utilizzo per risolvere problemi praticitecniche di dimostrazione di correttezza e loro funzione in relazione alla progettazione di algoritmi greedylimiti della tecnica golosaTecnica di programmazione dinamicaintroduzione alla tecnica e proprietà della sottostruttura ottima; confronto con la tecnica golosa e con il divide et imperaaspetti e scelte di impementazione: algoritmi ricorsivi e iterativi, memoizationutilizzo 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-Fordcammini minimi da tutti i nodi: algoritmo di Floyd-WarshallCenni sui problemi intrattabili:classi P, NP ed NP completezzaalgoritmi di complessità pseudopolinomialeintroduzione alle tecniche per affrontare i problemi difficili.

Conoscenza e capacità di comprensione: 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:modellare problemi utilizzando grafirisolvere problemi tramite l'implementazione di algoritmi classici di visita di grafirisolvere problemi utilizzando tecniche greedy e di programmazione dinamica, anche implementando algoritmi classiciCome aspetto collaterale il corso sviluppa le competenze di programmazione (in particolare nel linguaggio Java).Autonomia di giudizio:analizzare correttezza e costo di algoritmi greedy e di programmazione dinamicasaper affrontare con spirito critico gli algoritmi proposti, distinguendo i diversi gradi di difficoltà, e apprezzando la necessità di utilizzare tecniche avanzate (appena accennate in questo corso) per problemi per i quali non si conoscono algoritmi polinomialiriconoscere gli ingredienti comuni delle le strategie per la progettazione di algoritmi greedy o di programmazione dinamica per i problemi studiatiAbilità comunicative: aver acquisito e saper utilizzare la terminologia formale specifica relativa alle aree citate.Capacità di apprendere: 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.