Dettagli sull'Insegnamento per l'A.A. 2015/2016
Nome:
Laboratorio di Algoritmi e Strutture Dati / Laboratory of Algorithms and Data Structures
Informazioni
Crediti:
: Bachelor Degree in Computer Science 6 CFU (b)
Erogazione:
Bachelor Degree in Computer Science 2nd anno curriculum General Compulsory
Lingua:
Italiano
![[info]](img/info16.png)
Prerequisiti
Si assume che lo studente abbia acquisito una conoscenza di base dei principi della programmazione ed in particolare del linguaggio di programmazione Java.
Obiettivi
A partire dalle conoscenze acquisite nel corso di Fondamenti di Programmazione con Laboratorio, il modulo si concentra sullo studio di algoritmi e strutture dati fondamentali, stimolandone la comprensione attraverso la sperimentazione diretta in linguaggio Java. Il modulo illustra le principali tecniche di progettazione e le principali metodologie di analisi di algoritmi e strutture dati. Le lezioni sono svolte in linguaggio Java di cui si assume una conoscenza di base.
Sillabo
- Il Linguaggio Java: richiami sui concetti fondamentali; interfacce e classi astratte; Generics; classi e interfacce del Java Collection Framework.
- Strutture dati elementari e loro implementazione in Java: liste, stack e code. Implementazione delle liste mediante array e liste collegate semplici. Uso delle classi standard (client code perspective).
- Algoritmi di ricerca ed ordinamento e loro implementazione in Java: ricerca sequenziale e binaria; bubble-sort, insertion-sort, selection-sort, merge-sort, quick-sort.
- Strutture dati avanzate e loro implementazione in Java: alberi binari, visite BFS e DFS; alberi binari di ricerca (BST), BST bilanciati, alberi red-black, strutture dati union-find.
- Code con priorità e loro implementazione in Java: heap binari, code con priorità implementate mediante heap binari; algoritmo di ordinamento basato sulle code con priorità, implementazione Java dell'algoritmo heap-sort.
- Grafi: rappresentazione dei modelli di grafo orientato/non orientato ed etichettato/non etichettato; implementazione in Java delle visite BFS e DFS; implementazione in Java dei classici algoritmi per i problemi della ricerca del cammino minimo da sorgente singola e della ricerca del minimo albero ricoprente.
Descrittori di Dublino
Alla fine del corso, lo studente dovrebbe
- Know classical algorithms and data structures for information processing and their implementations, with particular focus on computational complexity aspects, and be aware of the effects of data organization and algorithms on program efficiency;
Be familiar with standard techniques for designing algorithms, including the techniques of recursion, divide-and-conquer, and greedy and understand how apply them to design efficient algorithms for different kinds of problems.
- Be able to apply their knowledge of data structures and algorithmic techniques to design efficient algorithms that correctly satisfy a given specification and write more efficient programs in Java;
Be able to rigorously analyze the relative time and space efficiency of competing algorithms and carry out a comparative evaluation of merits in terms of efficiency and applicability of standard data structure.
- Be able to identify efficient solutions to a given problem and choose appropriate data structures that effectively model the information in a problem;
Judge efficiency tradeoffs among alternative data structure implementations or combinations.
- Demonstrate the capability of formally presenting and modeling concrete problems and explain the most important characteristics concerning the standard data structures, their analyses, and their Java implementations.
- Have an understanding of the role and characteristics of data structures and of the importance of time and space efficiency in designing algorithms and writing programs; To be able to recognize and look up variations of the material studied in the literature.
Testi di riferimento
- William J. Collins, Algoritmi e strutture dati in Java , Ed. Maggioli, Apogeo Education.
- C. Demetrescu, U. Petrillo, I. Finocchi, G. Italiano, Progetto di Algoritmi e Strutture Dati in Java , McGraw-Hill.
Modalità d'esame
Pre-Assessment: Non è prevista nessuna valutazione preliminare. I prerequisiti del Modulo sono chiaramente descritti sulla pagina del Modulo.
Formative Assessment: Durante lo svolgimento delle lezioni gli studenti sono invitati ad interagire con la docente, a porre domande e a discutere su argomenti proposti in classe.
Summative Assessment:
L'esame consiste in una prova scritta e in un eventuale colloquio orale (a discrezione della docente in presenza di errori significativi nell’elaborato scritto, o su richiesta dello studente per migliorare il voto conseguito allo scritto). Il colloquio deve essere svolto nell’ambito della stessa sessione d’esame della prova scritta e, a partire dalla discussione della prova scritta, verte sugli argomenti in programma.
Per aiutare gli studenti a dividere il carico di lavoro, è data la possibilità di svolgere una prova scritta intermedia sugli argomenti svolti nella prima parte del corso.
La prova scritta consiste nello svolgimento di esercizi di programmazione in Java volti a valutare il livello di conoscenza e comprensione degli argomenti e l’abilità pratica.
Il voto finale del Corso di Algoritmi e Strutture Dati (12 CFU) si ottiene come voto medio conseguito nei due Moduli di Algoritmi e Strutture Dati (6 CFU) e Laboratorio di Algoritmi e Strutture Dati (6 CFU).
Note
- Gli studenti immatricolati fino all'A.A. 2012/2013 che hanno nel proprio piano di studi l'insegnamento propedeutico di Laboratorio di Programmazione II potranno optare per la prova scritta di Laboratorio in Java, anziché C, previa comunicazione alla docente. Gli altri sono invitati a contattare la docente per discutere del programma d'esame in base al proprio curriculum.
Aggiornamenti alla pagina del corso
Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:
Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.
Ultimo aggiornamento delle informazioni sul corso: 10 ottobre 2015, 18:56
English version
sad
strutture.univaq