Ateneo - UPO

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

Algoritmi e strutture dati 2/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) per circa 2/3 del corso, ed esercitazioni in laboratorio per circa 1/3 del corso.
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 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 lo studente viene guidato 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 un minimo di 3 esercizi, che verteranno su argomenti svolti in una parte diversa del programma: un esercizio riguarderà l’analisi della complessità, mentre gli altri due riguarderanno due argomenti tra: strutture dati fondamentali, algoritmi di ordinamento, algoritmi di ricerca tramite alberi, tabelle hash, code con priorità. Il voto terra' conto dei risultati parziali ottenuti nei singoli esercizi. Eventualmente (ad esempio, per richiesta dello studente), la stessa tipologia di esame potra' essere svolta oralmente, o integrata da una prova orale.

Laboratorio: Esame pratico. L'esame prevede l'implementazione di uno o più programmi in linguaggio C. Gli argomenti comprendono quelli presentati durante le lezioni frontali e in laboratorio. Il voto terra' conto dei risultati parziali ottenuti nei singoli esercizi.

La votazione finale terrà conto dei risultati finali ottenuti nelle prove d'esame di Teoria e di Laboratorio.

- Introduzione agli algoritmi.
- Modelli di analisi. Notazioni asintotiche: O, Omega e Theta. Limiti inferiori. Teorema Master.
- Tipi di dato astratto: 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;
Ricerca indicizzata:Alberi binari di ricerca
Tabelle di 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