Seleziona l'Anno Accademico:     2017/2018 2018/2019 2019/2020 2020/2021 2021/2022 2022/2023
Docente
CECILIA DI RUBERTO (Tit.)
Periodo
Secondo Semestre 
Modalità d'Erogazione
Convenzionale 
Lingua Insegnamento
ITALIANO 



Informazioni aggiuntive

Corso Percorso CFU Durata(h)
[60/61]  INFORMATICA [61/00 - Ord. 2016]  PERCORSO COMUNE 9 84
[60/65]  MATEMATICA [65/60 - Ord. 2020]  MATEMATICA APPLICATA 6 48

Obiettivi

Il corso permette di acquisire adeguate conoscenze di algoritmi, strutture dati e loro implementazione in C per la soluzione di problemi complessi. In particolare si evidenziano i seguenti aspetti:
- Definire formalmente la nozione di algoritmo.
- Organizzare le informazioni in strutture dati.
-Caratterizzare i dati da elaborare organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi.
- Progettare algoritmi corretti ed efficienti, attraverso l'esame di diversi paradigmi e risolvendo il problema il più velocemente possibile o usando il minor spazio di memoria possibile.
- Studiare le limitazioni inerenti dei problemi da risolvere.


Risultati di apprendimento attesi

Conoscenza e capacità di comprensione (knowledge and understanding)
Lo studente acquisirà le conoscenze fondamentali relative a:
- Conoscenza dei meccanismi di allocazione della memoria e utilizzo dei puntatori
- Abilità di programmazione in C, utilizzando puntatori e strutture dati dinamiche
- Abilità nelle tecniche di programmazione ricorsiva
- Conoscenza delle nozioni elementari di analisi della complessità
- Abilità di valutare la complessità di algoritmi e di migliorarne l'efficienza in termini di tempo di esecuzione e/o uso di memoria
- Abilità di problem solving mediante progetto di strutture dati e algoritmi
- Conoscenza di strutture dati complesse (liste, code, stack, heap, alberi, tabelle hash e grafi) e dei relativi algoritmi
- Conoscenza degli algoritmi di ordinamento

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding)
Lo studente dovrà essere in grado di applicare la conoscenza acquisita per il raggiungimento dei seguenti obiettivi:
- saper organizzare le informazioni in strutture dati adeguate
- caratterizzare i dati da elaborare organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi
- progettare algoritmi corretti ed efficienti, attraverso l'esame di diversi paradigmi e risolvendo il problema il più velocemente possibile o usando il minor spazio di memoria possibile.

Autonomia di giudizio (making judgements)
Lo studente sarà in grado di applicare le metodologie proprie dell'algoritmica per la comprensione e la risoluzione di nuovi problemi di natura computazionale. Le discussioni critiche in aula e le esercitazioni di laboratorio serviranno a stimolare e sviluppare l'autonomia di giudizio dello studente.

Abilità comunicative (communication skills)
Lo studente acquisirà la capacità di esprimere i concetti fondamentali propri degli algoritmi e delle strutture dati con terminologia appropriata e rigorosa. Imparerà a descrivere i problemi inerenti l'analisi e la progettazione di algoritmi corretti ed efficienti e le metodologie adottate per la loro soluzione.

Capacità di apprendimento (learning skills)
Lo studente acquisirà la capacità di studiare ed apprendere tecniche algoritmiche e strutture dati fondamentali. Imparerà a riconoscere l'importanza delle risorse computazionali (in particolare spazio e tempo) in modo da poter sviluppare autonomamente soluzioni per nuove problematiche inerenti la progettazione corretta ed efficiente di algoritmi.

Prerequisiti

Elementi di analisi matematica
Algebra lineare (vettori e matrici)
Conoscenza dell'architettura elementare dei sistemi di elaborazione
Conoscenza di sintassi, tipi di dato e costrutti base del linguaggio C
Capacità di sviluppare semplici programmi in C.

Contenuti

Analisi di algoritmi: complessità in tempo e in spazio, complessità asintotica, notazione· O, Omega, Teta; algoritmi ricorsivi e relazioni di ricorrenza, caso pessimo, ottimo e medio (8 h)

Strutture dati di base: array, matrice, stringa, coda, stack. Problema del pattern matching (6 h).
Strutture dati dinamiche: liste singolarmente concatenate, coda e stack dinamicamente concatenati. liste doppiamente concatenate (2 h)
Strutture ad albero: alberi binari, proprietà, rappresentazioni ed operazioni (5 h)
Heap e code con priorità (3 h).
Alberi binari di ricerca, AVL (6 h).
Tavole hash (2 h)
Grafi: proprietà, rappresentazioni, operazioni, problema del percorso minimo (7 h)

Algoritmi di ordinamento: ordinamento per inserzione e per selezione, ordinamento rapido, ordinamento per fusione, ordinamento con heap, ordinamento con radice (9 h)

Metodi Didattici

Oltre alle lezioni teoriche ed esercitazioni guidate in aula (48 h), sono previste esercitazioni pratiche svolte in laboratorio e coadiuvate dal docente e da tutors dove verranno implementati in C gli algoritmi descritti e utilizzati per risolvere alcuni problemi pratici (36 h).
La didattica sarà erogata in presenza. Le lezioni potranno essere integrate con materiali audiovisivi e con lo streaming.

Metodi Didattici

Oltre alle lezioni teoriche ed esercitazioni guidate in aula (48 h), sono previste esercitazioni pratiche svolte in laboratorio e coadiuvate dal docente e da tutors dove verranno implementati in C gli algoritmi descritti e utilizzati per risolvere alcuni problemi pratici (36 h).
La didattica sarà erogata in presenza. Le lezioni potranno essere integrate con materiali audiovisivi e con lo streaming.

Verifica dell'apprendimento

L’esame si compone di una prova scritta con esercizi/domande a risposta multipla sugli argomenti teorici e gli algoritmi descritti a lezione e di una prova orale. La prova scritta dura indicativamente 1 ora.
Viene valutata in trentesimi ed è ritenuta sufficiente se il relativo voto, che di norma rimane valido per il solo appello in cui la prova viene sostenuta, è di almeno 18/30. La prova scritta, se superata, è seguita da una prova orale, volta alla verifica e alla discussione delle soluzioni ai problemi proposti durante le esercitazioni di laboratorio e composta da ulteriori domande sul programma del corso. La prova orale è finalizzata ad accertare: il livello di conoscenza dei contenuti teorici del corso (descrittore di Dublino 1), il livello di competenza nell’esporre le proprie capacità di argomentazione (descrittore di Dublino 2), l’autonomia di giudizio (descrittore di Dublino 3) nel proporre l’approccio più opportuno per argomentare quanto richiesto. La prova orale ha anche l’obiettivo di verificare la capacità dello studente di rispondere con proprietà di linguaggio alle domande proposte, di sostenere un rapporto dialettico durante la discussione e di dimostrare capacità logico-deduttive e di sintesi nell'esposizione (descrittore di Dublino 4). Se superata, comporta un aggiustamento per eccesso o per difetto di al più 5/30 del voto della prova scritta, determinando così il voto finale.

Testi

C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, 2004.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi e Strutture Dati, McGraw-Hill, 2005.

Altre Informazioni

Slides delle lezioni ed altro materiale sono disponibili sulla piattaforma didattica per l’elearning Moodle.

Questionario e social

Condividi su:
Impostazioni cookie