Guida degli insegnamenti

Syllabus

Partially translatedTradotto parzialmente
[3I943] - ALGORITMI E STRUTTURE DATIALGORITHMS AND DATA STRUCTURES
GIUSEPPA RIBIGHINI
Lingua di erogazione: ITALIANOLessons taught in: ITALIAN
Laurea - [IT04] INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE First Cycle Degree (3 years) - [IT04] COMPUTER AND AUTOMATION ENGINEERING
Dipartimento: [040040] Dipartimento Ingegneria dell'InformazioneDepartment: [040040] Dipartimento Ingegneria dell'Informazione
Anno di corsoDegree programme year : 2 - Secondo Semestre
Anno offertaAcademic year: 2018-2019
Anno regolamentoAnno regolamento: 2017-2018
Crediti: 6
Ore di lezioneTeaching hours: 60
TipologiaType: D - A scelta dello studente
Settore disciplinareAcademic discipline: ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

LINGUA INSEGNAMENTO LANGUAGE

Italiano

Italian


PREREQUISITI PREREQUISITES

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

Knowledge of fundamentals of computer and an imperative programming language.


MODALITÀ DI SVOLGIMENTO DEL CORSO DEVELOPMENT OF THE COURSE

Lezioni:48 ore

Lectures:48h.


RISULTATI DI APPRENDIMENTO ATTESI LEARNING OUTCOMES
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.


Capacità di applicare conoscenze e comprensione.

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.


Knowledge and Understanding.

The course enables students to acquire appropriate knowledge of data structures and algorithms for the solution of remarkable fundamental problems (search, sort) taking into account the computational complexity of each algorithm, and to know how to implement it in an appropriate language, understanding modes and limits for the application of the examined algorithms.


Capacity to apply Knowledge and Understanding.

After completing the course, students will be able to formalize nformation engineering problems using appropriate algorithms and data structures (correct, efficient)


Transversal Skills.

The group work on the use and comparison of algorithms helps to improve student's ability of making judgements and communicate. Finally it will be stimulated the ability to learn autonomously and in-depth study.



PROGRAMMA PROGRAM

Introduzione agli algoritmi. Algoritmi numerici per il calcolo di integrali. 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 della complessità computazionale. Liste dinamiche: algoritmi per operazioni di ricerca, inserimento e cancellazione e calcolo della complessità computazionale. Alberi binari di ricerca: algoritmi ricorsivi per operazioni di ricerca, inserimento e cancellazione e calcolo della complessità computazionale. Cenni agli alberi rosso-neri. Tabelle hash ad indirizzamento chiuso e ad indirizzamento aperto: algoritmi per operazioni di ricerca, inserimento e cancellazione e calcolo della complessità computazionale. Il linguaggio utilizzato nel corso è il linguaggio C.

Introduction to algorithms. Numerical algorithms for solving integral. Design of recursive algorithms. Computational complexity, asymptotic notations, computational complexity of main structures, and computational complexity of recursive functions. Basic data structures. Sorting algorithms and their computational complexity. Dynamic lists: algorithms for search, insertion, and deletion and their computational complexity. Binary search trees: recursive algorithms for search, insertion, and deletion and their computational complexity. A short introduction to red-black trees. Hash tables for closed addressing and routing: algorithms for search, insertion and deletion and their computational complexity. The language used in the course is the C programming language.


MODALITÀ DI SVOLGIMENTO DELL'ESAME DEVELOPMENT OF THE EXAMINATION
Modalità 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 deve 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


Learning Evaluation Methods.

The evaluation learning consists of two tests: -a written test on topics covered in the course to be completed in two hours -an oral examination during which students discuss one or more course topics and any gaps arisen in the written test. The written test is preparatory to the oral test. Student must obtain at least the sufficiency in the written test in order to be admitted to the oral test. Students must also submit, prior to the written test or during the same, one project on one of the course topics at its choice. The project must be developed by a groups of four or five people and will be exposed by each group member during the oral examination.


Learning Evaluation Criteria.

The student must demonstrate an appropriate knowledge about data structures, the most appropriate algorithms for each problem, and how these algorithms should be implemented.


Learning Measurement Criteria.

Both in the written test and the oral examination, the student must demonstrate to know course topics, expose them in a sufficiently correct way using an appropriate technical terminology. Each test the assign a score up to 30


Final Mark Allocation Criteria.

In order to obtain a positive overall outcome, the student must achieve a score greater or equal than 18, both in the written test and the oral. The maximum rating is achieved by demonstrating a thorough understanding of content, exhibited with complete mastery of the technical language and presenting a good project. Full mark with distinction is reserved to students who, having played both tests correct and complete way, have shown a particular brilliance both on the written and in the oral test and a good autonomy in project work.



TESTI CONSIGLIATI RECOMMENDED READING

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
Materiale didattico disponibile al seguente indirizzo https://learn.univpm.it/course/view.php?id=7092

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
Slides and other documents are available at the following URL: https://learn.univpm.it/course/view.php?id=7092


E-LEARNING E-LEARNING

no

no


Scheda insegnamento erogato nell’A.A. 2018-2019
Le informazioni contenute nella presente scheda assumono carattere definitivo solo a partire dall'A.A. di effettiva erogazione dell'insegnamento.
Academic year 2018-2019

 


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