Programma 2017–2018

Suggerimento gene­ra­le

Per tut­ti gli argo­men­ti, è neces­sa­rio conoscere:

  • il pro­ble­ma che si vuo­le risolvere
  • l’al­go­rit­mo o gli algo­rit­mi che lo risolvono
  • la com­ples­si­tà del­le soluzioni

Complessità

  • Valutazione com­ples­si­tà
  • Notazione asin­to­ti­ca, defi­ni­zio­ne, proprietà
  • Risoluzione ricor­ren­ze
  • Master theo­rem
  • Analisi ammor­tiz­za­ta
    • Metodo degli accantonamenti
    • Metodo del­l’ag­gre­ga­zio­ne
    • Metodo del potenziale

Algoritmi di ordinamento

  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Counting Sort
  • Pigeonhole Sort
  • Bucket Sort
  • Limite infe­rio­re per l’ordinamento

Strutture dati 

  • Alberi
    • Definizione
    • Implementazioni
    • Visita {in,pre,post}-ordine
    • Visita in ampiezza
  • Alberi bina­ri di ricer­ca: defi­ni­zio­ne e implementazione 
    • Ricerca, Inserimento, Cancellazione
    • Successore/predecessore, minimo/massimo
  • Alberi Red-Black
    • Principi gene­ra­li dell’implementazione
    • Rotazione, inse­ri­men­to (solo cen­ni, non sottocasi)
  • Tabelle hash
    • Tabelle ad indi­riz­za­men­to diretto
    • Funzioni hash: meto­do del­la divisione
    • Funzioni hash: meto­do del­la moltiplicazione
    • Inserimento e cancellazione
    • Concatenamento
    • Indirizzamento aper­to
      • Ispezione linea­re
      • Ispezione qua­dra­ti­ca
      • Doppio hashing
  • Heap bina­ri: defi­ni­zio­ne e implementazione 
    • Max/MinHeapify
    • BuildMax/MinHeap
    • Heapsort
  • Merge-Find Set
    • Implementazione basa­ta su lista
    • Implementazione basa­ta su alberi
    • Euristica sul peso
    • Euristica sul rango
    • Euristica del­la com­pres­sio­ne dei cammini

Grafi

  • Definizioni prin­ci­pa­li
  • Implementazione
  • Visite in ampiez­za e applicazioni 
    • Cammini mini­mi
  • Visite in pro­fon­di­tà e applicazioni 
    • Individuazione cicli
    • Ordinamento topo­lo­gi­co
    • Componenti con­nes­se
    • Componenti for­te­men­te connesse
  • Alberi mini­mi di copertura 
    • Definizione mate­ma­ti­ca del problema
    • Kruskal
    • Prim
  • Cammini mini­mi, sin­go­la sorgente 
    • Definizione mate­ma­ti­ca del problema
    • Dijkstra
    • Johnson
    • Fredman-Tarjan
    • Bellman-Ford
    • Cammini mini­mi su DAG
  • Cammini mini­mi, sor­gen­ti multiple 
    • Floyd-Warshall
    • Chiusura tran­si­ti­va
  • Problemi di flusso 
    • Definizione mate­ma­ti­ca di rete di flus­so, flusso
    • Metodo del­le reti residue
    • Ford-Fulkerson
    • Edmonds-Karp
    • Abbinamento gra­fi bipartiti

Divide-et-impe­ra

  • Descrizione del­la tecnica
  • Moltiplicazione gran­di nume­ri (Karatsuba), prin­ci­pi gene­ra­li (no formule)
  • Moltiplicazione di matri­ci (Strassen), prin­ci­pi gene­ra­li (no formule)

Programmazione dina­mi­ca

  • Descrizione del­la tecnica
  • Zaino sen­za limiti
  • Sottosequenza comu­ne massimale
  • String mat­ching approssimato
  • Prodotto di cate­na di matrici
  • Insieme indi­pen­den­te di inter­val­li pesati

Greedy

  • Descrizione del­la tecnica
  • Insieme indi­pen­den­te di intervalli
  • Resto
  • Scheduling
  • Zaino fra­zio­na­rio
  • Compressione di Huffman

Backtrack

  • Descrizione del­la tecnica
  • Enumerazione
    • Sottoinsiemi
    • Permutazioni
  • Inviluppo con­ves­so

Algoritmi pro­ba­li­sti­ci

  • Descrizione del­la tecnica
  • Primalità
  • QuickSort pro­ba­ba­li­sti­co
  • Problema del­la selezione/mediana

NP-Completezza

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

Problemi appros­si­ma­ti

  • Algoritmi pseu­do-poli­no­mia­li
  • Algoritmi di approssimazione
  • Algoritmi branch-&-bound
  • Algoritmi euri­sti­ci
Scroll to top