Algoritmi e strutture dati T1/2007-2008

Indice

1 AVVISI
2 Orari
3 Scaglione alfabetico
4 Docenti
5 Programma
6 Orari ricevimento
7 Altre informazioni e links
8 Siti del corso
9 Materiale didattico
10 Diario del corso

AVVISI

La prima lezione di laboratorio sarà martedì 2 ottobre in aula G11 (Settore Didattico, via Celoria)
La lezione di martedì 2 ottobre non si terrà.
Da giovedi 11 ottobre le lezioni ed i laboratori tranne il laboratorio di venerdì si svolgeranno in aula V2
Nuova variazione: il laboratorio di martedì si svolge in aula 309

Orari

Lezione
- Lunedì, 10:30-12:30, aula V2
- Martedì, 08:30-10:30, aula V2
- Giovedì, 08:30-10:30, aula V2
- Venerdì, 10:30-12:30, aula 405

Laboratorio
- Martedì, 10:30-12:30, aula 309
- Giovedì, 10:30-12:30, aula V2

Scaglione alfabetico

Il turno è unico.

Docenti

Massimiliano Goldwurm (teoria)

Camillo Fiorentini (laboratorio)

Programma

Orari ricevimento

Altre informazioni e links

Siti del corso

Materiale didattico

Diario del corso

Lezione 01/10/2007

Definizione di algoritmo
Definizione di problema
Tipi di problemi
1. di decisione
2. di ricerca
3. di conteggio
4. di ottimizzazione
Complessità di un algoritmo
Tipi di difficoltà (problematiche)
1. SINTESI
2. ANALISI
3. CLASSIFICAZIONE

Lezione 02/10/2007

lezione annullata

Laboratorio 02/10/2007

Presentazione
Caratteristiche del linguaggio C
Differenze e somiglianze con JAVA
- C è per la programmazione strutturata, non ad oggetti
- In C non esistono i metodi ma le funzioni, + o - eguali ai metodi statici di JAVA
- C non è cross-latform, va ricompilato per ogni computer
- (...)
Compilazione: codice sorgente -> pre-processore -> codice sorgente preprocessato -> compilatore -> codice oggetto -> linker -> codice eseguibile
#INCLUDE

Lezione 04/10/2007

non ho potuto partecipare alla lezione, aggiungete particolari se riuscite

Macchina RAM
Istruzioni macchina RAM
Semantica del linguaggio RAM
Nozione di stato
Nozione di transizione fra stati

Laboratorio 04/10/2007

Processo dal file srgente alleseguibile:

Passaggio 1: pre-processazione
- gcc -E nomefile.c esegue solo la precompilazione
- Direttive al pre-processore
  1. #DEFINE
  2. #INCLUDE
Passaggio 2: compilazione
- gcc -c nomefile.c esegue la precompilazione e la compilazione
- risultato in file codice oggetto binario (xxx.o)
- le funzioni di cui c'è il prototipo (inserito o meno in fase di pre-compilazione) non sono sostituite dal loro codice, lo fa il linker al passaggio successivo.
Passaggio 3: linking
- collega i prototipi al loro codice
- Modularità
  - gcc x1.o x2.o unisce i due files compilati separatamente
  - ci deve essere un solo main in almeno uno dei file uniti assieme
  - non ci devono essere più definizioni della stessa funzione

ALTRO:

gcc -ansi nomefile.c esegue la compilazione secondo lo standard ANSI
gcc -pedantic nomefile.c esegue la compilazione con un livello di dettaglio del debug estremamente avanzato
gcc -Wall nomefile.c esegue la compilazione con tutti i warning

Lezione 05/10/2007

Proprietà della computazione
Criteri di costo
- Uniforme
- Logaritmico
Esempi

Lezione 08/10/2007

Criterio uniforme e criterio logaritmico
Costo delle operazioni della macchina RAM con criterio logaritmico
Esempi di valutazione di spazio e tempo con i due criteri e paragone dei risultati

Lezione 09/10/2007

Notazione asintotica
Relazioni e loro significato
- asintotico
- O grande
- o piccolo
- Omega grande
- Ordine di grandezza
Regole generali di confronto
Rapporti fra relazioni

Laboratorio 09/10/2007

printf
scanf
if..then
esempi ed esercizi in classe (vedere dispense di laboratorio)

Lezione 11/10/2007

Ripasso relazioni (o piccola, ...)
Sommatorie
- le più comuni: geometrica, somme di polinomi
Primi due metodi per calcolare le somme:
- derivazione
- perturbazione

Laboratorio 11/10/2007

Variabili
- attributi
  1. nome
  2. tipo
  3. valore
Funzioni
- parametri
- si raccomanda di documentarle
- il return di un valore di tipo errato determina un cast automatico
Prototipi
- definizione
Record di attivazione delle funzioni
- contenuti
  1. variabili locali
  2. informazioni per poter riprendere il programma chiamante all'istruzione giusta
- allocato nello stack di sistema con procedura LIFO
- PUSH/POP
Variabili globali
Criteri di visibilità
Tempo di vita di una variabile

Lezione 12/10/2007

Terzo metodo per calcolare le somme:
- integrazione per funzioni decrescenti e crescenti monotone
vari esempi di applicazione dell'integrazione
ripresa della Formula di Stirling

Lezione 15/10/2007

non ero presente, aggiungerò gli argomenti appena possibile

Lezione 16/10/2007

Vettori
Matrici
Record
Tabelle
esempi

Laboratorio 16/10/2007

Input/output
- caratteri e loro rappresentazione
- getchar()
- redirezione dello standard input
- end-of-file
- putchar()
- redirezione output
Esercizi

Lezione 18/10/2007

Liste (non ero presente, se potete aggiungere particolari ve ne sarei grato)

Laboratorio 18/10/2007

Espressioni
- semplici
  - costanti
  - variabili
- composte (espressioni aritmetiche, invocazione metodi)
Puntatori
- assegnamenti fra puntatori (compatibilità di tipo)
- esempi
- Dereferenziazione di un puntatore (operatore *)

Lezione 19/10/2007

Pile
- Insiemi utili per la definizione
- Operazioni
  - IS_EMPTY
  - TOP(S)
  - POP(S)
  - PUSH(S, u)
- Implementazioni delle pile
  - Tabella
  - Lista concatenata
Code
- Insiemi utili per la definizione
- Operazioni
  - IS_EMPTY
  - FRONT(Q)
  - DEQUEUE(Q)
  - ENQUEUE(Q, u)
- Implementazioni delle code
  - Tabella
  - Lista concatenata
Allineamenti ed insiemi
- allineamenti
  1. permutazione
  2. disposizione
    - semplice
    - complessa
- insiemi
  1. combinazione
    - semplice
    - complessa

Lezione 22/10/2007

Grafi
- non orentati
- orientati
Implementazioni
- matrice
- coppia di tabelle
- lista concatenata
definizione di cammino
definizione di ciclo
definizione di sottografo
definizione di grafo connesso
relazione di connessione
- proprietà: transitiva, riflessiva, generalmente non simmetrica
relazione di raggiungibilità

Lezione 23/10/2007

alberi
albero di copertura
foresta
albero con radice
rappresentazione di albero tramite tabella
clique
indipendent set
padre,figlio,foglia,radice,fratelli,predecessore,successore, altezza, profondità
albero bilanciato

Laboratorio 23/10/2007

esercizi su puntatori
esercizi su frazioni e passaggio parametri

Lezione 25/10/2007

visita di grafi per ampiezza
esercizi

Laboratorio 25/10/2007

ripasso tipi di dato
revisione esercizi del laboratorio precedente

Lezione 26/10/2007

alberi ordinati
- rappresentazione in memoria
  - liste di adiacenza
  - 3 vettori
- Tipi di attraversamento
  - in preordine
  - in postordine
alberi binari
- alberi binari completi
- rappresentazione in memoria
  - 2 vettori
- Tipi di attraversamento
  - in preordine
  - in postordine
  - in ordine simmetrico

Lezione 29/10/2007

ero assente

Lezione 30/10/2007

ricorsione terminale
procedura di ricerca binaria
- tempi e spazi (criterio uniforme)
attraversamento in preordine
- procedura
- versione iterativa
attraversamento in profondità
- procedura
- versione iterativa

Laboratorio 30/10/2007

esercizi su equazioni e interi

Lezione 01/11/2007

vacanza

Lezione 05/11/2007

Mergesort
- ordine di grandezza (tempo e spazio) di Mergesort

Lezione 06/11/2007

non c'ero

Lezione 08/11/2007

da svolgersi