Calendari del curs 2026/2027 Q1 (grupo 21)

Teoria (T): Dt 18–20 (A6106)

Ilario Bonacina: Despatx: \Omega-223
Consultes: TBD

Problemes/Lab (P/L): Dj 18–20 (A6102/A5S111)

Arnau Messegue Buisan: Despatx: \Omega-TBD
Consultes: envia un email

En les classes de teoria (T), el professor presenta els fonaments teòrics bàsics de cada tema i resol alguns problemes. Els estudiants aprofundeixen en la teoria durant el seu temps d’estudi personal utilitzant els recursos indicats pel professor (llibres, vídeos i altres materials complementaris).

En les classes de problemes (P) i en les sessions de laboratori (L), els estudiants exposen les solucions als problemes que se’ls han assignat prèviament. El professor intervé durant les explicacions per corregir errors o proposar millores. A més, pren notes sobre les presentacions dels estudiants per tenir-les en compte en l’avaluació final de l’assignatura. En les sessions de laboratori, els estudiants resolen problemes davant de l’ordinador que són avaluats automàticament.

Tots els avisos es faran a través del racó.
Per qüestions administratives, contacteu amb els coordinadors del curs (Ilario Bonacina, Antoni Lozano) .

Date		Tema de la classe
08 Sept	T	Overview of the course, administrative part. Introduction: math background, formal languages, proofs techniques (contradiction, cases, induction, pigeonhole principle). Solution of some exercises from Problem Set 0 (in groups in class).
11 Sept		No class
15 Sept	T	Regular languages (DFAs, \lambda-NFAs, examples, cartesian product and some closure properties). Determinization (subset set construction). Solution of some exercises from Problem Set 1 (in groups in class).
18 Sept	L	Construction of DFAs using RACSO. Students presentations of exercises from RACSO.
22 Sept	T	Minimization of DFAs (Moore’s algorithm). \{a^n b^n \mid n\in \mathbb N\} is not regular and proofs of non-regularity via distinguishing extensions. Solution of some exercises from Problem Set 1 (in groups in class).
25 Sept		No class
29 Sept	T	Regular expressions and equivalence with DFAs (Arden’s Lemma). Examples. Pumping Lemma for regular languages. Non regularity using closure properties. Solution of some exercises from Problem Set 1 (in groups in class).
02 Oct	P	Students presentations of exercises from Problem Set 1.
06 Oct	T	Context-Free Grammars, parse trees, ambiguity. Closure properties of CFGs. Regulars are included in CFL. Solution of some exercises from Problem Set 2 (in groups in class).
09 Oct	L	Construction of CFGs using RACSO. Students presentations of exercises from RACSO.
13 Oct	T	Depuration of CFGs and Chomsky Normal Form. Cocke-Younger-Kasami parsing algorithm. Solution of some exercises from Problem Set 2 (in groups in class).
16 Oct	P	Students presentations of exercises from Problem Set 2.
20 Oct	T	\{a^n b^n c^n \mid n\in \mathbb N\} is not context-free. Pumping Lemma for CFL. Non context-freeness using closure properties. Solution of some exercises from Problem Set 2 (in groups in class).
23 Oct	L	Construction of DFA and CFGs using RACSO. Students presentations of exercises from RACSO.
27 Oct	T	Push-down automata. Equivalence with CFGs. Deterministic CFLs. Turing Machines: one tape, multi tape, nondeterminism, basic properties. Equivalence with high level algorithms and Church-Turing Thesis.
30 Oct		No class
02 Nov		Partial Exam 1 (10:30-13:30)
03 Nov		No class
06 Nov	L	Construction of PDAs using RACSO. Students presentations of exercises from RACSO.
10 Nov	T	Gödel numbering, Universal TM. Definition of \mathbf{R} (decidable languages), \mathbf{RE} (semi-decidable languages), and \mathbf{coRE}. Diagonalization and undecidability of \mathtt{K} (\mathtt{K}\notin \mathbf{R}). Solution of some exercises from Problem Set 3 (in groups in class).
13 Nov	P	Students presentations of exercises from Problem Set 3.
17 Nov	T	\mathbf{RE} \cap \mathbf{coRE} = \mathbf{R}. Projection theorem for \mathbf{RE} (and analogue for \mathbf{coRE}). Arithmetic hierarchy. Many-one reductions. Proving undecidability through reductions. Undecidable properties of CFGs (statements only). Examples. Solution of some exercises from Problem Set 3 (in groups in class).
20 Nov	L	Construction of reductions from \mathtt{K} using RACSO. Students presentations of exercises from RACSO.
24 Nov	T	Recap of \mathbf{P}, \mathbf{NP}, \mathbf{coNP}, \mathbf{EXP}. Time-constructible functions. Universal TM (revised). Solution of some exercises from Problem Set 4 (in groups in class).
27 Nov	P	Students presentations of exercises from Problem Set 3.
01 Dec	T	\mathbf{NP}-completeness (Cook-Levin Theorem) and polynomial-time reductions. Reductions from \mathtt{SAT}. Examples. Solution of some exercises from Problem Set 4 (in groups in class).
04 Dec	L	Construction of PDAs and reductions from K using RACSO. Students presentations of exercises from RACSO.
08 Dec		No class
11 Dec	P	Students presentations of exercises from Problem Set 4.
15 Dec	T	\mathbf{NP}-intermediate problems (factoring, graph isomorphism, discrete log). Ladner’s Theorem. Time-hierarchy theorem. \mathbf{P}\neq \mathbf{EXP}. Solution of some exercises from Problem Set 4 (in groups in class).
18 Dec	P	Students presentations of exercises from Problem Set 4.
23 Dec		Partial Exam 2 (11:00–14:00)
18 Jan		Final Exam (08:00–11:00)