---

2024 Q3

CCM-104 - Teoria da Computação (Pós)

Professora: Carla Negri Lintzmayer

🚨 Avisos importantes (fique atento sempre!)

📌 [19/dez] Terminei de corrigir a prova 2 e contabilizei as notas finais. Estão disponíveis na seção de notas. Em caso de dúvidas, me mande um e-mail e podemos marcar para conversar na última semana de janeiro.

[12/dez] Responda ao questionário sobre o horário da prova 1.
[12/dez] Atualizei a lista 5: havia dois erros. Arrumei os errinhos nos slides das aulas 21 e 22.
[05/dez] Adicionei um exercício à lista 5, ao final, e liberei a lista 6. Nenhum exercício novo será adicionado a ambas.
Também liberei todos os materiais de apoio das aulas até o final do curso.
[21/nov] Vejam detalhes sobre a aula do dia 28/novembro no cronograma!
[18/nov] Fechei a lista 3 (o conteúdo dela foi cobrado na prova 1) e liberei uma lista 4.
[27/out] A lista 2 inteira foi liberada.
[15/out] A lista 1 inteira foi liberada.
[08/out] Deixei exercícios extras e suas resoluções no material extra da Aula 3.
[03/out] Exercícios para entrega no dia 17/out: veja na seção de listas.
[26/set] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em uma avaliação.

📝 Dias, horários e locais das aulas

🙋 Dias, horários e locais dos atendimentos extraclasse

🧐 Ementa da disciplina

CCM-104

Linguagens Regulares: autômatos finitos determinísticos e não-determinísticos, expressões regulares. Linguagens livres de contexto: gramáticas livres de contexto e autômatos com pilha. Máquinas de Turing: decidibilidade e reconhecibilidade. O problema da parada. Redução. Classes de complexidade: P, NP e NP-completo.

🖖 Recomendação

Para facilitar o acompanhamento do curso, é recomendado que você possua:

• conhecimentos de programação (em qualquer linguagem imperativa)
• familiaridade com estruturas de dados básicas (vetores, pilhas),
• familiaridade com linguagem matemática (conjuntos, sequências, relações, funções),
• capacidade para reconhecer argumentos lógicos em uma demonstração matemática.

Ter cursado a disciplina "Análise de algoritmos e estruturas de dados" do nosso programa ou outra equivalente também ajuda muito.
Veja aqui os sites das últimas vezes que eu ministrei essa disciplina.

Preparei esse material de 🔥revisão🔥 que contém praticamente tudo que precisamos para acompanhar a disciplina. Também tenho vídeos com definição e exemplos de indução.

Outros materiais de apoio:

• Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
• Fundamentos da matemática para computação, (videoaulas) do prof. Cláudio Possani, da USP.
• Notas de aulas - Análise de algoritmos e estruturas de dados.

📚 Bibliografia e outros materiais

1. [S] Sipser, M.. Introdução à teoria da computação. 2a edição. Thomson Learning. 2007. (ERRATA da versão em inglês. Tanto em inglês quanto em português, existem vários errinhos.)
2. [HUM] Hopcroft, J. E.; Ullman, D. J.; Motwani, R.. Introdução à teoria de autômatos, linguagens e computação. 2a edição. Editora Campus. 2003.
3. [V] Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.

⏰ Datas importantes

Resumo das datas importantes:

• Única entrega de exercícios (0.5 pontos na média + vale moral): 17/outubro
• Prova 1: 12/novembro
• Prova 2: 19/dezembro
• Prova substitutiva para quem tiver justificativa: a combinar por e-mail

📆 Cronograma

ATENÇÃO! O conteúdo exato e materiais de apoio de cada aula são atualizados durante o quadrimestre e as aulas que já foram ministradas estão coloridas.
Ou seja, as aulas que ainda não estão coloridas podem ter o conteúdo alterado!

Aula 1 - 01/out Conteúdo: Sobre o curso. Material complementar: slides de introdução ao curso e revisão; vídeos sobre indução: Referências: Capítulo 0 [S].

Aula 2 - 03/out Conteúdo: Alfabetos e linguagens. Autômatos finitos determinísticos (AFDs). Referências: Seção 1.1 [S]. Complementar: Seção 2.2 [HUM]. Notas da aula.

Aula 3 - 08/out Conteúdo: Autômatos finitos não determinísticos (AFNs). Linguagens Regulares (LRs). Referências: Seção 1.2 [S]. Notas da aula e slides de apoio. Exercícios AFD e Respostas.

Aula 4 - 10/out Conteúdo: Projeto de AFDs e AFNs (lista de exercícios para entrega no dia 17/outubro). Não haverá aula neste dia! Auxiliarei nos exercícios no dia 15/out, das 16h às 18h.

Aula 5 - 15/out Linguagem de um AFD e demonstração. AFDs vs AFNs. Propriedades das LRs. Atenção! Atendimento hoje das 16h às 18h. Referências: Seção 1.2 [S]. Linguagem e demonstração, AFDs vs AFNs (texto auxiliar), AFDs vs AFNs, e Propriedades.

Aula 6 - 17/out Conteúdo: Expressões regulares (ERs). ERs vs. AFDs/AFNs. Referências: Seção 1.3 [S]. Notas da aula.

Aula 7 - 22/out Conteúdo: Lema do bombeamento para LRs. Referências: Seção 1.4 [S]. Slides da aula.

Aula 8 - 24/out Conteúdo: Gramáticas livres de contexto (GLCs). Linguagens livres de contexto (LLCs). Referências: Seção 2.1 [S]. Notas da aula.

Aula 9 - 29/out Conteúdo: Gramáticas livres de contexto (GLCs). Autômatos com pilha (APs). Referências: Seção 2.1 e 2.2 [S]. Notas da aula: GLCs, APs.

Aula 10 - 31/out Conteúdo: Propriedades das LLCs. Lema do bombeamento para LLCs. Máquinas de Turing (MTs). Referências: Seção 2.3 e 3.1 [S]. Notas da aula: Propriedades e lema, MTs.

Aula 11 - 05/nov Conteúdo: Máquinas de Turing (MTs). Variações de MTs. Referências: Seção 3.1 e 3.2 [S]. Notas da aula: MTs.

Aula 12 - 07/nov Checkpoint: aula extra / revisão e dúvidas para prova. ATENÇÃO! NÃO haverá atendimento após a aula.

Aula 13 - 12/nov Prova 1 Conteúdo: aulas 1 a 11.

Aula 14 - 14/nov Conteúdo: Descrições em nível intermediário/alto nível. Cadeias. Tese Church-Turing. Referências: Seção 3.3 [S]. Notas da aula: Descrições e a tese.

Aula 15 - 19/nov Conteúdo: Decidibilidade. Referências: Seção 4.1 [S]. Notas da aula: Decidibilidade.

Aula 16 - 21/nov Conteúdo: O problema da Parada. Método da diagonalização. Indecidibilidade e Irreconhecibilidade. Referências: Seção 4.2 [S]. Notas da aula: O problema da Parada, diagonalização e indecidibilidade.

Aula 17 - 26/nov Conteúdo: Redução. Referências: Seção 5.1 e 5.3 [S]. Notas da aula: Redução.

Aula 18 - 28/nov Não haverá aula para que vocês possam participar do Workshop da nossa pós: confiram a programação e link para inscrições. Das 16h às 17h30 e das 19h às 20h estarei na minha sala, realizando atendimento.

Aula 19 - 03/dez Conteúdo: Mais exemplos de redução. Tempo de execução em máquinas de Turing. Referências: Seção 5.3 e 7.1 [S]. Notas da aula: Mais redução e tempo de execução.

Aula 20 - 05/dez Conteúdo: Tempo de execução em máquinas de Turing. Teoria da complexidade. Referências: Seção 7.1, 7.2 e 7.3 [S]. Notas da aula: tempo de execução e teoria da complexidade.

Aula 21 - 10/dez Conteúdo: Teoria da complexidade. Referências: Seção 7.4 e 7.5 [S]. Notas da aula: Errata e slides de teoria da complexidade (NP-completude).

Aula 22 - 12/dez Conteúdo: Teoria da complexidade. Referências: Seção 7.5, 8.1 e 8.2 [S]. Notas da aula: teoria da complexidade (NP-completude) e teoria da complexidade (espaço). Extra: Teorema Cook-Levin.

Aula 23 - 17/dez Checkpoint: aula extra / revisão e dúvidas para prova.

Aula 24 - 19/dez Prova 2 Conteúdo: tudo o que foi visto entre as aulas 14 e 23. ATENÇÃO! NÃO haverá atendimento após a prova.

👎 Plágio

• Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
  
  
• Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC.
• Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima.
• Abaixo uma versão resumida, que não substitui de modo algum sua leitura:
• Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
• Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
• Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
• Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
• Qualquer violação às regras descritas acima implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F.
• Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.
• Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

🏋 Listas de exercícios

• Sobre gabaritos das listas de exercícios:
  eu acredito que o objetivo de um exercício teórico não é a resolução do problema em si, mas sim praticar a resolução de problemas;
  você precisa chegar nas soluções por conta própria (com algumas dicas da minha parte) ao invés de apenas ler um gabarito (que mostrará uma única solução possível);
  por isso, eu não disponibilizo gabaritos das minhas listas;
  a melhor forma para você saber se resolveu o exercício corretamente é me procurar em horários de atendimento e me mostrar a sua solução.



• Disponibilizarei as listas de exercícios ao longo do quadrimestre, sempre com a devida antecedência: se um conteúdo estiver sendo ministrado, todos os exercícios de apoio já estarão disponíveis.


• Por isso, sempre baixe o arquivo da última lista que foi disponibilizada: nenhum exercício será removido, mas novos exercícios poderão ser adicionados.


• O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
• Procure atendimento sempre que tiver dúvidas nos exercícios.
• Faça o maior número de exercícios que puder, sempre.
  • Vale moral!!
    Qualquer exercício extra que for feito pode ser entregue nos dias das provas para serem considerados como evidência do seu esforço.
    Participar das aulas e dos atendimentos também vale moral.
    Alunos com moral terão direito a pedir arredondamento de conceitos e notas ou abono de alguma falta ao final do curso.
    Em nenhuma hipótese será feito o arredondamento de conceitos ou abono de faltas para alunos sem moral.

• Lista 1 (linguagens regulares)
  • Para o dia 17/outubro: 4 itens do exercício 2 (você escolhe), exercício 3, 4 itens do exercício 7 (você escolhe).
• Lista 2 (linguagens livres de contexto)
• Lista 3 (máquinas de Turing)
• Lista 4 (máquinas de Turing -- parte 2 -- decidibilidade)
• Lista 5 (redução para decidibilidade e reconhecibilidade)
• Lista 6 (teoria da complexidade)

🎓 Critérios de avaliação

• A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, respectivamente.
  • A prova 1 vale 50% da nota e 0 ≤ P₁ ≤ 10.
  • A prova 2 vale 50% da nota e 0 ≤ P₂ ≤ 10.


• Sua média final (MF), portanto, será
  
  MF = 0.5 x P1 + 0.5 x P2


• Seu conceito final será
  
  A, se MF ≥ 8.5
  B, se 7.0 ≤ MF < 8.5
  C, se 6.0 ≤ MF < 7.0
  F, se MF < 6.0
  


• Não esqueça do vale moral!

💯 Notas

Acesse a planilha aqui.

🤒 Mecanismos de avaliação substitutivos

• Uma prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas.
• A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.
• A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.
• A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.

---