Algoritmi e strutture dati T1/2007-2008

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

• Programma del corso
• Programma di laboratorio

Orari ricevimento

• Massimiliano Goldwurm
• Camillo Fiorentini

Altre informazioni e links

• Modalità d'esame
• Forum di Algoritmi su DSY
• Files di Algoritmi su DSY

Siti del corso

• Sito del corso
• Sito del laboratorio

Materiale didattico

• Dispense e testi consigliati
• Esercizi e temi d'esame
• Ultimi temi d'esame (ps,pdf)

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

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

Lezione 22/10/2007

da svolgersi