Primeiro quadrimestre de 2017
Turmas: A-diurno e A-noturno
Período letivo: de 07/02 a 29/04 de 2017 (mais a reposição do feriado de 28/02)
Horários e salas: ATENÇÃO PARA MUDANÇA DE SALA!!!
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br
10/05 -- Notas após o exame disponíveis
03/05 -- Pontos de lista disponíveis. Se o seu não estiver e você fez mais que duas listas, mande um email
COM SEU RA!
03/05 -- Notas da P3 disponíveis
27/04 -- Datas da SUB e Exame marcadas
25/04 -- Listas V e VI corrigidas (havia problemas em dois enunciados)
22/04 -- Adicionada referência para Complexidade
22/04 -- Lista VI disponível
10/04 -- Lista V disponível
06/04 -- Data de revisão da P2 anunciada!
05/04 -- Notas da P2 (TODAS) disponíveis
04/04 -- Notas da P2 (somente matutino) disponíveis
02/04 -- Referência sobre diagonalização na bibliografia!
18/03 -- LISTAs 03 e 04 PARA DIA 21 até final do dia
16/03 -- Lista IV corrigida
14/03 -- AVISO: vista / revisão de prova no dia 16/03, no horário da aula!
14/03 -- Lista IV disponível. Prazo 20/03
09/03 -- Lista III disponível. Prazo 20/03
08/03 -- Notas da P1 disponíveis
20/02 -- Lista II disponível. Esta lista deve ajudar na preparação para a prova.
15/02 -- Datas das provas listadas no site
12/02 -- Lista I, exercício 2: autômato estava errado; agora está correto (baixe novamente)
11/02 -- Lista I, exercício 1.c: enunciado agora está mais claro (baixe novamente)
09/02 -- Lista I disponível
08/02 -- mudança de sala de aula!
07/02 -- início do cursoConceitos 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
A disciplina tem grande importância e seus objetivos existem em várias dimensões.
Em uma dimensão prática, linguagens formais são usadas na descrição de linguagens de programação, e portanto o conhecimento delas é essencial ao trabalho em Compiladores, Interpretadores e outros programas similares; usam-se autômatos em descrições formais dos mais variados tipos -- de dispositivos eletrônicos a protocolos abstratos; autômatos são objetos fundamentais em verificação de modelos, e descrevem convenientemente cadeias de Markov, usadas para modelar uma vasta quantidade de processos probabilísticos.
A disciplina também aborda os fundamentos teóricos da Computação, uma vez que identifica o modelo abstrato que descreve tudo o que pode ser efetivamente realizado por computadores; permite compreender estruturas descrevendo-as como linguagens, sendo por isso de grande valor.
Há também outro aspecto da disciplina que não pode ser ignorado: o treinamento em abstração e raciocínio rigoroso, trabalhado também nas disciplinas de Matemática Discreta e Teoria dos Grafos.
A habilidade de implementar algoritmos já definidos tem característica operacional, trabalha o concreto. Já a habilidade de modelar e demonstrar fatos relaciona-se com o abstrato, e permite reusar soluções de problemas e encontrar outras, mais simples do que as já conhecidas.
Além disso, para qualquer assunto pode haver aplicações inusitadas. Vejam, por exemplo, o programa Context Free Art, que constrói imagens a partir de gramáticas livres de contexto.
Os objetivos específicos são dados a seguir.
Oficialmente a Universidade recomenda Programação Estruturada, mas deve-se dar atenção também à posição da disciplina na grade curricular do Bacharelado em Computação -- NÃO se trata de disciplina introdutória!
O conceito final da disciplina poderá ser:
Faremos três avaliações escritas com duas horas de duração: P1, P2 e P3. Cada avaliação vale exatamente 0, 1, 2 ou 3. A nota final é a soma das notas das provas, com mais um ponto para quem fizer as listas de exercícios (direi mais sobre isto depois).
AS AVALIAÇÕES SERÃO REALIZADAS SEM CONSULTA A QUALQUER MATERIAL!
COLA/PLÁGIO RESULTAM EM F NA DISCIPLINA
As notas serão convertidas em conceito de acordo com a seguinte regra: seja n a soma das notas das provas e do ponto de exercícios. Então o conceito final será:
Calcule (P1 + P2 + P3 + E)/2, some com a nota das listas, e aplique a tabela novamente.
Notas:
Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.
Tentaremos seguir de perto a abordagem no livro do Michael Sipser, mas em alguns momentos teremos que recorrer a outras referências.
No programa a seguir há indicação de trechos de livros indicados para cada tópico.
I - LINGUAGENS REGULARES
- Autômatos finitos :: Sipser 1.1 | Hopcroft 2.1, 2.2
- Autômatos finitos não-determinísticos :: Sipser 1.2 | Hopcroft 2.3, 2.5
- Expressões regulares :: Sipser 1.3 | Hopcroft 3
- Gramáticas regulares :: A DEFINIR
- Propriedades de linguagens regulares :: Hopcroft 4.2, 4.3
- Lema do bombeamento :: Sipser 1.4 | Hopcroft 4.1
II - LINGUAGENS LIVRES DE CONTEXTO
- Gramáticas livres de contexto :: Sipser 2.1 | Hopcroft 5.1
- Ambiguidade :: Sipser 2.1 | Hopcroft 5.2, 5.4
- Autômatos com pilha :: Sipser 2.2 | Hopcroft 6
- Propriedades de linguagens livres de contexto :: Hopcroft 7.3-7.4
- Lema do bombeamento :: Sipser 2.3 | Hopcroft 7.2
III - LINGUAGENS RECURSIVAMENTE ENUMERÁVEIS
- Máquinas de Turing :: Sipser 3.1 | Hopcroft 8
- Agoritmos, linguagens recursivas e recursivamente enumeráveis :: Sipser 3 | Hopcroft 8
- Modelos de computação: funções recursivas e λ-Cálculo :: Jung | Rojas
- Decidibilidade e problema da parada :: Sipser 4 | Hopcroft 9
- Reduções e indecidibilidade :: Sipser 5
IV - CLASSES DE COMPLEXIDADE
- Noções de complexidade computacional. Classes P e NP :: Notas de Criptografia, Apêndice C: [ C.1 antes de C.1.1 ]; C.4; [ C.6 excetp classes BPP e PSPACE]; [ C.7 até antes de C.7.1 ] | Papadimitriou-Steiglitz 8.1-8.5, 15