Algoritmi e strutture dati T1/2007-2008

Da WikiDsy.
Versione del 19 nov 2007 alle 16:18 di Joliet Jake (discussione | contributi) (→‎Lezione 08/11/2007)


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

non c'ero

Laboratorio 08/11/2007

  • aritmetica dei puntatori
  • esercizi sugli array

Lezione 09/11/2007

  • prodotto di matrici
  • algoritmo di strasse
  • esercizi vari con calcolo di tempi di cacolo e spazi di memoria

Settimana 12/11/2007->16/11/2007

non ero a Milano

Lezione 19/11/2007

  • strutture dati astratte
  • dizionari
  • dizionari ordinati
  • partizioni
  • hashing

Lezione 20/11/2007

da svolgersi

Estratto da "https://wiki.dsy.it/index.php?title=Algoritmi_e_strutture_dati_T1/2007-2008&oldid=18177"