Ateneo - UPO

Metodi di analisi degli algoritmi. Strutture dati fondamentali. Algoritmi fondamentali (ricerca e ordinamento). Tecniche algoritmiche, nozione di grafo e algoritmi su grafi

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e strutture dati 2/ed MacGraw-Hill, 2008; ISBN: 978 88 386 64687- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, third editionMcGraw-Hill, 2010. (presente anche in italiano)

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.

Aver superato l’esame di Programmazione 1 e 2.

Didattica Erogativa in aula (eventualmente in modalità blended) e Didattica Interattiva in laboratorio.
Nelle lezioni in aula vengono esposte le nozioni fondamentali, corredate di esempi. Vengono confrontate diverse strutture dati, e algoritmi diversi mirati a risolvere problemi della stessa classe.Sulla piattaforma DIR sono indicati i libri di testo suggeriti ed è a disposizione delle studentesse e degli studenti 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 la studentessa/lo studente viene guidata/o 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 gli assenti.

Le studentesse e gli studenti 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 studentesse e gli studenti con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo,
possono contattare la/il 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, pesando i risultati coerentemente con il numero di CFU di ciascun modulo.
Precisamente, i voti vengono assegnati secondo la seguente griglia di valutazione:
Meno di 18: 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.
Teoria primo modulo: Esame scritto, eventualmente in forma di quiz. L'esame prevede tipicamente 4 esercizi, che verteranno su argomenti svolti in una parte diversa del programma: un esercizio riguarderà l’analisi della complessità, mentre gli altri riguarderanno argomenti tra: strutture dati fondamentali, algoritmi di ordinamento, algoritmi di ricerca tramite alberi, tabelle hash, code con priorità. Gli esercizi saranno volti a valutare le conoscenze teorico/pratiche e le capacità di giudizio (esercizi in cui viene richiesto allo studente/studentessa di esprimere una scelta o un giudizio) Il voto terra' conto dei risultati parziali ottenuti nei singoli esercizi. La stessa tipologia di esame potra' essere svolta oralmente, o integrata da una prova orale. Il quiz permette di raggiungere il voto di 24/30. Facoltativamente, si potrà anche completare una dimostrazione, arrivando potenzialmente al punteggio di 30 e lode (eccellenza in caso di dimostrazione corretta e completa). Tramite la dimostrazione si valuteranno le capacità comunicative (lessico e chiarezza nell’esposizione) e la capacità di apprendere (motivare i vari passi con senso critico). Chi supera la parte di teoria (ottenendo un punteggio pari ad almeno 18/30) è ammessa/o immediatamente alla prova di laboratorio, che si svolge nella stessa giornata. Laboratorio primo modulo: Esame pratico. L'esame prevede due esercizi in cui si richiede l'implementazione di due programmi in linguaggio C. I due esercizi valgono 15 punti l'uno. La sufficienza richiede di raggiungere almeno 18 punti complessivi, mentre il corretto sviluppo di entrambi gli algoritmi e relativo programma permette di raggiungere 30 punti. 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. Secondo modulo: Esame scritto seguito da orale (con valutazione degli esercizi svolti in laboratorio) L’esame scritto è solitamente composto da 6 domande. Lo studente che supera l’esame scritto (con votazione almeno pari a 18) può accedere alla prova orale. L’esame orale verifica le competenze teoriche. In particolare, si verifica che lo studente abbia acquisito la terminologia formale e la capacità di analisi. Vengono poste delle domande (solitamente 3, il cui numero può variare in base alle risposte date) che hanno come obbiettivo: (i) verifica della familiarità con il concetto di grafo nelle sue varianti, (ii) capacità di analisi di algoritmi di visita di grafi, (iii) capacità di analisi di algoritmi greedy e di programmazione dinamica, (iv) basilare sensibilità su come affrontare problemi difficili. Al termine della prova orale viene espresso un voto che tiene conto per il 50% della prova scritta e per l’altro 50% della prova orale.

Introduzione agli algoritmi. Modelli di analisi. Algoritmi di ordinamento e di ricerca. Algoritmi su grafi. Tecniche algoritmiche.

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 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 nei linguaggi C e Java)Autonomia di giudizio:analizzare correttezza e costo di algoritmi ricorsivianalizzare correttezza e costo di algoritmi greedy e di programmazione dinamicasaper affrontare con spirito critico gli algoritmi e gli esercizi proposti, distinguendo i diversi gradi di difficoltà e proponendo soluzioni corrette in modo autonomoapprezzare 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 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.