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

Orari

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

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

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 12/10/2007

da svolgersi