Programmazione 2 (2009/10)
Programma Didattico

Programmazione Java avanzata

Creazione e distruzione di oggetti
Classi e interfacce
Genericità di tipi
Ambito delle variabili locali
Fondamenti e stile di programmazione
Debugging, Asserzioni ed Eccezioni

Operare con array e linked list

Impiego degli array
Linked list semplici
Inserimento e rimozione di elementi
Linked list doppie
Inserimento e rimozione intermedi
Linked list circolari

Ricorsione

Definizioni ricorsive
Anatomia di una invocazione ricorsiva
Ricorsione lineare
Ricorsione binaria
Ricorsione multipla
Backtracking

Strumenti per l'analisi

Funzioni per l'analisi asintotica
Confronto tra funzioni asintotiche
Analisi degli algoritmi
Notazione ed analisi asintotica
Tecniche di dimostrazione

Pile e code

La struttura dati stack
Implementazione con array e linked list
La struttura dati coda
Implementazione con array e linked list
Code doppie

Le liste e gli iteratori

Array list
Implementazione con array ed array estensibili
Node list
Implementazione con linked list
Implementazione con liste doppiamente linkate
Iteratori e utilizzo di cicli iterativi

Gli alberi

Terminologia e proprietà
Algoritmi fondamentali sugli alberi
Profondità e altezza dei nodi
Attraversamento di alberi
Alberi binari e alberi n-ari
Proprietà, attraversamento e implementazione

Alberi binari di ricerca

Alberi binari di ricerca
Proprietà e implementazione
Operazione di ricerca
Operazioni di aggiornamento
Alberi estesi

Ordinamento, insiemi e selezione

Insertion-sort e Selection-sort
Merge-sort
Quick-sort
Limite inferiore per l'ordinamento
Ordinamento in tempo lineare
Algoritmi di selezione

Grafi e strutture reticolari

Strutture dati per i grafi
Liste di adiacenza e matrici di adiacenza
Attraversamento in ampiezza
Attraversamento in profondità
Grafi orientati

Libri di testo

Strutture dati e algoritmi in Java
Autore: M.T. Goodrich, R. Tamassia
Casa editrice: Zanichelli
Anno: 2007
Pagine: 640

Effective Java
Autore: Joshua Bloch
Casa editrice: Pearson Education
Anno: 2009
Pagine: 352

Materiale didattico online

• SUN's Java Tutorials
  Tutorial e guide per il linguaggio Java sul sito della SUN. Le guide sono consultabili nsul sito http://java.sun.com/docs/books/tutorial e scaricabili in formato elettronico dal sito http://java.sun.com/docs/books/tutorial/information/download.html.
• API di Java
  The API specification for the Java 2 Platform.
• Strutture Dati ed algoritmi in Java
  Sito web ufficiale del libro di testo "Strutture dati ed algoritmi in Java". Contiene anche i codici presenti sul libro.
• Pensare da informatico: Imparare con Python
  La versione Python del libro di Allen Downey : How to Think Like a Computer Scientist. È in assoluto il migliore libro scritto per principianti, libero, disponibile in tutti i formati. Si concentra sul linguaggio di programmazione Python ed affronta praticamente tutti gli aspetti della programmazione, è usato in alcuni istituti scolastici superiori americani.
• Python.it
  Portale italiano del linguaggio di programmazione Python

Uso di Array e Linked-List

• Memorizzazione degli elementi di un gioco: GameEntry; Scores; Inserimento; Cancellazione.
• Ordinamento di un array: InsertionSort
• Liste linkate semplici: L'oggetto Nodo; L'oggetto Lista.
• Liste linkate doppie: L'oggetto Nodo; Gestione della Lista; Inserimento e cancellazione. Test.
• Liste circolari
• InsertionSort su una lista linkata doppia

Stack e Queue

• Codice sullo Stack
• Codice sulla Queue

Le Liste e gli Iteratori

• PositionList

Alberi

• SimpleTree
  Semplice implementazione di un albero generico comprendente i metodi iterator() e positions()
• PositionTree
  Implementazione di un'interfaccia Tree che utilizza nodi che estendono l'interfaccia Position

Appunti e dispense

Fondamenti di programmazione

• Classi Boxed : (Boolean; Character; Byte; Short; Integer; Long; Float; Double)
• Principi dell'autoboxing
• Utilizzare il boxing con cura
• Utilizzare le classi boxed per dati opzionali
• Ritornare array vuoti piuttosto che null
• Non dichiarare variabili locali prima dell'uso
• Oggetti immutabili

Costruzione di oggetti

• Metodi static factory
• Esempio : Telescoping constructor
• Esempio : Oggetti Builder

I/O su file

• Principi di base sull'I/O su file
• Leggere file di caratteri : classe FileReader
• Scrivere file di caratteri : classe FileWriter
• Leggere file di token : classe Scanner
• Scrivere su file testo formattato : classe PrintWriter
• Leggere informazioni bufferizzate : classe BuferedReader
• Scrivere informazioni buferizzate : classe BufferedWriter
• Accesso casuale ai file : classe RandomAccessFile
• Esempio : Copia di file

Eccezioni

• Eccezioni e flusso di esecuzione
• Come utilizzare catch e finally
• Evitare blocchi catch vuoti
• Utilizzo della clausola throws
• Classe : Exception

Errori di programmazione e Debugging

• Top Ten errori di programmazione
• Tecniche e tool per il debugging
• Asserzioni in Java
• Evitare gli errori banali di stile

Temi di ottimizzazione

• Evitare l'utilizzo dei floating point
• Esempio : calcoli in valuta
• Concatenazione di stringhe