Temari

El següent és una versió més detallada del temari a la web de la UPC.

1. Introducció
   1. Notions matemàtiques bàsiques
      • conjunts i tuples
      • relacions i funcions
   2. Llenguatges formals
      • cadenes i llenguatges
      • concatenació
      • estrella de Kleene
      • homomorfismes
   3. Tècniques de demostració més habituals
      • demostracions per contradicció
      • demostracions per casos
      • demostracions per inducció
      • principi del colomar (pigeonhole principle)
   4. Diagonalització de Cantor
      • gairebé tots els llenguatges no tenen una descripció finita
        
2. Llenguatges regulars
   1. Autòmates Finits Deterministes (DFA)
   2. Models equivalents
      • Autòmates Finits No Deterministes (NFA) i \lambda-NFA
      • expressions regulars (regex)
      • equivalència entre DFA/NFA/\lambda-NFA/regex
      • Lema d’Arden
   3. Minimització de DFA (algorisme de Moore)
   4. Propietats de clausura dels llenguatges regulars respecte de
      • unió, intersecció i complement
      • concatenació i estrella de Kleene
      • revers
      • homomorfisme i invers d’un homomorfisme
   5. Demostracions de no-regularitat
      • \{a^nb^n \mid n\in \mathbb N\} no ès regular
      • lema de bombament per a llenguatges regulars
      • extensions distintives
3. Llenguatges incontextuals
   1. Gramàtiques incontextuals (CFG)
   2. Arbres d’anàlisi (parsing trees) i ambigüitat
   3. Depuració de CFG i Forma Normal de Chomsky
   4. Algorisme CYK
   5. Propietats de clausura dels llenguatges incontextuals respecte de
      • unió, concatenació i estrella de Kleene
      • revers
      • homomorfisme
      • intersecció amb un llenguatge regular
   6. Autòmates amb pila (PDA)
      • equivalència amb CFG
      • PDA deterministes
      • PDA d’acceptació única (uniquely-accepting)
   7. Lema de bombament per a llenguatges incontextuals
      • \{a^nb^nc^n \mid n\in \mathbb N\} no és incontextual
4. Llenguatges decidibles i semidecidibles
   1. Màquines de Turing deterministes (DTM) de 1 cinta
      • llenguatge reconegut i funció computada per una DTM
   2. Models equivalents
      • Màquines de Turing no deterministes
      • Màquines de Turing amb múltiples cintes
   3. Tesi de Church-Turing
   4. Numeració de Gödel de les MT
   5. Màquina de Turing universal
   6. \mathbf{R}/\mathbf{RE}/\mathbf{coRE}
      • teorema de projecció
      • \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}
      • propietats de clausura de \mathbf{R}/\mathbf{RE}/\mathbf{coRE}
      • \mathbf{RE}\neq \mathbf{R}
   7. Reduccions many-one
   8. Teorema de Rice
   9. Problemes naturals que no pertanyen a \mathbf{R}
5. Elements de teoria de la complexitat
   1. \mathbf{P}/\mathbf{NP}/\mathbf{coNP}/\mathbf{EXP}
   2. \mathbf{NP}-completesa
      • \mathtt{SAT} i el Teorema de Cook-Levin
      • reduccions en temps polinòmic
   3. Teorema de jerarquia en temps i \mathbf{P}\neq \mathbf{EXP}