Skip to content

Latest commit

 

History

History
1856 lines (1843 loc) · 49.4 KB

README.md

File metadata and controls

1856 lines (1843 loc) · 49.4 KB

Automi, Calcolabilità e Complessità

Note

Lo scopo di questo repository GitHub è lo scambio e il confronto di Soluzioni ad Esercizi di Automi, Calcolabilità e Complessità assegnati, a lezione e nei testi d'esame, dai professori dell'insegnamento presso il Corso di Laurea Triennale in Informatica di Sapienza Università di Roma

💬 Nel forum realizzato attraverso questo repository potrai dunque trovare (e possibilmente confermare) soluzioni proposte da altri studenti o anche condividere e ricevere un feedback in merito alle tue!

Warning

Questo forum è gestito e contribuito da studenti e, in quanto tale, non è ufficiale e non sostituisce né intende sostituire le fonti ufficiali!

📖 Esercizi tratti dal libro

Libro: Michael Sipser, Introduzione alla Teoria della Computazione, Maggioli Editore, 2016.

Capitolo 0:
Introduzione

0.1 0.2 0.3 0.4 0.5
0.6 0.7 0.8 0.9 0.10
0.11 0.12 0.13 0.14 0.15

Parte prima:
Automi e linguaggi

Capitolo 1:
Linguaggi regolari

1.1 1.2 1.3 1.4 1.5
1.6 1.7 1.8 1.9 1.10
1.11 1.12 1.13 1.14 1.15
1.16 1.17 1.18 1.19 1.20
1.21 1.22 1.23 1.24 1.25
1.26 1.27 1.28 1.29 1.30
1.31 1.32 1.33 1.34 1.35
1.36 1.37 1.38 1.39 1.40
1.41 1.42 1.43 1.44 1.45
1.46 1.47 1.48 1.49 1.50
1.51 1.52 1.53 1.54 1.55
1.56 1.57 1.58 1.59 1.60
1.61 1.62 1.63 1.64 1.65
1.66 1.67 1.68 1.69 1.70
1.71 1.72 1.73 --- ---

Capitolo 2:
Linguaggi context-free

2.1 2.2 2.3 2.4 2.5
2.6 2.7 2.8 2.9 2.10
2.11 2.12 2.13 2.14 2.15
2.16 2.17 2.18 2.19 2.20
2.21 2.22 2.23 2.24 2.25
2.26 2.27 2.28 2.29 2.30
2.31 2.32 2.33 2.34 2.35
2.36 2.37 2.38 2.39 2.40
2.41 2.42 2.43 2.44 2.45
2.46 2.47 2.48 2.49 2.50
2.51 2.52 2.53 2.54 2.55
2.56 2.57 2.58 2.59 ---
--- --- --- --- ---
--- --- --- --- ---
--- --- --- --- ---

Parte seconda:
Teoria della computabilità

Capitolo 3:
La tesi di Church-Turing

3.1 3.2 3.3 3.4 3.5
3.6 3.7 3.8 3.9 3.10
3.11 3.12 3.13 3.14 3.15
3.16 3.17 3.18 3.19 3.20
3.21 3.22 --- --- ---
--- --- --- --- ---
--- --- --- --- ---

Capitolo 4:
Decidibilità

4.1 4.2 4.3 4.4 4.5
4.6 4.7 4.8 4.9 4.10
4.11 4.12 4.13 4.14 4.15
4.16 4.17 4.18 4.19 4.20
4.21 4.22 4.23 4.24 4.25
4.26 4.27 4.28 4.29 4.30
4.31 4.32 --- --- ---

Capitolo 5:
Riducibilità

5.1 5.2 5.3 5.4 5.5
5.6 5.7 5.8 5.9 5.10
5.11 5.12 5.13 5.14 5.15
5.16 5.17 5.18 5.19 5.20
5.21 5.22 5.23 5.24 5.25
5.26 5.27 5.28 5.29 5.30
5.31 5.32 5.33 5.34 5.35
5.36 --- --- --- ---

Capitolo 6: Argomenti avanzati
nella teoria della computazione

6.1 6.2 6.3 6.4 6.5
6.6 6.7 6.8 6.9 6.10
6.11 6.12 6.13 6.14 6.15
6.16 6.17 6.18 6.19 6.20
6.21 6.22 6.23 6.24 6.25
6.26 6.27 6.28 --- ---
--- --- --- --- ---
--- --- --- --- ---

Parte terza:
Teoria della complessità

Capitolo 7:
Complessità di tempo

7.1 7.2 7.3 7.4 7.5
7.6 7.7 7.8 7.9 7.10
7.11 7.12 7.13 7.14 7.15
7.16 7.17 7.18 7.19 7.20
7.21 7.22 7.23 7.24 7.25
7.26 7.27 7.28 7.29 7.30
7.31 7.32 7.33 7.34 7.35
7.36 7.37 7.38 7.39 7.40
7.41 7.42 7.43 7.44 7.45
7.46 7.47 7.48 7.49 7.50
7.51 7.52 7.53 7.54 ---

Capitolo 8:
Complessità di spazio

8.1 8.2 8.3 8.4 8.5
8.6 8.7 8.8 8.9 8.10
8.11 8.12 8.13 8.14 8.15
8.16 8.17 8.18 8.19 8.20
8.21 8.22 8.23 8.24 8.25
8.26 8.27 8.28 8.29 8.30
8.31 8.32 8.33 8.34 ---
--- --- --- --- ---
--- --- --- --- ---
--- --- --- --- ---
--- --- --- --- ---

Capitolo 9:
Intrattabilità

9.1 9.2 9.3 9.4 9.5
9.6 9.7 9.8 9.9 9.10
9.11 9.12 9.13 9.14 9.15
9.16 9.17 9.18 9.19 9.20
9.21 9.22 9.23 9.24 9.25

Capitolo 10: Argomenti avanzati
nella teoria della complessità

10.1 10.2 10.3 10.4 10.5
10.6 10.7 10.8 10.9 10.10
10.11 10.12 10.13 10.14 10.15
10.16 10.17 10.18 10.19 10.20
10.21 10.22 10.23 --- ---