Programma

Prima parte del programma — Prima prova parziale

Introduzione

  • Cos’è un algoritmo
  • Come descri­ve­re gli algo­rit­mi (pseu­do­co­di­ce)
  • Come valu­ta­re gli algoritmi
  • Algoritmi discus­si a lezione: 
    • Ricerca del minimo
    • Ricerca dico­to­mi­ca

Analisi degli algoritmi

  • Modelli di calcolo
  • Funzioni di costo
  • Complessità algo­rit­mi vs com­ples­si­tà problemi
  • Limiti asin­to­ti­ci supe­rio­ri e inferiori
  • Analisi di ricorrenze 
    • Metodo di sostituzione
    • Metodo del­l’al­be­ro di ricorrenza
    • Metodo del­l’e­sper­to
  • Algoritmi discus­si a lezione: 
    • Moltiplicazione di Karatsuba
    • Selection Sort
    • Insertion Sort
    • Merge Sort

Strutture dati astratte

  • Sequenza
  • Insiemi
  • Dizionari
  • Alberi e grafi
  • Algoritmi discus­si a lezione: 
    • Lista bidi­re­zio­na­le con/senza sentinella
    • Pila basa­ta su vettore
    • Coda basa­ta su vet­to­re circolare

Analisi ammor­tiz­za­ta

  • Metodo del­l’ag­gre­ga­zio­ne
  • Metodo del­l’am­mor­ta­men­to
  • Metodo del potenziale
  • Algoritmi discus­si a lezione: 
    • Contatori bina­ri
    • Vettori dina­mi­ci

Alberi

  • Definizioni
  • Realizzazioni
    • Con vet­to­re dei figli
    • Con padre/primo figlio/fratello
    • Con vet­to­ri dei padri
    • Alberi bina­ri
  • Algoritmi discus­si a lezione: 
    • Visita in profondità
    • Visita in ampiezza

Alberi bina­ri di ricerca

  • Alberi bina­ri di ricerca
  • Alberi bilan­cia­ti di ricerca 
    • Alberi Red-Black
  • Algoritmi discus­si a lezione: 
    • Ricerca, inse­ri­men­to, cancellazione
    • Successore, pre­de­ces­so­re
    • Minimo, mas­si­mo
    • Rotazioni in albe­ri Red-Black
    • Inserimento in albe­ri Red-Black
    • Cenni sul­la can­cel­la­zio­ne in albe­ri Red-Black

Grafi

  • Definizioni
  • Realizzazioni
    • Liste/vettori di adiacenza
    • Matrici di adiacenza
  • Visite
    • Visita in profondità
    • Visita in ampiezza
  • Algoritmi basa­ti sul­le visite: 
    • Distanza
    • Ordinamento topo­lo­gi­co
    • Grafi aci­cli­ci
    • Componenti con­nes­se
    • Componenti for­te­men­te connesse

Tabelle hash

  • Funzioni hash
    • Metodo del­la moltiplicazione
    • Metodo del­la divisione
  • Metodi di scansione 
    • Scansione inter­na
    • Scansione ester­na
  • Algoritmi discus­si a lezione: 
    • Tabella hash con scan­sio­ne inter­na basa­ta su dop­pio hashing

Insiemi

  • Vettori boo­lea­ni
  • Liste/vettori non ordinati
  • Liste/vettori ordi­na­ti
  • Alberi bilan­cia­ti
  • Tabelle hash
  • Bloom fil­ters

Strutture dati speciali

  • Alberi heap
  • Code con priorità
  • Algoritmi discus­si a lezione 
    • Heapsort

Seconda parte del programma — Seconda prova parziale

Strutture dati speciali

  • Insiemi disgiun­ti
  • Algoritmi discus­si a lezione 
    • Insiemi disgiun­ti basa­ti su euri­sti­ca sul ran­go e com­pres­sio­ne dei cammini

Strutture dati e pro­get­ta­zio­ne di algoritmi

  • Problema dei cam­mi­ni minimi
  • Algoritmi discus­si a lezione: 
    • Algoritmo di Dijkstra
    • Algoritmo di Johnson
    • Algoritmo di Fredman-Tarjan
    • Algoritmo di Bellman-Ford-Moore

Programmazione dina­mi­ca

  • Zaino 0/1, con varianti
  • Sottosequenza comu­ne massimale
  • String mat­ching approssimato
  • Prodotto di cate­na di matrici
  • Insieme indi­pen­den­te inter­val­li pesati
  • Cammini mini­mi fra tut­te le coppie

Algoritmi gree­dy

  • Zaino rea­le
  • Insieme indi­pen­den­te di intervalli
  • Problema del resto
  • Minimo albe­ro di copertura 
    • Algoritmo di Kruskal
    • Algoritmo di Prim
  • Compressione di Huffman

Backtrack

  • Enumerazione
    • Sottoinsiemi
    • Permutazioni
    • Problema del­le n regine
    • Giro di cavallo
    • Sudoku
  • Inviluppo com­ples­so (no in 2022/23)
    • Algoritmo di Graham

Ricerca loca­le

  • Schema gene­ri­co di ricer­ca locale
  • Reti di flusso 
    • Ford-Fulkerson
    • Edmonds-Karp

Algoritmi pro­ba­bi­li­sti­ci

  • Primalità
  • Bloom fil­ters
  • Quicksort pro­ba­bi­li­sti­co
  • Problema del­la sele­zio­ne o del­la mediana
    • Soluzione pro­ba­bi­li­sti­ca
    • Soluzione deter­mi­ni­sti­ca

Ordinamento

  • Limiti infe­rio­ri per l’ordinamento
  • Counting Sort
  • Pigeonhole Sort (no 2022/23)
  • Bucket sort (no 2022/23)
  • Stabilità degli algo­rit­mi di ordi­na­men­to (no 2022/23)

Solo orale

NP-Completezza

  • Definizione
  • Riduzione
  • Classe P
  • Classe NP
  • Problemi NP-com­ple­ti

Soluzioni per pro­ble­mi intrattabili

  • Algoritmi pseu­do-poli­no­mia­li
  • Algoritmi di approssimazione
  • Algoritmi branch-&-bound
  • Algoritmi euri­sti­ci
  • Algoritmi visti
    • Subset sum, pseudopolinomiale
    • Partition
    • Bin-pac­king
    • Algoritmo appros­si­ma­to per Delta-TSP
    • TSP gree­dy
    • TSP ricer­ca locale
    • TSP branch-&-bound
Scroll to top