Insegnamento di Complessità computazionale

Materiale didattico dell'insegnamento

A partire dall'anno accademico 2011/12, il materiale didattico, i temi d'esame e i commenti alle prove d'esame sono pubblicati sul sito "elearning" dell'Università di Verona.

Per comodità, le pagine di accesso al sito sono:

Per chi non è iscritto al sito di elearning, può consultare direttamente solo la raccolta dei temi d'esame.

Errata corrige della dispensa del corso

Per le versioni 1.3 e successive non è disponibile una errata corrige via web perché gli errori sono praticamente solo di battitura (tranne due casi, risolti dalla versione 1.3.2).

Errata corrige 1.2.1

La seguente tabella rappresenta l'errata corrige per la versione 1.2.1 della dispensa 'Dispensa del corso di complessità computazionale'.

PaginaRigaTesto erratoTesto correttoData inserimento
09-14quantoquando13/10/2011
11-12 alla -4. Tutte le occorenze di "quanti"unità13/10/2011
11-7uguaglianzerelazioni13/10/2011
18L'esercizio 2.2 è una ripetizione dell'esercizio 2.1: cancellare.13/10/2011
32penultima riga tabella in fondo paginaO(l(i)+l(ri))O(l(ri))11/10/2011
32ultima riga tabella in fondo paginaO(l(i)+l(ri)+l(rri))O(l(ri)+l(rri))11/10/2011
333l(i)+l(ri)+l(ri)+11/10/2011
335l(r0)+l(i)+l(r0)+11/10/2011
43-8solo una voltaesattamente due volte se il grafo non è diretto, solo una volta altrimenti20/10/2011
43-7|E|2|E| se il grafo non è diretto, |E| altrimenti20/10/2011
70Commento dopo 3a riga algoritmo 6.2il simbolo a sinistra del simbolo correnteil simbolo a sinistra di ";q;"06/11/2011
716=O(n log n f(n)2)=O((log n) n f(n)2)06/11/2011
42Subito dopo la dimostrazioneAggiungere la seguente nota:
"La versione più forte del Teorema dell'accelerazione lineare stabilisce che se un linguaggio L è decidibile da una MdT M in tempo f(n) e f(n)=ω(n), allora per ogni d>0 esiste un n0 intero e una MdT M' che decide L in tempo d·f(n) per ciascun n≥n0."
15/11/2011
79-2Se la complessità computazionale di r è limitata opportunamente, è ragionevole pensare che se L1 si riduce a L2, allora L2 difficile almeno quanto L1.Se la complessità computazionale di r è limitata opportunamente, è possibile pensare che  "L1 è non più difficile da decidere di quanto lo sia L2".15/11/2011
802Sostituire il testo della Nota!Il concetto “L1 è non più difficile da decidere di quanto lo sia L2” è anche espresso come "L2 è difficile almeno quanto L1" intendendo che se è possibile decidere in modo efficiente L2, allora è possibile decidere in modo efficiente anche L1 mentre nulla si può dire circa la complessità di decidere L2 se si conosce solo che si può decidere in modo efficiente L1.15/11/2011
87riga 2 col 2 Tabella 7.3σq2x2q221/11/2011
92-16(¬a ∨ b) ∈ φ ∨ (b ∨ ¬ a) ∈ φ(¬a ∨ b) ∈ φ16/01/2012
1179 e 10 dell'algoritmo end if
Y2 = Y2 ∪ {xj}
else
Y2 = Y2 ∪ {xj}
end if
09/12/2011
949almeno l'espressionel'espressione11/12/2011
9410al più 7esattamente 711/12/2011
9712la cricca di cardinalità minimauna cricca di cardinalità minima11/12/2011
9713il ricoprimentoun ricoprimento11/12/2011
115Dimostrazione Teorema 8.3tutte le occorrenze di m*(x)sostituirle con m*(f(x))20/12/2011

Errata corrige 1.2

La seguente tabella rappresenta l'errata corrige per la versione 1.2 della dispensa 'Dispensa del corso di complessità computazionale'.

PaginaRigaTesto erratoTesto correttoData segnalazione
56-7G''G22/10/2009
576di lunghezza n e senza nodi ripetuticancellare, altrimenti l'esercizio è banale!23/10/2009
61-34-NMdT5-NMdT30/10/2009
64-7...rispetto alle operazioni di unione e concatenazione....rispetto all'operazione di unione.03/11/2009
65-6A tal fine, sia M0,M1,... un'enumerazione delle MdT.A tal fine, sia M0,M1,... l'ordine lessicografico delle MdT.06/11/2009
65-4Si sostituisca la definizione di P(i,k)∀ i, k≤0, P(i, k) ="ogni MdT Mj con 0≤j≤i termina o entro k passi oppure dopo 2k passi quando l'input ha lunghezza i (una computazione può anche non terminare)"06/11/2009
663k'1=2ik'1=006/11/2009
6612La funzione f ha un andamento molto irregolare e cresce molto rapidamente.La funzione f ha un andamento
  molto irregolare e cresce molto rapidamente ma è computabile e, per ogni i, P(i, f(i)) è vera.
06/11/2009
6615Per come è stata costruita f,Dato che P(|x|, f(|x|)) è vera per costruzione,06/11/2009
66-18descrescentedecrescente06/11/2009
68-17cancellare cosidetto 06/11/2009
7119delle complessitàdella complessità08/11/2009
5322O(m(2− 2/(k-1))n).O(poly(n) (2−2/(k+1))n).09/11/2009
17etichetta del nodo padre dei nodi 'non trattabili' e 'trattabili' è errata!decidibili11/11/2009
8818-20il simbolo di funzione SB13/11/2009
83Figura 7.4il nodo 4 è un nodo con bordo semplice mentre dovrebbe essere doppiodisegnare il bordo con una doppia linea per indicare che è il nodo di output09/12/2009
92Figura 7.6(a) disegnare l'arco orientato (¬x2, ¬x1)11/01/2010

Errata corrige 1.0

La seguente tabella rappresenta l'errata corrige per la versione 1.0 della dispensa 'Dispensa del corso di complessità computazionale'.

Pag.RigaTesto erratoTesto correttoData segnalazione
5-6per y e per zper y e per w-
7-14O(n2 2n)O(n 2n)-
228qSqY,-
31-7è in nuovoè il nuovo-
357Semplificando un po' le cose, si osservaSi osserva-
359l(32k) = 2k log 3.l(32k) = 2k log 3 per k = 1,..., x = 2n.-
35112k)c 2k)-
3512cl e c3 sonocl e c sono-
3520La cifra 6 nell'espressione deve essere sostituita con 7. 22/08/2006
36-6Nq,σj+7   ADD dNq,σj+7   ADD =d-
3711carattere)v correnti).carattere) correnti).-
3717dei f(n) passidegli f(n) passi-
41-11dal Algoritmodall'Algoritmo-
43-7Si itera il procedimento sul grafo G' e flusso f'.Si itera il procedimento sul grafo G e flusso f'.21/11/2005
446dal Algoritmodall'Algoritmo-
4411costruisci N'(f) secondo...Costruisci N'(f) a partire da G e da f secondo...21/11/2005
48-4nel Algoritmodall'Algoritmo-
507L'algoritmo M è dato in dettaglio nel Algoritmo 4.4.Il funzionamento di M è dato in dettaglio dall'Algoritmo 4.4.-
518, già presentato nel Algoritmo 4.3, vedi Algoritmo 4.3-
53-8 Attenzione inoltre a non commettere l'errore di risolvere un'istanza del complemento di CAMMINO HAMILTONIANO ricorrendo all'algoritmo non-deterministico per quest'ultimo e negando quindi la risposta: per la definizione di accettazione di una computazione non deterministica non è possibile costruire computazioni non-deterministiche mediante la composizione delle stesse.21/11/2005
5422quantificata φquantificata φ in forma normale congiunta.-
558Si specializzi l'algoritmo del Algoritmo 4.1Si specializzi l'Algoritmo 4.1-
5512dell'algoritmo nel Algoritmo 4.3dell'Algoritmo 4.3-
5922una 2-MdTuna 3-MdT-
59-12≤ 4 log|x|≤ 3 log|x|-
61-5, -10, -26n|x|-
63-17se n = p q con p e q primise esiste m > 0 tale che n = pm con p primo22/08/2006
65-5(2n+1 - 2)(2n+1 - 1)22/08/2006
67-6|Σ|}|Σ|-1}-
6820``ε;qS;x´´``▹;qS;x´´-
68-10Prima della riga, aggiungereIl tempo di inizializzazione del nastro 2 è O(|encode(x)|}.-
68-7O(1) per implementare la transizione sul nastro 2.O(lM) passi per implementare la transizione sul nastro 2. lM = O(log n) è il numero di bit necessari per rappresentare un simbolo di M: infatti dalla definizione della codifica encode(M), si determina che |encode(M)| ≤ 2 lM + ( 3 lM + ( 2 lM )k ) 22lM, quindi lM = O(log |encode(M)|) = O(log n).21/11/2005
68-6Se la computazione di M ha complessità in tempo O(f(|x|)), allora la complessità in tempo della computazione computazione U(M;x) è O(|encode(M)|) O(f(|x|)) = O(n f(|x|)) = O(n f(n)),Se la computazione di M ha complessità in tempo f(|x|), allora la complessità in tempo della computazione U(M;x) è O(|encode(x)|) + O((|encode(M)| + log n) f(|x|)) = O(n) + O(n f(|x|)) = O(n f(n)),21/11/2005
61-1O(k2 n ( f(n) )2)O(k n log n ( f(n) )2) 
717O(lM k2 f(|x|)2)O(lM k f(|x|)2)21/11/2005
717O(1)O(lM)21/11/2005
719O((log n)3 f(|x|))O((log n)2 f(|x|))21/11/2005
71-16.. + O(n) = f(n)... + O(n) = f(n) + O(n) = O(f(n))-
74-5⌈log n⌉⌈log n⌉2-
844C' ⊆ C ∧ L ∈ C'C' ⊆ C ∧ C' è chiusa ∧ L ∈ C'11/12/2005
8613inferiore a 1al più 1-
9320sono sonosono23/11/2005
9325MASSIMO INSIEME DI INDIPENDENZAMASSIMO INSIEME DI INDIPENDENZA(D)23/11/2005
10116gli interi hanno dimensionegli interi hanno valore28/11/2005
1077SOL(x)SOL*(x)29/11/2005
107-9r-approssimante0.0-approssimante.29/11/2005
109-23A r-approssimante polinomiale in tempo che,A che,30/11/2005
109-20Full PolynomialFully Polynomial29/11/2005
109-171/(r-1)r/(r-1)29/11/2005
110-7sostituire ≥ con ≤ 30/11/2005
110-4r = ( m ln ( (m+1)/2 ) ) / m = ln ( (m+1) / 2 ) = O(ln m)r ( m ln ( (m+1)/2 ) ) / m = ln ( (m+1) / 2 )   ln m30/11/2005
116131/(r-1)r/(r-1)30/11/2005