Automi, Calcolabilità e Complessità

👋 Introduzione

ℹ️ 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!

🗃 Risorse utili

• Sito del corso (Prof. Venturi) » contiene le informazioni del corso, il programma e il diario delle lezioni

🔗 Collegamenti rapidi

Filtri per Argomento

1. Automi
2. Calcolabilità
3. Complessità

Esami precedenti (prof. Venturi)
2023 9 gennaio 6 febbraio 27 marzo 5 giugno 6 luglio 6 settembre	2024 10 gennaio 8 febbraio 8 aprile 6 giugno 3 luglio 11 settembre

📖 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 --- ---