ALGORITMI E STRUTTURE DATI

0612700006
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
CORSO DI LAUREA
INGEGNERIA INFORMATICA
9 CFU

OBBLIGATORIO
ANNO CORSO 2
ANNO ORDINAMENTO 2016
PRIMO SEMESTRE
CFUOREATTIVITÀ
324LEZIONE
324ESERCITAZIONE
324LABORATORIO


Obiettivi
L’INSEGNAMENTO 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 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.
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 2/2/6)

SUPPORTO A RUN-TIME: ASPETTI GENERALI SUI MODELLI DI MEMORIA, MEMORIA STATICA E MEMORIA DINAMICA, STACK E RECORD DI ATTIVAZIONE (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 2/2/0)
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.

Per poter sostenere la verifica finale del profitto e conseguire i CFU
relativi all’attività formativa, lo studente dovrà avere frequentato
almeno il 70% delle ore previste di attività didattica assistita.
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
LA LINGUA DI INSEGNAMENTO È L’ITALIANO.
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2018-06-05]