Differenze tra le versioni di "Algoritmi e strutture dati T2/2006-2007"

Da WikiDsy.
(→‎Lunedì 6 Novembre)
(→‎Venerdì 3 Novembre)
Riga 318: Riga 318:
  
 
*Heap
 
*Heap
 +
*La struttura dati ''Heap''
 +
**Costruzione di un Heap
 +
**Heapify
 +
*Uso degli Heap per implementare code con priorità
 +
*Heap sort
  
 
===Lunedì 6 Novembre ===
 
===Lunedì 6 Novembre ===
  
 
*Analisi dei costi di Heapsort
 
*Analisi dei costi di Heapsort

Versione delle 08:51, 8 nov 2006

News

.

  • La prossima lezione di laboratorio Giovedì 26 Ottobre si terrà ina aula attrezzata 309 (VIA CELORIA)



.

Informazioni generali

.

Docenti

Prof. Torelli / Prof. Aguzzoli per il laboratorio.

Corsi di laurea

Modalità d'esame

Orale + Progetto Pagina Ufficiale Modalita' d'esame

N.B

  • Non è possibile sostenere l'orale senza aver già consegnato il progetto
  • il progetto e l'orale devono essere svolti nello stesso appello

Orari e luogo delle lezioni

Lunedì Mercoledì Giovedì(laboratorio) Giovedi (laboratorio) Venerdì
18:30-20:00 Aula 202 (celoria). 20:00-21:30 Aula 202 (celoria). 18:30-19:30 Aula 202. 19:30-21:30 Aula PC settore didattico . 18:30-20:00 Aula 202 (celoria).


Orario di ricevimento studenti

  • Lunedì ore 10 -11 e martedì ore 18 -19, Via Comelico

-

Informazioni specifiche

Sito Ufficale del corso


N.B. Il Prof.Torelli tiene un Diario del corso sul suo sito che è sicuramente è più affidabile di quello che ci sforziamo di tenere sul dsy, riteniamo comunque utile portare avanti questo diario nella speranza che possa esser una risorsa aggiuntiva, non limitandosi a fornire un elenco degli argomenti svolti, ma più in generale fornendo notizie e informazioni sul corso, link e materiale inerente alle lezioni

Sito Ufficiale del laboratorio


Forum dsy Algoritmi

Forum su DSY.IT

Materiale Didattico

Programma del corso

Si può scaricare da qui


TESTI

Testo di riferimento

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill Italia, 2005 (oppure II edizione in inglese, 2002).


Altri Bibliografia

Testo per il laboratorio:

  • Al Kelley, Ira Pohl, C – Didattica e programmazione, Pearson/Addison-Wesley, 2004 (oppure A Book on C, 4a edizione, in inglese).

Bibliografia di consultazione:

  • M. Torelli, Appunti per il corso di Algoritmi e Strutture Dati, scaricabili da http://homes.dsi.unimi.it/~torelli/note.html
  • A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso di Algoritmi e Strutture Dati), scaricabili da http://homes.dsi.unimi.it/~goldwurm/algo/
  • R. Sedgewick, Algoritmi in C/C++, Addison-Wesley, 1993 (nuova edizione ampliata 2002).
  • A.J. Kfoury, R.N. Moll, M.A. Arbib, A programming approach to computability, Springer, 1982.


Altro materiale consigliato

Video delle lezioni

Le Videolezioni dell'anno accademico 2003/2004 sono disponibili sul sito Virtual Classroom

DISPENSE E LINK UTILI

Dispense prof Goldwurm

dispense Università di Urbino

dispense Università dell' Aquila

Compilatore GCC per Windows

Diario del corso

.

Lunedì 2 Ottobre 2006

  • Introduzione al corso e alle modalità di esame
  • Complessità del problema dell'ordinamento
    • che cosa si intende per complessità di un algoritmo
  • Algoritmo di Counting Sort (altro link utile per capire il counting sort)
  • Introduzione alle notazioni asintotiche O , Θ e Ω


Mercoledì 4 Ottobre 2006

  • Ripasso Algoritmo Counting Sort - .link utile .per capire il counting sort
  • Il concetto di algoritmo di ordinamento Stabile
  • La complessità di un Algoritmo
  • La complessità di un Problema
  • Confrontare la coplessità di algoritmi
  • Definizione formale delle notazioni asintotiche e relativi esempi

Giovedì 5 Ottobre 2006

.Laboratorio. http://homes.dsi.unimi.it/~aguzzoli/algo.htm

  • Introduzione alla parte di laboratorio del corso
  • Cenni storici sul linguaggio C
  • Caratteristiche generali del C
  • Lo standard ANSI C
  • primo programmino in c (il consueto Ciao Mondo)
  • Il compilatore (useremo Gcc)
  • Le direttive al preprocessore
    • Include
    • i file .h
  • Il concetto di funzione
  • Opzioni di Gcc
    • -ansi , -pedantic , -wall

Venerdì 6 Ottobre 2006

  • Analisi degli algoritmi (cap 2.2)
  • Analisi di Counting Sort

Lunedì 9 Ottobre

Mercoledì 11 Ottobre

  • Insertion Sort
  • Il concetto di ordinamento in loco
  • Gli Algoritmi Divide et Impera
    • Merge Sort
    • Esempi di merge sort con figure
    • Pseudocodice Merge Sort

Giovedì 12 Ottobre

.Laboratorio. http://homes.dsi.unimi.it/~aguzzoli/algo.htm

  • riassunto della Prima lezione
  • printf
    • Opzioni di printf
  • altri semplici programmini di esempio
  • C ed il passaggio per valore
  • L'utility make
  • introduzione ai puntatori
  • Bubble sort
  • Introduzione agli Array in C

Venerdì 13 Ottobre

  • Merge Sort: Albero delle chiamate ricorsive
  • Notazioni standard e funzioni comuni:
    • Funzione Floor
    • Funzione Ceiling
    • Funzione Monotone
    • Fattoriale
    • Formula di Stirling
    • Piccolo Teorema di Fermat
  • Ricorsione e Iterazione

Lunedì 16 Ottobre

  • Cap. 3.2 NOTAZIONI STANDARD E FUNZIONI COMUNI
    • Funzioni Monotone
    • Floor e ceiling
    • Aritmetica modulare
    • Polinomi
    • Esponenziali
    • Logaritmi
    • Fattoriali
    • Iterazione di una funzione
  • Ricorsione o ricorrenza
  • teorema di Fermat
  • Il classico (1202!) problema dei conigli

Mercoledì 18 Ottobre

  • Cap. 4 Ricorrenze
    • Il metodo di sostituzione
    • Il metodo dell’albero di ricorsione
    • Il metodo dell’esperto


  • (Il metodo iterativo (CENNI))
  • Il classico (1202!) problema dei conigli (soluzione)

http://utenti.quipo.it/base5/fibonacci/fibonacci.htm,

Giovedì 19 Ottobre

.Laboratorio.

Il 26 Ottobre si terrà la prima lezione in laboratorio. Sono state racolti i dati ( nome, cognome e matricola ) per attivare l'utenza di laboratorio

http://homes.dsi.unimi.it/~aguzzoli/algo.htm

  • Le stringhe sono array
  • Elementi lessicali, operatori, espressioni
  • Dichiarazioni, tipi fondamentali

Venerdì 20 Ottobre

come nella scorsa lezione

  • Cap. 4 Ricorrenze
    • Il metodo di sostituzione
    • Il metodo dell’albero di ricorsione
    • Il metodo dell’esperto

Esempi di utilizzo dei 3 metodi su la ricorsione

Lunedì 23 Ottobre

  • Ancora ricorsione
  • Numeri di Fibonacci
  • La formula di Eulero-Binet

Mercoledì 25 Ottobre

  • la formula di Eulero - Binet
  • nozioni di insiemistica(unione,intersezione....relazioni)
  • Accenno ai linguaggi

Giovedì 26 Ottobre

.Laboratorio.

  • Svolti esercizi in aula attrezzata


Venerdì 27 Ottobre

Dispense usate per questa lezione

  • Grafi e Alberi come Linguaggi
    • Grafi Orientati
    • Grafi non orientati
  • Alberi


Lunedì 30 Ottobre

  • I Grafi come linguaggi
    • Grafi Orientati
    • Grafi Non orientati
    • Cammini e Cicli
    • Lemma di Eliminazione dei cicli
    • Il concetto di Grado di un vertice
    • Grafi connessi
    • sottografi
  • Alberi Binari
  • Alberi k-Ari
  • Alberi Completi a sx.
  • alberi pienamente Binari
  • Heap

Mercoledì 1 Novembre

Festa

Giovedì 2 Novembre

.Laboratorio.

  • Inuput ed Output con getchar e putchar
  • Input ed Output su file
  • Operatori logici
  • Controllo del flusso
    • If - Else
    • for
    • While
    • Do-While
    • Break
    • Continue
    • Switch
  • Funzioni e stack
  • Protottipi di funzione


Venerdì 3 Novembre

  • Heap
  • La struttura dati Heap
    • Costruzione di un Heap
    • Heapify
  • Uso degli Heap per implementare code con priorità
  • Heap sort

Lunedì 6 Novembre

  • Analisi dei costi di Heapsort
Estratto da "https://wiki.dsy.it/index.php?title=Algoritmi_e_strutture_dati_T2/2006-2007&oldid=16330"