Errata corrige per la dispensa versione 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 -7 G'' G 22/10/2009
57 6 di lunghezza n e senza nodi ripetuti cancellare, altrimenti l'esercizio è banale! 23/10/2009
61 -3 4-NMdT 5-NMdT 30/10/2009
64 -7 ...rispetto alle operazioni di unione e concatenazione. ...rispetto all'operazione di unione. 03/11/2009
65 -6 A tal fine, sia M0,M1,... un'enumerazione delle MdT. A tal fine, sia M0,M1,... l'ordine lessicografico delle MdT. 06/11/2009
65 -4 Si 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
66 3 k'1=2i k'1=0 06/11/2009
66 12 La 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
66 15 Per come è stata costruita f, Dato che P(|x|, f(|x|)) è vera per costruzione, 06/11/2009
66 -18 descrescente decrescente 06/11/2009
68 -17 cancellare cosidetto   06/11/2009
71 19 delle complessità della complessità 08/11/2009
53 22 O(m(2− 2/(k-1))n). O(poly(n) (2−2/(k+1))n). 09/11/2009
1 7 etichetta del nodo padre dei nodi 'non trattabili' e 'trattabili' è errata! decidibili 11/11/2009
88 18-20 il simbolo di funzione S B 13/11/2009
83 Figura 7.4 il nodo 4 è un nodo con bordo semplice mentre dovrebbe essere doppio disegnare il bordo con una doppia linea per indicare che è il nodo di output 09/12/2009
92 Figura 7.6(a)   disegnare l'arco orientato (¬x2, ¬x1) 11/01/2010

Raccolta di temi d'esame

Una raccolta di temi d'esame dati in passato è disponibile in formato pdf.