Italiano
Italian
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.
Lezioni:48 ore
Lectures:48h.
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.
Al termine del corso gli studenti saranno in grado di
formalizzare problemi dell'Ingegneria
dell'Informazione utilizzando strutture dati ed
algoritmi adeguati (corretti, efficienti)
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.
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.
After completing the course, students will be able to
formalize nformation engineering problems using
appropriate algorithms and data structures (correct,
efficient)
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.
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.
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.
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.
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.
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
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.
The student must demonstrate an appropriate knowledge about data structures, the most appropriate algorithms for each problem, and how these algorithms should be implemented.
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
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.
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
no
no
Università Politecnica delle Marche
P.zza Roma 22, 60121 Ancona
Tel (+39) 071.220.1, Fax (+39) 071.220.2324
P.I. 00382520427