Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
Algoritmi e programmazione

 

Docente responsabile:  Claudio Zandron e Marco Antoniotti

 

 

PROGRAMMA

 

Obiettivi e contenuti

Lo studente acquisirà le metodologie fondamentali di progetto ed analisi degli algoritmi e delle strutture dati elementari. L’insegnamento si propone inoltre di approfondire alcune tecniche avanzate di programmazione orientata agli oggetti in Java utili nell’implementazione degli algoritmi e strutture dati elementari.

 

Programma algoritmi e strutture dati 1

 

1.       Nozioni fondamentali (algoritmo, problema, istanza); Pseudocodice e macchina RAM; Problema dell'ordinamento di un vettore (Algoritmo insertion sort)

2.       Nozioni matematiche: Limiti asintotici inferiori e superiori; Il principio di induzione; Nozioni varie (base, tetto, sommatorie, approssimazioni, polinomi)

3.      Analisi di algoritmi: Dimensione dei dati di un problema; Complessità computazionale; Valutazione dei tempi di esecuzione

4.     Ricorsione: Definizioni ricorsive di insiemi; Algoritmi ricorsivi; Induzione

5.       Approccio Divide-et-Impera: Definizione; Algoritmo Merge-Sort

6.       Tempo di esecuzione di algoritmi ricorsivi (equazioni di ricorrenza): Definizioni; Metodo Sostituzione; Metodo Iterativo e alberi di ricorsione; Metodo Principale

7.       Ordinamento in loco: Algoritmo Quick-sort;

8.       Algoritmo di ordinamento Heapsort: Grafi e Alberi (nozioni fondamentali); Nozione di Heap; Heapsort

9.       Altri algoritmi di ordinamento: Bubble sort; Ordinamento in tempo lineare; Limite inferiore per ordinamenti basati su confronti; Counting sort; Concetto di stabilità; Radix sort

10.   Tipi astratti di dati e strutture dati (Introduzione): La nozione di tipo astratto (ADT); Insiemi dinamici; Operazioni fondamentali su insiemi dinamici

11.   Liste concatenate: Liste semplici e doppie; Liste circolari; Uso di sentinelle; Operazioni fondamentali; Gestione di liste mediante array multipli

12.   Pile (stack): Inserimento (push), cancellazione (pop); Implementazioni

13.   Code (queue): Inserimento, cancellazione, attraversamento; Implementazioni

14.   Insiemi: Definizioni e operazioni fondamentali; Realizzazione tramite liste; Realizzazione tramite vettori caratteristici

15.   Alberi: Nozione di grafo e proprietà; Alberi generici: definizione ricorsiva; Nozioni generali (nodo, figlio, antenato, discendente, altezza...); Implementazione (record con puntatori; varianti)

16.   Alberi binari: Attraversamento (ordine anticipato, simmetrico, posticipato); Alberi binari di ricerca e operazioni fondamentali (inserimento, cancellazione, ricerca, max, min, successore, predecessore)

17.   Tabelle di hash: Indirizzamento diretto; Funzioni di hash; Risoluzione di collisioni tramite liste concatenate e indirizzamento aperto; Scansione lineare; Scansione quadratica; Doppio hashing

 

Programma per Programmazione 3

1.       Approfondimenti sull’ereditarietà in Java

2.       Eccezioni

3.       Gestione Input/Output (I/O) in Java

a.       Classe Scanner

b.       Classe File

c.       I/O testuale

d.       I/O binario

4.       Vettori e Liste in Java

5.       Code e Pile in Java

6.      Programmazione Ricorsiva

7.       Definizione e utilizzo di strutture dati dinamiche ricorsive (alberi)

8.       “Generics” Java e polimorfismi

9.       Utilizzo di librerie standard Java: il “Collection Framework”

 

Risultati di apprendimento previsti: essere in grado di formalizzare la soluzione di un problema tramite opportuno algoritmo, valutarne i costi ed implementarlo successivamente in Java

 

 

Prerequisiti: aver seguito con attenzione i corsi di programmazione 1 e 2

 

 

Aims and contents

The main objective is to give students the ability to analyze, use and design algorithms and elementary data structure.  The course also aims to deepen the knowledge about advanced object-oriented programming in Java, focusing on some techniques useful in implementing algorithms and data structures.

 

Program details

 

Algorithms and Data Structures 1
1.         Fundamental notions (algorithm, problem, instance); pseudo-code and RAM machine; ordering problem for a vector (Insertion Sort).
2.         Mathematics notions; asymptotic limits, inferior and superior; induction principle; other notions (base, ceiling, sums, approximations and polynomials).
3.         Analysis of Algorithms; dimensions of problem data; computational complexity; execution time evaluation.
4.         Recursion; recursive set definitions; recursive algorithms; induction.
5.         Divide and Conquer approaches; definition; Merge Sort algorithm.
6.         Recursive algorithms execution time (recurrence equations); definitions; substitution method; iterative method and recursion trees; Master Theorem.
7.         In-place sorting; Quicksort algorithm.
8.         Heapsort; Trees and Graphs (fundamental notions); Priority Queues.
9.         Other sorting algorithms: Bubble Sort; sorting in linear time; lower bound for comparison based sorting methods; Counting Sort; Radix Sort; stability of a sorting method; Radix sort.
10.       Abstract Data Types (introduction): The notion of Abstract Data Type (ADT); dynamical sets; fundamental operations on dynamical sets.
11.       Linked Lists; single- and double- linked lists; circular lists; notion and use of “sentinels”; fundamental operations; lists management with multiple arrays.
12.       Stacks: insertion (push); extraction (pop); implementations.
13.       Queues: insertion; removal; traversal; implementations.
14.       Sets: definitions and fundamental operations; list implementation; implementation with characteristic vectors.
15.       Trees: notion of Graph and related properties; generic trees: recursive definition; general notions (node, child, descendent, height, etc. etc.); implementation (pointers and variations thereof.
16.       Binary Trees: traversal (pre-order, in-order, post-order); Binary Search Trees and fundamental operations (insertion, removal, search, min, max, successor, predecessor); balancing problem (AVL Trees and Red Black trees).
17.       Hash Tables: direct addressing; hash functions; collision problem and resolution with separate linking or open addressing; linear scan; quadratic scan; double hashing.


Programming 3
1.         Advanced use of inheritance in Java.
2.         Exception Handling in java.
3.         Streams and File Input/Output in java

a. The Scanner class

b. The File class

c. Text-File I/O

d. Binary-File I/O
4.         Definition and use of dynamic data structures in Java

a. Vectors and Linked Lists.

b. Stacks and queues.
6.         Recursion
10.       Definition and use of recursive dynamic data structures (binary trees).

12.       Generics and Polymorphism.
13.       The Java Collection Framework.

 

Learning outcomes: students will be able to formalize the solution of a problem by an algorithm, compute its costs and implement it in Java.

 

Prerequisites: Knowledge of Object Oriented Programming in Java.

 

 

 

Tipo esame:

·          Scritto

 

Tipo valutazione:

·          Voto finale

 

 

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 11/11/2013