Temari i Referències

El curs inclou un contingut matemàtic important. Es preveu que els estudiants tinguin experiència prèvia amb el concepte de demostració i un cert grau de maduresa matemàtica. Per a aquells que compleixin aquests requisits i sentin curiositat pels límits teòrics de la computació, el curs promet ser intel·lectualment estimulant i alhora gratificant.

Temari

The following is a more detailed and up-to-date version of the UPC syllabus of the course.

Consell0. Introduction
  1. Basic mathematical notions
    sets and tuples, relations and functions
  2. Formal languages
    strings and languages, concatenation, Kleene star, homomorphisms
  3. Common proof techniques
    proofs by contradiction, cases, induction, Pigeonhole principle

References:
(Sipser 2013, \S 0) (Cases i Màrquez 2003, \S 1)
(Hopcroft et al. 2007, \S 1)

Nota1. Regular languages
  1. Deterministic Finite Automata (DFA) and equivalent models
    Non-deterministic Finite Automata (NFA) and \lambda-NFAs, regular expressions (regex), equivalence between DFA/NFA/\lambda-NFA/regex, Arden’s Lemma.
  2. Minimization of DFAs (Moore’s algorithm)
  3. Closure properties of regular languages
    union, intersection, complement, concatenation and Kleene star, reverso, homomorphism and inverse of homomorphism
  4. Proofs of non-regularity
    \{a^nb^n \mid n\in \mathbb N\} is not regular, pumping lemma for regular languages, distinguishing extensions

References:
(Sipser 2013, \S 1.1-1.4)
(Cases i Màrquez 2003, \S 4-6.4 and \S 7.1)
(Hopcroft et al. 2007, \S 2.1 - 2.5, \S 3.1-3.2 and \S 4.1-4.4)

Precaució2. Context-free languages
  1. Context-free grammars (CFGs)
    Parsing trees and ambiguity. Depuration of CFGs and Chomsky Normal Form
  2. CYK algorithm
  3. Closure properties of context-free languages
    union, concatenation, and Kleene star, reverse, homomorphism, intersection with a regular language, inverse homomorphism
  4. Push-down automata (PDAs)
    equivalence with CFGs, deterministic PDAs, uniquely-accepting PDAs
  5. Proofs of non context-freeness
    Pumping lemma for context-free languages. \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free. Proofs of non context-freeness by closure properties

References:
(Sipser 2013, \S 2.1-2.3)
(Cases i Màrquez 2003, \S 2-3 and \S 7.2-7.3)
(Hopcroft et al. 2007, \S 5.1, \S 5.4, \S 7.1-7.3)

Alerta3. Decidable and semidecidable languages
  1. Turing Machines
    Deterministic (1-tape) Turing Machines (DTM), language recognized and function computed by a DTM, equivalent models (nondeterministic Turing Machines, TMs with multiple tapes). Church-Turing Thesis. Gödel numbering of TMs. Universal Turing Machine
  2. Decidable (\mathbf{R}), semi-decidable(\mathbf{RE}), and co-semi-decidable (\mathbf{coRE}) languages
    projection theorem, \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}, closure properties of \mathbf{R}/\mathbf{RE}/\mathbf{coRE}, a glimpse into the arithmetical hierarchy
  3. Cantor Diagonalization
    almost all languages do not have a finite description
  4. \mathbf{RE}\neq \mathbf{R}
    \mathtt {K, HALT,\dots}\notin \mathbf R, many-one reductions, natural problems not in \mathbf{R}

References:
(Sipser 2013, \S 3-5)
(Serna et al. 2004, \S 1-3)
(Hopcroft et al. 2007, \S 8-9.3)
(Kozen 1997, Lectures 28-32)

Important4. Elements of complexity theory
  1. \mathbf{P}/\mathbf{NP}/\mathbf{coNP}/\mathbf{EXP}
    \mathbf{NP}-completeness, \mathtt{SAT} and Cook-Levin’s Theorem, polynomial-time reductions, a glimpse into the polynomial hierarchy
  2. \mathbf{NP}-intermediate problems
    factoring, discrete log, graph isomorphism, Ladner’s theorem
  3. \mathbf{P}\neq \mathbf{EXP}
    time computable functions and time hierarchy theorem

References:
(Sipser 2013, \S 7 and \S 9.1-9.2)
(Hopcroft et al. 2007, \S 10)

Referències

Llibres

El llibre principal de l’assignatura és (Sipser 2013).

Sipser, Michael (2013).
Introduction to the Theory of Computation. 3rd edition.
Cengage Learning.
Available at UPC library

En català, els llibres (Cases i Màrquez 2003) and (Serna et al. 2004) també cobreixen el material del curs.

Cases, Rafel, and Lluís Màrquez (2003).
Llenguatges, Gramàtiques i Autòmats : Curs Bàsic. 2a ed.
Edicions UPC.
Available at UPC library

Serna, Maria José, Carme Àlvarez, Rafel Cases, and Antoni Lozano (2004).
Els Límits de La Computació : Indecidibilitat i NP-Completesa. 2a ed.
Edicions UPC.
Available at UPC library

Altres llibres que tracten els temes del curs (amb més detall que (Sipser 2013)) són (Hopcroft et al. 2007) i (Kozen 1997).

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman (2007).
Introduction to Automata Theory, Languages, and Computation. 3rd edition.
Pearson Addison Wesley.
Available at UPC library

Kozen, Dexter (1997).
Automata and Computability.
Undergraduate Texts in Computer Science. Springer.
Available at UPC library

Vídeos

En aquest curs es cubreix el material dels vídeos de M. Sipser al MIT. S’arriba aproximadament fins la lliçó 16 (tot i que alguns temes es veuen en més profunditat que les classes de Sipser).

En català/castellà també estan disponibles els vídeos de G. Godoy