MCTA015-13 - Linguagens Formais e Automata (2020 Q1, ECE)
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
Grupo no Discord (para alunos!)
🚨 Avisos importantes (fique atento sempre!)
🆕 [29/06] As notas finais (pós REC) estão disponíveis.[22/06] Atenção! Avisos semifinais:
- As notas finais (antes da REC) estão disponíveis. Se você fez a P2, confira seu e-mail para mais informações.
- Farei um atendimento no Discord no dia 23/06, das 19h às 21h.
- Se possível, preencha o formulário anônimo de avaliação final da disciplina (sim, mais um, mas garanto que o último 🤓).
- Para fazer a REC (dia 25/05), você precisa me enviar um e-mail.
[14/06] Haverá atendimento no dias 16/06, das 19h às 21h no Discord.
[09/06] Sobre a prova 1.
[09/06] Notas da lista 2. Um e-mail com explicações foi enviado a cada um. A mesma mensagem foi enviada no Discord.
[08/06] As datas das avaliações foram atualizadas (veja cronograma). Aos que decidiram realizá-las pessoalmente, entrem em contato quando tais atividades forem possíveis.
[07/06] Fiz um vídeo extra sobre o conteúdo da prova 1.
[07/06] Notas da lista 1, parte 5. Um e-mail com explicações foi enviado a cada um. A mesma mensagem foi enviada no Discord.
[30/05] Considerando a situação crítica do país em relação à pandemia, o indicativo de que o distanciamento físico deve perdurar por mais alguns meses, e que o prazo para finalização remota dos ECE foi estendido até o dia 27 de junho, as avaliações finais desta disciplina poderão ser feitas à distância.
O conteúdo das aulas terminará no dia 3/06 e a entrega da última lista está para o dia 7/06 e não será adiada. O período de extensão que nos foi dado será utilizado apenas para a realização das avaliações.
Acesse este formulário até o dia 7 de junho para verificar o novo plano e indicar se você irá aderir ao mesmo. Considero que os que não responderem ao formulário não têm interesse em realizar as avaliações à distância.
[27/05] Lista 4 liberada.
[25/05] O prazo da lista 3 foi para o dia 28/05.
[21/05] O exercício 6 da lista 3 foi removido.
[20/05] O enunciado de um exercício da lista 3 foi alterado. Seu prazo também.
[17/05] O prazo da lista 2 foi para o dia 18/05.
[15/05] Lista 3 liberada.
[08/05] Lista 2 atualizada.
[07/05] Lista 2 liberada.
[06/05] Disponibilizei um vídeo novo sobre erros ao usar o lema do bombeamento para linguagens regulares.
[30/04] Alguns prazos de listas foram modificados.
[27/04] Lista 1, parte 5 liberada.
[18/04] Atenção! A partir do dia 20/04, retornaremos as atividades em esquema de Estudo Continuado Emergencial (ECE).
Veja este vídeo para mais informações sobre como serão nossas atividades.
É muito importante que você faça parte do grupo no Discord.
Conteúdo dessa página
 |
🕐 Dias, horários e local das aulas (voltar ao topo)
Videoaulas e quizzes serão disponibilizados semanalmente, até às segundas-feiras, na seção Cronograma.
Os vídeos referentes ao conteúdo de uma aula prevista não ultrapassarão o total de 2h.
Os quizzes serão referentes ao conteúdo dos vídeos.
As respostas a eles serão utilizadas para avaliar a participação e engajamento dos alunos.
Eles terão prazo de uma semana para serem finalizados.
Todas as terças-feiras, das 19h às 21h, e sextas-feiras, das 21h às 23h, haverá atendimento online no Discord, preferencialmente sobre o conteúdo previsto no cronograma.
🆘 Dias, horários e local de atendimento (voltar ao topo)
Todas as terças-feiras, das 19h às 21h, e sextas-feiras, das 21h às 23h, a professora estará online no Discord.
Atenção! O grupo no Discord pode e deve ser utilizado em qualquer horário.
🤓 Ementa da disciplina (voltar ao topo)
Conceitos básicos. Linguagens regulares: autômatos determinísticos e não-determinísticos, expressões regulares. Linguagens livres de contexto: gramática, autômatos a pilha. Linguagens recursivamente enumeráveis: máquinas de Turing determinísticas e não-determinísticas. Indecidibilidade: o problema da parada. Complexidade: definição das classes P e NP.
Objetivos: (i) Apresentar os conceitos fundamentais da teoria da computação. (ii) Familiarizar o aluno com modelos teóricos de um computador e o tratamento formal de tais modelos. (iii) Apresentar ao aluno as diferentes classes de linguagens. (iv) Preparar o aluno para o posterior estudo de técnicas de construção de Compiladores e processamento de Linguagem Natural. (v) Refinar a habilidade do aluno para tratar com conceitos formais abstratos.
(Disponível na pg. 63 do projeto pedagógico.)
🤯 Recomendação (voltar ao topo)
Disciplinas: Programação Estruturada; Matemática Discreta; Algoritmos e Estruturas de Dados I.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.
- Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
- O que é uma prova matemática, do prof. Paulo Feofiloff, da USP.
- Matemática discreta para computação, dos profs. Anamaria Gomide e Jorge Stolfi, da Unicamp.
- Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
- Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
- Notas de aula, da disciplina de Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).
- Notas de aula, da disciplina de Programação Estruturada (introdução à programação em C, recursão, vetores e listas).
📖 Bibliografia e outros materiais (voltar ao topo)
- [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.)
- [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.
- [V] Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.
- Grupo de Whatsapp criado e mantido pelos alunos.
📆 Cronograma (voltar ao topo)
As referências utilizadas nas aulas serão atualizadas durante o curso.
Sobre qualquer material feito por mim, participe do banco de informantes.
O conteúdo a seguir já foi coberto durante as aulas presenciais:
| Aula | Data | Tópicos |
|---|---|---|
| 1 | 11/02 | Objetivo do curso. Revisão de conceitos importantes para o curso.
✏️ Referências: veja materiais na seção de recomendação. ✏️ Slides usados em sala: introdução ao curso e revisão. |
| 2 | 14/02 | Alfabetos e linguagens. Autômatos finitos determinísticos.
✏️ Referências: Seção 1.1 [S]. ✏️ Extras: Slides do prof. Maycon. Programa para brincar com autômatos. Introdução, AFD (Vídeo-aulas prof. Lucrédio UFSCar). |
| 3 | 18/02 🌧️ | Construção de autômatos finitos determinísticos. Linguagens regulares.
✏️ Referências: Seção 1.1 [S]. ✏️ Extras: Slides do prof. Maycon. AFD (Vídeo-aulas prof. Lucrédio UFSCar). |
| 4 | 21/02 | Construção de autômatos finitos determinísticos. Linguagens regulares.
✏️ Referências: Seção 1.1 [S]. ✏️ Extras: Slides do prof. Maycon. AFD (Vídeo-aulas prof. Lucrédio UFSCar). |
| 🛀 | 25/02 | ---- Feriado (Carnaval) ---- |
| 5 | 28/02 | Autômatos finitos não determinísticos.
✏️ Referências: Seção 1.2 [S]. ✏️ Extras: Slides com detalhes de como um AFN processa cadeias. Slides do prof. Maycon. AFN (Vídeo-aulas prof. Lucrédio UFSCar). |
| 6 | 03/03 | Autômatos finitos determinísticos vs. não determinísticos. Propriedades de linguagens regulares.
✏️ Referências: Seção 1.1, 1.2 [S]. ✏️ Extras: Slides sobre AFN e propriedades dados em sala. Transições epsilon, AFN vs. AFD (Vídeo-aulas prof. Lucrédio UFSCar). |
| 7 | 06/03 | Autômatos finitos determinísticos e não determinísticos.
✏️ Referências: Seção 1.1, 1.2 [S]. ✏️ Extras: Slides dados em sala. |
| 8 | 10/03 | Expressões regulares.
✏️ Referências: Seção 1.3 [S]. ✏️ Extras: Slides com o conteúdo dado em sala. Expressões regulares, Expressões vs. autômatos, Expressões regulares na prática (Vídeo-aulas prof. Lucrédio UFSCar). |
| 9 | 13/03 | Expressões regulares e equivalência com linguagens regulares.
✏️ Referências: Seção 1.3 [S]. ✏️ Extras: Slides com o conteúdo dado em sala. |
| 16/03 | Aulas canceladas devido ao surto do COVID-19. |
Como vai funcionar o ECE:
Revisão do conteúdo já visto:
O conteúdo a seguir será coberto durante o ECE:
| Aula | Data | Tópicos |
|---|---|---|
| 21/04 | ---- Feriado (Tiradentes) ---- | |
| 10 | 24/04 | Revisão e solução de exercícios.
⏰ Tempo total: 1h 12min 📝 Não se esqueça de responder o quiz! (Prazo: 01/05) |
| 11 | 28/04 | Lema do bombeamento para linguagens regulares. 
⏰ Tempo total: 54min 📝 Não se esqueça de responder o quiz! (Prazo: 05/05) ✏️ Referências: Seção 1.4 [S]. |
| 01/05 | ---- Feriado (Dia do trabalho) ---- | |
| 12 | 05/05 | Gramáticas livres de contexto e linguagens livres de contexto. 
⏰ Tempo total: 60min 📝 Não se esqueça de responder o quiz! (Prazo: 12/05) ✏️ Referências: Seção 2.1 [S]. |
| 13 | 08/05 | Autômatos com pilha. Propriedades de LLCs. 
⏰ Tempo total: 44min 📝 Não se esqueça de responder o quiz! (Prazo: 15/05) ✏️ Referências: Seção 2.2 [S]. |
| 14 | 12/05 | Lema do bombeamento para linguagens livres de contexto. 
⏰ Tempo total: 76min 📝 Não se esqueça de responder o quiz! (Prazo: 19/05) ✏️ Referências: Seção 2.3 [S]. |
| 15 | 15/05 | Máquinas de Turing. 
⏰ Tempo total: 71min 📝 Não se esqueça de responder o quiz! (Prazo: 22/05) ✏️ Referências: Seção 3.1 [S]. |
| 16 | 19/05 | Variações de máquinas de Turing. Máquinas de Turing e algoritmos. Tese Church-Turing. 
⏰ Tempo total: 68min 📝 Não se esqueça de responder o quiz! (Prazo: 26/05) ✏️ Referências: Seção 3.2, 3.3 [S], Seção 8.6 [HUM]. ✏️ Extras: MT não determinísticas, MT e computadores (Vídeo-aulas prof. Lucrédio UFSCar). |
| 17 | 22/05 | Decidibilidade. O Problema da Parada. 
⏰ Tempo total: 41min 📝 Não se esqueça de responder o quiz! (Prazo: 29/05) ✏️ Referências: Capítulo 4 [S]. ✏ Extras: A história da indecidibilidade (inglês). |
| 18 | 26/05 | Problemas Turing-Reconhecíveis e Turing-Irreconhecíveis. Introdução à redução. 
⏰ Tempo total: 90min 📝 Não se esqueça de responder o quiz! (Prazo: 02/06) ✏️ Referências: Seção 4.2 [S]. |
| 19 | 29/05 | Redutibilidade. 
⏰ Tempo total: 63min 📝 Não se esqueça de responder o quiz! (Prazo: 05/06) ✏️ Referências: Capítulo 5 [S]. |
| 20/21 | 02/06 | Teoria da complexidade. 
⏰ Tempo total: 110min 📝 Não se esqueça de responder o quiz! (Prazo: 09/06) ✏️ Referências: Capítulo 7 [S]. ✏️ Extras:  ,
P vs. NP and the Computational Complexity Zoo,
Map of Computer Science (não exatamente relacionado com a aula).
|
| 22 | 11/06 | Prova 1 (será enviada por e-mail, às 18h). Conteúdo: Aulas 1 a 14. |
| 23 | 18/06 | Prova 2 (será enviada por e-mail, às 18h). Conteúdo: Aulas 15 a 21. |
| 24 | 25/06 | Prova de recuperação (será enviada por e-mail, às 18h) |
👎 Plágio (voltar ao topo)
- Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
- fraudem avaliações,
- fabriquem ou falsifiquem dados,
- plagiem ou não creditem devidamente autoria,
- aceitem autoria de material acadêmico sem participação na produção,
- 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.
- Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!
- 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.
🏋 Listas de exercícios (voltar ao topo)
- Ao todo teremos 4 listas, cujos enunciados serão disponibilizados aqui, nas datas indicadas abaixo.
- As soluções das listas deverão ser feitas à mão (capriche na letra!), escaneadas em um único arquivo PDF e entregues pelo Google Forms nos links disponibilizados abaixo, nas respectivas datas.
- Sugestão de aplicativo para escanear a lista: CamScanner (disponível para Android e iPhone.)
- Por favor, certifique-se de que o resultado final está legível.
- As partes 1, 2, 3 e 4 da lista 1, já disponibilizadas, não valem nota, mas serão consideradas como bônus.
- A parte 5 da lista 1 e as listas 2, 3 e 4 valerão 30% da nota da disciplina.
- Atenção! As listas serão corrigidas e qualquer caso de detecção de plágio implicará em nota final 0 para os envolvidos.
🎓 Critérios de avaliação (voltar ao topo)
- A avaliação da disciplina constituirá da nota de duas provas, respectivamente denotadas por P1 e P2, da média simples das notas das listas 2.5, 3 e 4 de exercícios, denotada por L, e da média simples das notas dos quizzes, denotada por Q.
- A prova 1 vale 35% da nota.
- A prova 2 vale 30% da nota.
- As listas valem 30% da nota.
- Os quizzes valem 5% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.35 x P1 + 0.3 x P2 + 0.3 x L + 0.05 x Q - Seu conceito final será
A, se MF ≥ 8.5
B, se 7.0 ≤ MF < 8.5
C, se 6.0 ≤ MF < 7.0
D, se 5.0 ≤ MF < 6.0
F, se MF < 5.0
- As provas serão realizadas presencialmente, nas duas primeiras semanas de retorno das atividades presenciais na UFABC.
- Em caso excepcional, poderão ser aplicadas de forma online, e os alunos serão avisados com, no mínimo, 7 dias de antecedência.
Acompanhe a entrega das atividades aqui. Essa planilha é atualizada automaticamente.
💪 Mecanismo de recuperação (voltar ao topo)
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que responderem a ao menos 75% dos quizzes.
- Consistirá numa prova, em formato similar ao das avaliações regulares.
- Será realizada presencialmente, na terceira semana de retorno das atividades presenciais da UFABC. Em caso excepcional, poderão ser aplicadas de forma online, e os alunos serão avisados com, no mínimo, 7 dias de antecedência.
- O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
- A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média a seguir:
NFR = max {MF, (MF + 2 x NR) / 3}
- O conceito final obtido na recuperação substituirá o conceito original e será
C, se NFR ≥ 6.0
D, se 5.0 ≤ NFR < 6.0
F, se 0.0 ≤ NFR < 5.0
🤒 Mecanismos de avaliação substitutivos (voltar ao topo)
A 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.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br