2. Docenti
  3. Didattica

ALGORITMI E STRUTTURE DATI

Diodato FERRAIOLI ALGORITMI E STRUTTURE DATI

0612700006
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
CORSO DI LAUREA
INGEGNERIA INFORMATICA
2015/2016

OBBLIGATORIO
ANNO CORSO 2
ANNO ORDINAMENTO 2012
PRIMO SEMESTRE
CFUOREATTIVITÀ
990LEZIONE
PASQUALE FOGGIA T Curriculum
DIODATO FERRAIOLI Curriculum
Obiettivi
RISULTATI DI APPRENDIMENTO PREVISTI E COMPETENZE DA ACQUISIRE
IL CORSO HA L’OBIETTIVO DI APPROFONDIRE GLI ASPETTI RELATIVI ALLA PROGETTAZIONE E REALIZZAZIONE DI ALGORITMI, UTILIZZANDO TECNICHE ITERATIVE E RICORSIVE E VALUTANDO L’EFFICIENZA DEI PROGRAMMI OTTENUTI E LE STRUTTURE DATI FONDAMENTALI, COME STACK, CODE, LISTE, ALBERI E TABELLE HASH, CURANDONE LA REALIZZAZIONE IN LINGUAGGIO C.

CONOSCENZE E CAPACITÀ DI COMPRENSIONE
CONOSCENZA DEGLI ALGORITMI E STRUTTURE DATI FONDAMENTALI. CONOSCENZA DEI PARADIGMI DI PROGRAMMAZIONE ITERATIVA E RICORSIVA. CONFRONTO DI ALGORITMI SULLA BASE DELL’EFFICIENZA DI MEMORIA E DI ESECUZIONE

CONOSCENZA E CAPACITÀ DI COMPRENSIONE APPLICATE
ANALIZZARE PROBLEMI TIPICI E REALIZZARE APPLICAZIONI CHE LI RISOLVANO UTILIZZANDO ALGORITMI E STRUTTURE DATI STANDARD IN LINGUAGGIO C, VALUTANDONE L’EFFICIENZA. REALIZZAZIONE DI PROGETTI SOFTWARE IN C DI PICCOLE DIMENSIONI IMPIEGANDO SIA
STRUMENTI CASE CHE LA COMPILAZIONE SEPARATA.

AUTONOMIA DI GIUDIZIO
SELEZIONARE GLI ALGORITMI E LE STRUTTURE DATI ADEGUATE A SUPPORTARE UN’APPLICAZIONE, SULLA BASE DELLE SPECIFICHE ESIGENZE APPLICATIVE.

ABILITÀ COMUNICATIVE
ESSERE IN GRADO DI DOCUMENTARE E COMUNICARE LE SCELTE DI PROGETTO DI PROGRAMMI CHE UTILIZZANO ALGORITMI E STRUTTURE DATI STANDARD USANDO GLI APPROPRIATI FORMALISMI IN FORMA SCRITTA E ORALE. LAVORARE IN PICCOLI GRUPPI.
Prerequisiti
PER IL PROFICUO RAGGIUNGIMENTO DEGLI OBIETTIVI PREFISSATI SONO RICHIESTE CONOSCENZE SULLA PROGRAMMAZIONE IN LINGUAGGIO C.
Contenuti
COMPLEMENTI DI PROGRAMMAZIONE IN C: PUNTATORI, ARRAY E PUNTATORI, ARITMETICA DEI PUNTATORI. LE STRUTTURE (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 4/2/2)

RICORSIONE: ASPETTI E DEFINIZIONI GENERALI. INDUZIONE MATEMATICA. DIVIDE ET IMPERA. ALGORITMI RICORSIVI NOTEVOLI: HANOI, QUICKSORT, MERGESORT (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 4/2/2)

COMPLESSITÀ COMPUTAZIONALE: DEFINIZIONI, IL MODELLO RAM, NOTAZIONI FUNZIONI BIG-O, OMEGA, THETA, CALCOLO DI COMPLESSITÀ (I VARI COSTRUTTI), CALCOLO DI COMPLESSITÀ DEGLI ALGORITMI, FORMULE DI RICORRENZA, RICORRENZE NOTEVOLI E LORO RISOLUZIONE, CENNI ALLA ANALISI AMMORTIZZATA (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 4/2/0)

LISTE DINAMICHE: ASPETTI GENERALI, CLASSIFICAZIONE E STRUTTURA DATI, ALGORITMI DI BASE (IN VERSIONE ITERATIVA E RICORSIVA): CREAZIONE, INSERIMENTO, RICERCA, CANCELLAZIONE, VISITA, ALTRI ALGORITMI SULLE LISTE (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 6/4/2)

ALBERI BINARI: ASPETTI GENERALI, CLASSIFICAZIONE E STRUTTURA DATI, ALGORITMI DI BASE (IN VERSIONE ITERATIVA E RICORSIVA): CREAZIONE, INSERIMENTO, RICERCA, CANCELLAZIONE, VISITA, ALTRI ALGORITMI SUGLI ALBERI (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 6/4/2)

TABELLE HASH: ASPETTI GENERALI, HASHING ESTERNO ED INTERNO, ALGORITMI DI BASE (IN VERSIONE ITERATIVA E RICORSIVA): CREAZIONE, INSERIMENTO, RICERCA, CANCELLAZIONE, VISITA, ALTRI ALGORITMI SULLE TABELLE HASH (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 6/4/2)

STRUMENTI CASE: AMBIENTI DI PROGRAMMAZIONE, DEBUGGING E TESTING, COMPILAZIONE SEPARATA E LIBRERIE, MAKEFILE (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 6/5/5)

SUPPORTO A RUN-TIME: ASPETTI GENERALI SUI MODELLI DI MEMORIA, MEMORIA STATICA E MEMORIA DINAMICA, STACK E RECORD DI ATTIVAZIONE, NOMI ED AMBIENTE, REGOLE DI SCOPE STATICO E DINAMICO (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 8/4/2)
Metodi Didattici
L’INSEGNAMENTO CONTEMPLA LEZIONI TEORICHE, ESERCITAZIONI IN AULA ED ESERCITAZIONI PRATICHE DI LABORATORIO. NELLE ESERCITAZIONI IN AULA VENGONO PROPOSTI E COMMENTATI ALGORITMI E LA RELATIVA CODIFICA IN LINGUAGGIO C, UTILIZZANDO OPPORTUNI STRUMENTI CASE. NELLE ESERCITAZIONI IN LABORATORIO GLI STUDENTI SVOLGONO LE PRECEDENTI ATTIVITÀ IN AUTONOMIA SULLA BASE DELLE SPECIFICHE FORNITE DAL DOCENTE. L’ATTIVITÀ DI LABORATORIO PREVEDE ANCHE LO SVILUPPO DI PROGETTI REALIZZATI IN GRUPPI DI 3-4 PERSONE.
DURANTE IL CORSO, SONO PROPOSTE AGLI STUDENTI DUE PROVE PRATICHE CON VALUTAZIONE DA PARTE DEL DOCENTE (CONTEST). TALI PROVE ORGANIZZATE NELL’AMBITO DELLE ORE DEL CORSO DESTINATE ALLE ESERCITAZIONI, HANNO L’OBIETTIVO DI VALUTARE LE COMPETENZE PRATICHE ACQUISITE DALLO STUDENTE ALLA DATA DELLE STESSE. ALLE PROVE È ATTRIBUITO UN PUNTEGGIO IN FASCE, NONCHÉ UNA LISTA DI INDICAZIONI PER LA CORREZIONE DEGLI ERRORI E IL MIGLIORAMENTO DELLA SOLUZIONE AL PROBLEMA PROPOSTO. I CONTEST SONO CONSIDERATI COMPLESSIVAMENTE SUPERATI SE IN OGNUNO È STATA RAGGIUNTA LA SUFFICIENZA.
Verifica dell'apprendimento
LA PROVA DI ESAME È FINALIZZATA A VALUTARE NEL SUO COMPLESSO: LA CONOSCENZA E LA CAPACITÀ DI COMPRENSIONE DEI CONCETTI PRESENTATI AL CORSO; LA CAPACITÀ DI APPLICARE TALI CONOSCENZE PER LA RISOLUZIONE DI PROBLEMI CHE RICHIEDONO L’UTILIZZO DI ALGORITMI E STRUTTURE DATI FONDAMENTALI, VALUTANDONE L’EFFICIENZA DI ELABORAZIONE; L’AUTONOMIA DI GIUDIZIO, LE ABILITÀ COMUNICATIVE E LA CAPACITÀ DI APPRENDERE. ESSA CONSISTE DI UNA PROVA PRATICA E DI UN COLLOQUIO ORALE.
LA PROVA PRATICA È TESA AD ACCERTARE LE COMPETENZE NEL REALIZZARE PROGRAMMI IN LINGUAGGIO C CHE USANO ALGORITMI (ORDINAMENTO E SELEZIONE) E STRUTTURE DATI DI BASE (PILE, CODE, LISTE, ALBERI, TABELLE HASH), ED È REALIZZATA DIRETTAMENTE SUL SISTEMA DI ELABORAZIONE PERSONALE. SONO CONSIDERATE CAPACITÀ MINIME QUELLE DI RISOLVERE IL PROBLEMA PROPOSTO, SENZA ERRORI SINTATTICI RILEVANTI; SONO RITENUTE CAPACITÀ MASSIME QUELLA DI PERVENIRE A SOLUZIONI ALGORITMICHE CHE SIANO EFFICIENTI E CHE FACCIANO USO DELLE STRUTTURE DATI E DEGLI ALGORITMI PIÙ ADEGUATI, SIA IN VERSIONE ITERATIVA CHE RICORSIVA. ESEMPI DI PROVE PRATICHE SONO CONSULTABILI SUL SITO DEL CONSIGLIO DIDATTICO.
SONO ESONERATI DALLA PROVA PRATICA GLI STUDENTI CHE HANNO SUPERATO CON ESITO POSITIVO I CONTEST DURANTE IL CORSO.
IL SUPERAMENTO DELLA PROVA PRATICA È CONDIZIONE PER ACCEDERE AL COLLOQUIO ORALE.
IL COLLOQUIO ORALE VERTERÀ SU TUTTI GLI ARGOMENTI DEL CORSO E LA VALUTAZIONE TERRÀ CONTO DELLE CONOSCENZE DIMOSTRATE DALLO STUDENTE E DEL GRADO DEL LORO APPROFONDIMENTO, DELLA CAPACITÀ DI APPRENDERE DIMOSTRATA, DELLA QUALITÀ DELL’ESPOSIZIONE.
AI FINI DEL VOTO FINALE, ESPRESSO IN TRENTESIMI, LA PROVA PRATICA CONTRIBUISCE PER IL 60% E LA PROVA ORALE PER IL 40%. LA LODE PUÒ ESSERE ATTRIBUITA AGLI STUDENTI CHE DIMOSTRINO UNA OTTIMA CAPACITÀ DI ANALISI E DI PROGETTO DI ALGORITMI E STRUTTURE DATI.
Testi
M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL.

IL CORSO È COMPLETAMENTE SUPPORTATO DA MATERIALE DIDATTICO ON-LINE E DISPENSE DEL DOCENTE DISPONIBILI SUL SITO DEL CORSO. SONO INOLTRE DISPONIBILI PER GLI STUDENTI ESEMPI DI ESERCIZI SVOLTI E ULTERIORE MATERIALE DIDATTICO INTEGRATIVO.

TESTI CONSIGLIATI:
T.H. CORMEN, C.E. LEISERSON, R.R. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 2/ED”, MCGRAW-HILL.
Altre Informazioni
L’INSEGNAMENTO È EROGATO IN PRESENZA CON FREQUENZA OBBLIGATORIA. LA LINGUA DI INSEGNAMENTO È L’ITALIANO.
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2016-09-30]