Ateneo - UPO

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

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

Enunciare la definizione delle strutture dati fondamentali e saperle adottare in problemi proposti.
Analizzare un algoritmo dato, sia esso ricorsivo che iterativo.
Saper descrivere gli algoritmi di ricerca e di ordinamento.
Saper applicare un algoritmo specifico, tra quelli visti, ad un problema dato.
Essere in grado di darne un'implementazione in C.

Aver superato l’esame di Programmazione 1 e 2.

Lezioni in aula (eventualmente in modalità blended) ed esercitazioni 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. 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.

Teoria: 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: Esame pratico. L'esame prevede due esercizi in cui si richiede l'implementazione di due programmi in linguaggio C. Gli argomenti comprendono quelli presentati durante le lezioni frontali e in laboratorio. 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.

- 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.

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.
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.Autonomia di giudizio: analizzare gli algoritmi ricorsivi; saper affrontare con spirito critico gli esercizi proposti, proponendo soluzioni corrette in modo autonomo.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