http://www.cic.unb.br/~rezende/ac.htm

Autômatos e computabilidade

Ciência da Computação - UnB
Prof. Pedro A. D. Rezende
prezende at unb.br

Semestre 2/2007: Terça, Quinta e Sexta, 10:00 às 11:50h Sala Conf 2
Mantenha-se em contato com esta página até o final do semestre.
Notas, prazos, enunciados dos trabalhos, avisos, etc. serão divulgados aqui.

Esta página contém partes atualizadas periodicamente.
Versão inicial
: 01/09/07 - Última versão: 20/12/07 10:45h

Índice

Apresentação
Objetivos
Programa
Metodologia
Atividades
    Semanais
    Listas de exercícios
Avaliação
Bibliografia


Apresentação

Guiados por essas perguntas, apresentaremos a disciplina Autômatos e Computabilidade. A teoria aqui apresentada foi desenvolvida em busca de respostas a perguntas como estas. Essa busca produziu formalismos e métodos matemáticos cujas aplicações e desdobramentos levaram à informática de hoje.

Em particular, ela permitiu traçar o rumo em que a arquitetura de computadores e da engenharia na microeletrônica evoluiu, a derivação de sub-teorias e formalismos específicos -- modelos computacionais -- para o desenvolvimento dos modernos compiladores, interpretadores e otimizadores, e uma abordagem profícua ao aspecto operacional da inteligência humana.

E mais: as respostas encontradas desvelam um mistério da natureza cuja descoberta causou uma crise que produziu perda de inocência e uma profunda revolução nos fundamentos da matemática e na filosofia da ciência (vide seminário). Apertem os cintos.

Objetivos

Estudar os modelos computacionais mais relevantes, seu poder expressivo, as relações importantes entre estes e suas possíveis aplicações. Entender o papel desses modelos nos processos produtivos na microeletrônica e no desenvolvimento de softwares. Para isso, precisamos apreender um certo formalismo matemático, desenvolvido para permitir a formulação e aplicações de conceitos tais como:

Programa

A ementa oficial da disciplina é a seguinte
    * Revisão
          o Noções Matemáticas e Terminologia
          o Definições, Teoremas e Provas
          o Tipos de Provas
    * Introdução
          o Noções de Automata, Computabilidade e Complexidade
          o Ferramentas de suporte à disciplina
    * Automata e linguagens
          o Linguagens Regulares e Autômato Finito
          o Não determinismo
          o Expressões regulares
          o Propriedades das Linguagens Regulares
          o Linguagens não regulares
          o Gramáticas Livre de Contexto
          o Autômato Pushdown
          o Propriedades das Linguagens Livre de Contexto
          o Além das Linguagens Livre de Contexto
    * Computabilidade
          o Máquina de Turing
                + Máquina com um número Ilimitado de Registradores
                + Funções Recursivas
                + Máquina Universal de Turing
                + Variantes das Máquinas de Turing
                + Definição de algoritmo
          o Decidibilidade
                + Linguagens Decidíveis
                + Problema da Parada
          o Redutibilidade
          o Hierarquia de Chomsky
          o Tese de Church-Turing
          o Tópicos Avançados
                + O Teorema da Recursão
                + Decidibilidade de teorias lógicas
                + Reducibilidade de Turing
                + Definição de Informação
    * Complexidade
          o Medidas de Complexidade
          o A classe P
          o A classe NP
          o NP-completude
          o Problemas NP-completos

Atividades

Metodologia

Será seguido, como bibliografia de referência, o livro de Hopcroft e Ullman, "Introduction to Automata, Languages and Computation" (capa 'Alice no país das maravilhas'). As aulas expositivas seguirão o texto referência mas, como ele é bastante amplo, o tempo e contexto da nossa disciplina não nos permite cobri-lo todo. Cobriremos o programa seqüen­cialmente até onde for possível. É importante que o aluno se dedique individualmente ao estudo do texto de referência, para bem assimilar os conceitos e para que a parte expositiva do curso lhe seja produtiva.

Serão disponibilizados textos complementares e ferramentas para auxiliar os alunos no treinamento do uso do formalismo e nos exercícios. Pressupondo esforço prévio do aluno para sanar eventual dúvida ou resolver deter­minado problema, o professor estará disponível em sua sala para atendimento, durante horário a ser posteriormente combinado. Nas páginas web correspondentes a este documento, serão registradas as atividades do curso, incluindo links para material didático complementar. Eventualmente usaremos também a página do curso “Automatos e Computa­bilidade” no Moodle em http://aprender.unb.br

1a. Semana

Listas de Exercício

Serão passadas tres ou quatro listas de exercício obrigatórias, e uma ou duas opcionais. A primeira lista obrigatória será corrigida antes da primeira prova, as demais conforme haja necessidade. As listas opcionais serão para efeito de arredondamento de menção, quando aplicável a critério do professor, e corrigidas conforme haja necessidade.

Lista de exercícios não obrigatória, não opcional para preparação à segunda prova

  1. Depois da 1a. prova, com quais modelos computacionais voce travou conhecimento através desta matéria?
  2. Desses modelos, quais admitem variantes, conforme esse conhecimento?
  3. Desses modelos, quais admitem mais de uma semântica (interpretação do funcionamento), quais não?
  4. Dos que admitem mais de uma semântica, como você as descreveria?
  5. Dos que admitem mais de uma variante, quais variantes alteram o poder expressivo do modelo, quais não?
  6. A menos de variantes equivalentes, quais modelos/semânticas guardam relação direta (p.ex., menor, maior, igual) com respeito ao poder expressivo, citando exemplos se possível?
  7. Como voce hierarquizaria essas relações, e como voce descreveria a hipótese metafísica que "fecharia" esta hierarquia no seu topo?
  8. O que é o "problema da parada", e como vc descreveria sua importância para a teoria da computação?
  9. O que são classes de complexidade computacional?
  10. Quais dessas classes voce considera mais importantes, e por que?

Avaliação

Aluno Lista 1 Lista 2
Clique
Lista 3 Prova 1 Prova 2 Pontos | Menção Inassiduidades | faltas 
até 18/12 (35 chamadas)
03/27000 7.4
4,5 <7.5 5.0
5.3
< 58.5 | MM
02 | 00 :  9.4
03/84101 2.0
5,9 <10 5.5
8.4
< 70.3 | MS 10 | 05:   7.1
03/86740 --
4,8 0
4.2
2.4
< 35.1 | MI 12 | 06:   6.5
04/27951 7.2
6,2 <10 7.9
8.0
< 81.0 | MS 01 | 00:   9.7
04/80711 8.8
7,8 <7.5 5.8
6.4
< 66.9 | MM 11 | 09:   6.8
04/82081 7.4

0
7.5
4.5
49.2 <  < 55.8 | 22 | 12:   3.7
04/86001 6.3
5,9 0
4.8
8.0
61.6 | MM 10 | 06:   7.1
04/87015 9.5

0
4.4
1.5
31.2 <  < 37.8 | MI 22 | 12:   3.7
04/93902 7.9
6,2 <10 3.5
3.1
< 47.4 | MI 05 | 01:   8.5
04/94968 8.1
6,5 <10 5.2
7.8
< 73.0 | MS 05 | 04:   8.5
04/95107 9.7
5,6 0
3.5
2.8
37.9 | MI 14 | 11:   6.0
05/15710 8.5
9,2 <10
6.5
8.2
< 80.5 | MS 02 | 01:   9.4
05/19308 8.2
9,0 <10 5.2
3.7
< 55.6 | MM 10 | 08:   7.1
05/20667 7.5
6,9 <10 4.7
8.0
< 71.8 | MS 02 | 02:   9.4
05/20713 --

<10
7.6

08 | 07:   7.7
05/23101 7.2
5,9 <10 8.8
7.1

03 | 02:   9.1
05/24387 3.7
7,6 <10 7.3
9.3

03 | 00:   9.1
05/24557 7.6
6,9 <5.0 7.0
7.9

06 | 02:   8.2
05/24859 6.4
2,3 <7.5 6.9 6.8

04 | 04:   8.8
05/31758 5.5
6,5 <7.5 5.8
2.6

06 | 06:    8.2
05/37608 5.0

<7.5 3.8
3.4

14 | 07:   6.0
05/37861 8.9
9.5*
<10 8.5
9.5

00 | 00:   10.0
05/39643 5.7

<7.5 7.1
7.5

05 | 04:   8.5
05/41923 5.2
3,8 <10 4.2
6.9

17 | 07:    5.1
05/41940 9.0
6,3 <10 7.1
6.9

01 | 01:    9.7
05/99409 7.2
8.7*
<10 7.5
6.2

07 | 06:    8.0
OBS
* - Falha do professor / monitor no envio / tratamento de arquivo(s): Nota corrigida
Avisos
Cálculo final da menção a ser divulgado antes do horário de revisão.
Horário de Revisão: Dia 19 20/12/07 Das 11 às 12:30 h e das 14 às 15h

PROVAS -
Haverá duas provas escritas, em 22 de outubro e 11 18 de dezembro de 2007.

CRITÉRIOS-
Os elementos e pesos para a avaliação serão os seguintes. A chamada será feita no início da aula, eventualmente confirmada por uma segunda chamada ao final da aula. Atraso ocorre quando o aluno não estiver presente para responder à chamada no início da aula. Assiduidade ocorre nas aulas em que o aluno não falta, não se atrasa nem se ausenta por longo tempo da aula depois de responder à chamada.
Trabalhos serão aceitos com atraso mediante redução na nota máxima alcançável. Sob nenhuma hipótese haverá prova de reposição.
Após a segunda prova, a avaliação seguirá roteiro e prazos a serem definidos, para divulgação do resultado da avaliação e revisão final.

Bibliografia

Livro texto de referência:
Ferramenta:
Outros textos:
Leitura complementar:
Serão linkados aqui, ao longo do semestre, textos e ferramentas disponíveis na web que possam vir a ser de utilidade ao aluno. Sugestões são bem-vindas.