Tags:
create new tag
view all tags

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-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