Facoltà di Ingegneria - Guida degli insegnamenti (Syllabus)

Programma

Nuova ricerca Nuova ricerca    Stampa scheda Stampa scheda

Algoritmi e Strutture Dati
Algorithms and Data Structures
Giuseppa Ribighini

Sede Ingegneria
A.A. 2016/2017
Crediti 9
Ore 72
Periodo II
Lingua ITA

Prerequisiti
conoscenza degli argomenti di un corso di Fondamenti di Informatica e di un linguaggio di tipo imperativo.

Risultati di apprendimento attesi
CONOSCENZE E COMPRENSIONE:
L'insegnamento permette agli studenti di possedere una conoscenza adeguata delle strutture dati e di algoritmi notevoli per la soluzione di alcuni problemi fondamentali (ricerca, inserimento), tenendo conto della complessità computazionale di ciascun algoritmo, nonché di saperli implementare in un opportuno linguaggio, comprendendo modalità e limiti di applicazione degli algoritmi e strutture dati esaminati.
CAPACITA' DI APPLICARE LE CONOSCENZE:
Al termine del corso gli studenti saranno in grado di formalizzare problemi dell'Ingegneria dell'Informazione utilizzando strutture dati ed algoritmi adeguati (corretti, efficienti)
COMPETENZE TRASVERSALI:
Il lavoro di gruppo svolto sull'utilizzo e il confronto di algoritmi contribuirà a migliorare sia il grado di autonomia di giudizio in generale, sia la capacità comunicativa dello studente. Infine sara' stimolata la capacità di apprendimento in autonomia e di approfondimento da parte dello studente.

Programma
Introduzione agli algoritmi. Algoritmi numerici per il calcolo di integrali e per la soluzione di un sistema di equazioni lineari. Progettazione di algoritmi ricorsivi. Complessità computazionale, notazioni asintotiche, complessità dei principali costrutti e calcolo della complessità computazionale di funzioni ricorsive. Strutture dati elementari. Algoritmi di ordinamento e calcolo delle relative complessità computazionali. Liste dinamiche: algoritmi per operazioni di ricerca, inserimento e cancellazione e relative complessità computazionali. Alberi binari di ricerca: algoritmi ricorsivi per operazioni di ricerca, inserimento e cancellazione e relative complessità computazionali. Cenni agli alberi rosso-neri,ai B-alberi, agli alberi AVL e agli alberi 2-3. Tabelle hash ad indirizzamento chiuso e ad indirizzamento aperto: algoritmi per operazioni di ricerca, inserimento e cancellazione e relative complessità computazionali. Tipi di dato astratti: progetto e realizzazione. Il linguaggio utilizzato nel corso è il linguaggio C.

Modalità di svolgimento dell'esame
METODI DI VALUTAZIONE DELL'APPRENDIMENTO
La valutazione dell'apprendimento consiste in due prove: - una prova scritta relativa ad argomenti trattati nel corso da completare in due ore - una prova orale nel corso della quale verranno discussi uno o più temi trattati durante il corso ed eventuali lacune evidenziate nello svolgimento della prova scritta. La prova scritta è propedeutica alla prova orale, per accedere alla quale lo studente deve aver ottenuto almeno la sufficienza nella prova scritta. Lo studente dovrà inoltre presentare, prima della prova scritta o durante la medesima, un progetto, a sua scelta, su uno dei temi trattati nel corso. Il progetto, in linea di massima, deve essere svolto in gruppi composti al massimo di quattro o cinque persone e verrà esposto da ciascuno in sede di orale.

CRITERI DI VALUTAZIONE DELL'APPRENDIMENTO
Lo studente deve dimostrare di possedere una conoscenza adeguata delle strutture dati e degli algoritmi più opportuni per la soluzione di problemi e di saper implentare tali algoritmi.

CRITERI DI MISURAZIONE DELL'APPRENDIMENTO
Sia nella prova scritta che in quella orale lo studente deve dimostrare di possedere una complessiva conoscenza dei contenuti, esposti in maniera sufficientemente corretta con utilizzo di adeguata terminologia tecnica. In entrambe le prove il voto viene espresso in trentesimi

CRITERI DI ATTRIBUZIONE DEL VOTO FINALE
Affinché l'esito complessivo della valutazione sia positivo, lo studente deve conseguire almeno la sufficienza, pari a diciotto punti, sia nella prova scritta che in quella orale. La valutazione massima è raggiunta dimostrando una conoscenza approfondita dei contenuti, esposta con completa padronanza del linguaggio tecnico e presentando un buon progetto. La lode è riservata agli studenti che, avendo svolto entrambe le prove in modo corretto e completo, abbiano dimostrato una particolare brillantezza nella prova scritta e nell'esposizione orale, nonché una buona autonomia nella redazione del progetto

Testi consigliati
P.Foggia, M. Vento - “Algoritmi e strutture dati - Astrazione, progetto e realizzazione“- McGraw Hill 2011 (Testo adottato) C. Demetrescu, I. finocchi, G. F. Italiano - “Algoritmi e strutture dati “-McGraw Hill 2008 C. Demetrescu, I. finocchi, G. F. Italiano - “Progetto di algoritmi e strutture dati in Java “ -McGraw Hill 2007. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein - “Introduzione agli algoritmi e strutture dati“-McGraw Hill 2010

Corsi di laurea
  • Ingegneria Informatica e dell'Automazione (Corso di Laurea Triennale (DM 270/04))




Università Politecnica delle Marche
P.zza Roma 22, 60121 Ancona
Tel (+39) 071.220.1, Fax (+39) 071.220.2324
P.I. 00382520427