Contenuti del corso

Questo corso si compone di due parti che saranno portate avanti parallelamanete.

La prima, di circa 60 ore, si occuperà della descrizione e progettazione di algoritmi efficienti; la seconda, di circa 30 ore, si occuperà di programmazione.

Descrizione e progettazione di algoritmi efficienti

  • Introduzione
    • Concetti di algoritmo, di struttura dati, di efficienza; di complessita' 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;
    • complessita' nel caso migliore, peggiore e medio
    • Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
    • complessita' 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 della complessita' delle funzioni ricorsive tramite equazioni di ricorrenza
      • metodo di sostituzione
      • metodo iterativo
      • metodo dell'albero
      • teorema principale (senza dimostrazione)
  • Il problema dell'ordinamento:
    • algoritmi naif: filosofia, codice e complessita'
    • limitazione inferiore sulla complessita' degli ordinamenti per confronti; dimostrazione
    • funzione di fusione e merge sort; cenno alla tecnica del divide et impera
    • quick sort e sua complessita' nel caso peggiore, migliore e medio
    • heap e heap sort
    • ordinamento in tempo lineare: counting sort
  • Strutture dati fondamentali
    • insiemi dinamici ed operazioni su di essi
    • vettore non ordinato e ordinato
    • lista semplice e doppiamente puntata
    • pila e coda, funzioni di inserimento ed estrazione, coda circolare
    • coda con priorità
    • albero
      • definizione come grafo connesso aciclico
      • teorema di caratterizzazione degli alberi
      • alberi radicati, alberi binari, 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 della complessita' tramite equazione di ricorrenza
  • Dizionari
    • indirizzamento diretto
    • tabelle hash
      • scansione lineare
      • scansione quadratica
      • hashing doppio e relative prestazioni (senza dimostrazione)
    • alberi binari di ricerca
      • definizione
      • algoritmo di ricerca e sua complessita'
      • algoritmo di inserimento e sua complessita'
      • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'
      • algoritmo di cancellazione e sua complessita'
    • la problematica del bilanciamento (alberi red-black)
      • rotazioni e cambi di colore
      • complessità del bilanciamento
  • Grafi
    • rappresentazione in memoria
      • liste di adiacenza
      • matrice di adiacenza
      • matrice di incidenza
      • lista di archi
      • confronto della complessita' spaziale e temporale in alcune operazioni elementari
    • visita in ampiezza (BFS)
      • definizione di albero ricoprente
      • proprietà degli archi non dell'albero
      • proprieta' della distanza dalla radice
    • visita in profondita' (DFS)
      • proprietà degli archi non dell'albero
      • proprieta' del numero di archi in funzione della lunghezza del cammino più lungo
    • similitudini e differenze tra le due visite
    • loro complessita' al variare della struttura dati usata
    • Algoritmo di Dijkstra per il calcolo dei cammini minimi
      • funzionamento
      • pseudocodice
      • complessità
      • dimostrazione della correttezza

Programmazione

Per i contenuti di questa parte si vedano le informazioni fornite dal prof. Franceschini su questa pagina.

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2021-01-22 - GiancarloBongiovanni






 
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-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback