Exercicis per a l’avaluació continuada
Aquesta pàgina conté una llista d’exercicis sobre els temes tractats al curs.
Els exercicis estan agrupats en Tasques (T). Al racó, aproximadament cada dues setmanes, se t’assignarà un exercici d’una tasca (o una part d’un exercici). Consulta el racó per veure quin exercici t’ha estat assignat i prepara’t per presentar la teva solució a la pissarra.
Es recomana discutir les solucions amb altres estudiants i treballar en grup (especialment amb estudiants als quals se’ls hagi assignat parts del mateix exercici). Ara bé, a classe, les presentacions a la pissarra són individuals.
Sobre la notació
En els exercicis següents fem servir notació matemàtica estàndard i alguna de lleugerament no estàndard:
\lambda denota el mot buit. En la majoria de llibres, això es representa amb \epsilon: aquest és el cas, per exemple, de (Sipser 2013), (Hopcroft, Motwani, i Ullman 2007) i (Kozen 1997).1
Donat n\in \mathbb N, fem servir n\mathbb N o \dot n per representar el conjunt dels naturals múltiples de n. Escriure m\in n\mathbb N +k és el mateix que afirmar que m\equiv k \pmod{n}. Per exemple, és cert que 6\in 3\mathbb N i 16\in 5\mathbb N +1, mentre que 13\notin 7\mathbb N.
Per a un mot binari w, \mathtt{value}_2(w) representa el valor binari del mot w. Per convenció, \mathtt{value}_2(\lambda)=0. Observem que \mathtt{value}_2(w0)=2\cdot\mathtt{value}_2(w) i \mathtt{value}_2(w1)=2\cdot\mathtt{value}_2(w)+1. Cal notar també que un nombre arbitrari de zeros inicials en un mot dona lloc al mateix nombre: \mathtt{value}_2(w)=\mathtt{value}_2(0w)=\mathtt{value}_2(00w)=\mathtt{value}_2(000w)=\cdots. En particular, per a cada nombre natural n hi ha infinits mots binaris w tals que \mathtt{value}_2(w)=k.
Tasca 1
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- (Sipser 2013, \S 0)
- (Cases i Màrquez 2003, \S 1)
- (Hopcroft, Motwani, i Ullman 2007, \S 1)
En els exercicis següents podeu suposar totes les propietats bàsiques ben conegudes de la unió, la intersecció i el complementari de conjunts. Per exemple, la distributivitat de la intersecció sobre la unió, la distributivitat de la unió sobre la intersecció i les lleis de De Morgan, és a dir, donats conjunts A,B,C es compleix que:
- A\cap (B\cup C)=(A\cap B)\cup (A\cap C) i A\cup (B\cap C)=(A\cap B)\cup(A\cup C),
- \overline{A\cap B}=\overline A\cup \overline B i \overline{A\cup B}=\overline A\cap \overline B.
Recordeu també que, per mostrar una igualtat entre dos conjunts A i B, n’hi ha prou amb mostrar que A\subseteq B i B\subseteq A, és a dir, que per a tot x\in A es compleix que x\in B i, viceversa, que per a tot y\in B es compleix que y\in A.
| # | Títol | Categories |
|---|---|---|
| 1 | De descripcions informals a formals | theory of languages |
| 2 | Concatenació — propietats bàsiques | theory of languages, concatenation |
| 3 | Estrella de Kleene — propietats bàsiques | Kleene star, theory of languages |
| 4 | Caracteritzacions | Kleene star, theory of languages |
| 5 | Revessat – propietats bàsiques | theory of languages, reverse |
| 6 | Homomorfismes I – propietats bàsiques | homomorphism, theory of languages |
| 7 | Homomorfismes II – propietats bàsiques | homomorphism, theory of languages |
| 8 | Sobre la mida dels llenguatges | theory of languages, cardinality of languages |
| 9 | Desplaçament d’un llenguatge | theory of languages, shift |
| 10 | Simplificació de llenguatges | theory of languages |
| 11 | L=\overline{\Sigma L} | theory of languages, hard exercise |
| 12 | Passejades arbitràriament llargues en grafs | pigeonhole principle |
| 13 | Inducció senzilla | induction proof |
| 14 | Divisibilitat en un conjunt de nombres | induction proof, proof by cases, hard exercise, pigeonhole principle |
Tasca 2
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- Exemples de construcció d’autòmats finits (Lluís Màrquez, Enrique Romero)
- (Cases i Màrquez 2003, \S 4 and \S 5)
- (Sipser 2013, \S 1.1 and \S 1.2)
- (Hopcroft, Motwani, i Ullman 2007, \S 2.1, \S 2.2 and \S 4.2)
| # | Títol | Categories |
|---|---|---|
| 1 | Unió i intersecció de llenguatges regulars – la construcció del producte | regular languages, union, intersection, product construction, minimization of DFAs |
| 2 | El complementari d’un llenguatge regular és regular | regular languages, complement, minimization of DFAs |
| 3 | La concatenació de llenguatges regulars és regular | regular languages, concatenation, minimization of DFAs |
| 4 | L’estrella de Kleene d’un llenguatge regular és regular | regular languages, Kleene star, minimization of DFAs |
| 5 | El revessat d’un llenguatge regular és regular | regular languages, reverse |
| 6 | L’homomorfisme d’un llenguatge regular és regular | regular languages, homomorphism, minimization of DFAs |
| 7 | L’homomorfisme invers d’un llenguatge regular és regular | regular languages, homomorphism, minimization of DFAs |
| 8 | Minimització de DFAs | regular languages, minimization of DFAs |
| 9 | Els NFAs poden ser exponencialment més succints que els DFAs | regular languages, NFAs vs DFAs, pigeonhole principle, minimization of DFAs |
| 10 | DFAs – propietats decidibles | regular languages, decidable properties |
| 11 | Els llenguatges finits són regulars | regular languages, union, finite set |
| 12 | La pertinença a un regular és decidible en temps polinòmic | regular languages, polynomial time, membership problem |
| 13 | Les progressions aritmètiques són regulars | regular languages, arithmetic progressions, hard exercise, base-2, unary |
| 14 | Almenys k ocurrències de cada símbol és un llenguatge regular | regular languages, minimization of DFAs, pigeonhole principle, hard exercise |
| 15 | La primera meitat d’un regular és regular | regular languages, first half, hard exercise |
| 16 | L’IntercalAND de regulars és regular | regular languages, intercalAND |
| 17 | Prefixos i sufixos | regular languages, prefixes, suffixes |
Tasca 3
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- (Sipser 2013, \S 1.4 Nonregular Languages)
- (Cases i Màrquez 2003, \S 7.1)
- (Sipser 2013, \S 1.3 Regular Expressions)
- (Cases i Màrquez 2003, \S 6.1 – \S 6.4)
- (Hopcroft, Motwani, i Ullman 2007, \S 4.1 and \S 3)
| # | Títol | Categories |
|---|---|---|
| 1 | Variacions sobre a^n b^n | pumping lemma, dyck language |
| 2 | Comptar as i bs no és regular (en general) | pumping lemma |
| 3 | Sobre as en la primera part i bs en la segona | pumping lemma, hard exercise |
| 4 | Palíndroms i palíndroms parcials | pumping lemma, hard exercise |
| 5 | Comprovar aritmètica bàsica no és regular | pumping lemma |
| 6 | Seqüències unàries amb forats arbitràriament grans | pumping lemma |
| 7 | Aproximacions de nombres reals | pumping lemma, diagonalization, hard exercise |
| 8 | Quines operacions preserven la no regularitat? | non regularity, union, complement, intersection, reverse, shift, Kleene star, homomorphism, inverse homomorphism |
| 9 | Lema d’Arden i aplicacions | theory of languages, Arden’s Lemma, hard exercise, regular expressions |
| 10 | Expressions regulars i propietats de tancament dels regulars | regular expressions, union, complement, intersection, reverse, homomorphism, inverse homomorphism, Kleene star, concatenation |
| 11 | Propietats decidibles sobre expressions regulars | regular expressions, decidable properties |
| 12 | Transformació d’expressions regulars | regular expressions |
Tasca 4
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- (Sipser 2013, \S 2.1 Content-free Grammars)
- (Cases i Màrquez 2003, \S 2 and \S 3)
- (Hopcroft, Motwani, i Ullman 2007, \S 5)
| # | Títol | Categories |
|---|---|---|
| 1 | Només incontextual o en realitat regular? | context-free languages, pumping lemma |
| 2 | Gramàtiques incontextuals ambigües | ambiguity, context-free languages |
| 3 | Llenguatges de Dyck | context-free languages, ambiguity, dyck language |
| 4 | Operacions de tancament dels incontextuals i ambigüitat | context-free languages, ambiguity, union, concatenation, reverse, Kleene star, homomorphism |
| 5 | Depuració de gramàtiques | context-free languages, depuration of grammars |
| 6 | Sobre la forma normal de Chomsky | Chomsky normal form, context-free languages |
| 7 | La pertinença a un incontextual és decidible en temps polinòmic | membership problem, context-free languages, CKY algorithm, decidable properties |
| 8 | Propietats decidibles dels incontextuals | decidable properties, context-free languages |
| 9 | El complementari d’un incontextual pot ser incontextual | complement, context-free languages, hard exercise |
| 10 | Condicions suficients per la inambigüitat | context-free languages, ambiguity |
| 11 | Sobre les gramàtiques regulars | context-free languages, depuration of grammars, regular languages, linear grammar, regular grammar, ambiguity |
Tasca 5
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- (Sipser 2013, \S 3 and \S 4.1)
- (Hopcroft, Motwani, i Ullman 2007, \S 8)
- (Kozen 1997, Lectures 28-32)
- (Serna et al. 2004, \S 1, 2, 3)
Els exercicis següents fan servir notació habitual en computabilitat. En particular:
- \mathbf{R} és el conjunt de tots els llenguatges decidibles (també dits recursius).
- \mathbf{RE} és el conjunt de tots els llenguatges semidecidibles (també dits enumerables recursivament).
- \mathbf{coRE} és el conjunt de tots els llenguatges L tals que \overline L\in \mathbf{RE}. \mathbf{coRE} no és el complementari de \mathbf{RE}. De fet, la majoria de llenguatges no són ni a \mathbf{RE} ni a \mathbf{coRE}.
Recordeu que \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}.
| # | Títol | Categories |
|---|---|---|
| 1 | Màquines de Turing per llenguatges senzills | Turing machines |
| 2 | Models equivalents de màquines de Turing | Turing machines |
| 3 | \mathbf{R}, \mathbf{RE} i \mathbf{coRE} són tancades per unió, intersecció i revessat | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, union, intersection, reverse |
| 4 | Altres propietats de tancament de \mathbf{R}, \mathbf{RE} i \mathbf{coRE} | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, complement, concatenation, Kleene star, shift |
| 5 | \mathbf{R}, \mathbf{RE} i \mathbf{coRE}, i els homomorfismes | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, homomorphism, inverse homomorphism |
| 6 | Alguns llenguatges a \mathbf{RE} | RE (semi-decidable/ recursively enumerable languages) |
| 7 | \mathbf{R}, \mathbf{RE}, \mathbf{coRE} i la diferència simètrica | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, symmetric difference |
| 8 | Characteritzacions de \mathbf{R} i \mathbf{RE} | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), computable functions |
| 9 | Projecció de \mathbf{RE} | RE (semi-decidable/ recursively enumerable languages) |
| 10 | Funcions computables | computable functions |
Tasca 6
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de G. Godoy
Llibres
- (Sipser 2013, \S 4.2 and \S 5)
- (Serna et al. 2004, \S 4)
- (Hopcroft, Motwani, i Ullman 2007, \S 9)
- (Kozen 1997, Lecture 33)
Els exercicis següents fan servir notació habitual en computabilitat. En particular, donat n\in \mathbb N,
- M_n representa la màquina de Turing amb nombre de Gödel n.
- \varphi_n representa la funció computada per la màquina de Turing amb nombre de Gödel n.
Donada una màquina de Turing M,
- M(x)\!\uparrow vol dir que M amb entrada x no s’atura.
- M(x)\!\downarrow vol dir que M amb entrada x s’atura.
- M(x)=y vol dir que M amb entrada x s’atura i dona y com a sortida.
Amb K representem el conjunt de tots els nombres naturals n tals que M_n s’atura amb entrada n:
K=\{n\mid M_n(n)\!\downarrow\}
A classe hem vist que K\in \mathbf{RE}\setminus \mathbf{R}.
Recordeu que, donats dos llenguatges A, B sobre el mateix alfabet \Sigma, diem que A es redueix a B (s’escriu A\leq_m B) si existeix una funció computable total f:\Sigma^*\to\Sigma^* tal que per a tot w\in \Sigma^*, w\in A si i només si f(w)\in B.
Una propietat útil de les reduccions és la següent: donat A\leq_m B,
- si B\in \mathbf{R}, llavors A\in \mathbf{R},
- si B\in \mathbf{RE}, llavors A\in \mathbf{RE}, i
- si B\in \mathbf{coRE}, llavors A\in \mathbf{coRE}.
La m en la notació \leq_m indica que la funció f no és necessàriament injectiva (és many-one).
| # | Títol | Categories |
|---|---|---|
| 1 | Classificació I: propietats bàsiques de les màquines de Turing | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 2 | Classificació II: llenguatges computables | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 3 | Classificació III: domini de les funcions computables | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 4 | Classificació IV: imatge de les funcions computables | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 5 | Classificació V: propietats de les funcions computables | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 6 | Classificació VI: variacions de K | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 7 | Sobre la imatge dels conjunts decidibles | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 8 | Són computables? | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 9 | Són funcions (computables)? | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
Tasca 7
Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:
Vídeos de Sipser
Llibres
- (Sipser 2013, \S 7)
- (Hopcroft, Motwani, i Ullman 2007, \S 10 and \S 11.1)
| # | Títol | Categories |
|---|---|---|
| 1 | Problema del viatjant de comerç | polynomial time, exponential time |
| 2 | A la recerca de cliques | polynomial time, exponential time, NP-completeness |
| 3 | Propietats de tancament de \mathsf{P}, \mathsf{NP} i \mathsf{coNP} | P, NP, coNP |
| 4 | Reduccions de temps polinòmic | polynomial-time reductions |
| 5 | Tancament per l’estrella de Kleene | P, NP, Kleene star |
| 6 | Cerca vs decisió | P, NP, polynomial time |
| 7 | Teorema de Berman | P, NP, NP-completeness, unary language |
| 8 | \mathsf{NP} i \mathtt{HALT} | NP, NP-completeness |
| 9 | \mathtt{Unique SAT} | NP, coNP, DP, Unique SAT |
| 10 | Pertanyen a \mathsf{P}? | NP, P, 3SAT |
Referències
Notes a peu de pàgina
L’ús de la lletra grega \epsilon (èpsilon) sembla estar relacionat amb la paraula anglesa empty (buit). La viquipèdia en alemany afirma que l’ús de la lletra grega \lambda (lambda) està relacionat amb l’alemanya leer, que vol dir buit. És possible que l’ús de \lambda per denotar el mot buit s’originés en l’escola finesa i en el treball influent del matemàtic Arto Salomaa. Algunes persones en combinatòria fan servir 1 per al mot buit amb algunes justificacions algebraiques.↩︎