Tags:
create new tag
view all tags

Programma di massima A.A. 2020/21

(questo č un programma di massima; per il programma dettagliato di quest'anno consultare il diario delle lezioni)

  • Introduzione
    • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale;
    • modello RAM; misura di costo uniforme e logaritmico.
  • Notazione asintotica
    • Definizione e significato degli insiemi O, Ω e Θ
  • Il problema della ricerca
    • Ricerca sequenziale in un vettore disordinato;
    • costo computazionale nel caso migliore, peggiore e medio
    • Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
    • costo computazionale nel caso migliore, peggiore e medio
  • Introduzione alla ricorsione
    • funzioni ricorsive
    • versione iterativa e ricorsiva di algoritmi: esempi
    • occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci
    • calcolo del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
      • metodo di sostituzione
      • metodo iterativo
      • metodo dell'albero
      • teorema principale ( dimostrazione facoltativa )
  • Il problema dell'ordinamento
    • algoritmi naif: filosofia, pseudocodice e costo computazionale
      • insertion, selection e bubble sort
    • limitazione inferiore sul costo computazionale degli algoritmi di ordinamento per confronti; dimostrazione
    • funzione di fusione e merge sort; cenno alla tecnica del divide et impera
    • ordinamento in tempo lineare: counting sort e bucket sort
    • quick sort e suo costo computazionale nel caso peggiore, migliore e medio
    • heap e heap sort
  • Strutture dati fondamentali
    • insiemi dinamici ed operazioni su di essi
    • vettore non ordinato e ordinato
    • pila e coda, funzioni di inserimento ed estrazione, coda circolare
    • lista semplice e doppiamente puntata
    • coda con prioritā
    • albero
      • definizione come grafo connesso aciclico
      • teorema di caratterizzazione degli alberi e dimostrazione
      • alberi radicati, alberi binari, alberi ordinati, alberi binari completi
      • relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo
      • rappresentazione in memoria di un albero binario
        • rappresentazione posizionale
        • rappresentazione con puntatori
        • vettore dei padri
      • visita in pre-, post- ed in-ordine e calcolo del costo computazionale tramite equazione di ricorrenza
  • Dizionari
    • indirizzamento diretto
    • tabelle hash
      • collisioni
      • soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico)
      • costo computazionale nel caso medio
      • soluzioni delle collisioni con indirizzamento aperto
      • vari tipi di scansione (lineare, quadratica ed hashing doppio)
      • costo computazionale nel caso medio
    • alberi binari di ricerca
      • definizione
      • algoritmo di ricerca e suo costo computazionale
      • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
      • algoritmo di inserimento e suo costo computazionale
      • algoritmo di cancellazione e suo costo computazionale
    • la problematica del bilanciamento per la limitazione del costo computazionale
      • alberi red black e teorema per la limitazione dell'altezza ( rotazioni ed altri dettagli facoltativi )
Topic revision: r1 - 2021-02-03 - AngeloMonti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback