Collapse Sobre o curso

Professor responsável

  • Ruy J.G.B. de Queiroz ruy at cin.ufpe.br

Horário e sala

  • Terça-feira 10h00 - 12h00 (Sala D005)
  • Sexta-feira 08h00 - 10h00 (Sala D005)

Forum

  • Informática Teórica 2013.2

Monitores

  • Bruno Soares da Silva
  • David Barros Hulak
  • Diego Aragão (dca@cin.ufpe.br) (coordenador)
  • João Gabriel Santiago Maurício de Abreu
  • Natália Paola de Vasconcelos Cometti

Ementa

  • PARTE I - Linguagens formais e autômatos:
    Autômatos finitos determinísticos (AFD) / Autômatos finitos não-determinísticos (AFN) / Linguagens regulares (proprieades e operações) / Expressões regulares (ER) / Equivalência AFD<=>AFN<=>ER / Linguagens não-regulares (Lema do bombeamento) / / Gramáticas Livres de Contexto (GLC) / Linguagens Livres de Contexto (proprieades e operações) / Ambiguidade de normalização de GLCs / Autõmatos com Pilha (AP) / Equivalência GLC<=>AP / Linguagens não-livres de contexto (Lema do bombeamento)
  • PARTE II - Teoria da Computabilidade:
    Máquinas de Turing (MT) / Variações das MT / Não-determinismo / Tese de Church-Turing / Linguagens recursivas e recursivamente enumeráveis / Decidibilidade / O Problema da Parada / Teorema de Rice / Redutibilidade.
  • PARTE III - Teoria da Complexidade:
    Complexidade de Tempo / Classes de complexidade / Redução polinomial / P vs. NP / NP-completude / Teorema de Cook-Levin / Complexidade de Espaço / Teorema de Savitch / PSPACE-completude.

Bibliografia

Bibliografia básica

  1. Michael Sipser. Introdução à Teoria da Computação, Cengage Learning, 2007, ISBN 8522104999.
    (Tradução brasileira da 2ª. Ed. Norte-americana de Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 2005 ) (A 3ª. Ed. Norte-americana já foi publicada em Julho/2012, mas a sua tradução brasileira ainda não está disponível )

Bibliografia Suplementar

  1. John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introdução à Teoria dos Autômatos, Linguagens e Computação, Editora Campus, Outubro 2002, ISBN 85-352-1072-5.
    (Tradução brasileira de: John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd Ed., Addison-Wesley, 2001, ISBN: 0-201-44124-1. - Página de apoio )
  2. Harry R. Lewis, Christos Papadimitriou. Elements of the Theory of Computation (2nd Ed.), Prentice-Hall, 1998, ISBN: 0-13-262478-8.
  3. Dexter Kozen. Automata and Computability, Springer, 1997, ISBN: 0-387-94907-0.
  4. Christos Papadimitriou. Computational Complexity, Addison Wesley, 1994, ISBN: 0-201-53082-1.

Avaliação

A avaliação será feita em três unidades correspondendo exatamente a cada uma das partes do curso (Partes I, II e III). A média do curso (MC) será calculada como

MC = (M1+M2+M3) / 3

onde:

  • M1 = Média da 1a. Unidade
  • M2 = Média da 2a. Unidade
  • M3 = Média da 3a. Unidade

A média de cada unidade será calculada a partir das notas de uma prova escrita valendo 70%, e da média das mini-provas, valendo 30% da média da unidade.

Segunda chamada

Ao final do curso será oferecida a chance de fazer uma prova de segunda chamada que substituirá 1(uma) prova que o aluno não realizou. O assunto da segunda chamada engloba todo o conteúdo do curso.

Prova final

Se MC >= 7, o aluno está aprovado por média.

Se MC < 3, o aluno está reprovado por média.

Se 3 <= MC < 7, o aluno deverá fazer uma prova final (PF).

A prova final versará sobre o assunto de todo o curso.

A média final será calculada como

MF = (MC + PF) / 2.

Se MF >= 5, o aluno está aprovado.

Se MF < 5, o aluno está reprovado.

IMPORTANTE: As provas serão discutidas posteriormente (em horário a ser definido) e os alunos poderão solicitar revisão. Entretanto, não há margem "extra" de tolerância quanto às médias.

Frequência obrigatória

A frequência às atividades escolares é obrigatória, respeitados o turno e o horário previstos para a disciplina (conforme a Resolução n° 04/1994 link to document). Considera-se reprovado por falta, independentemente do aproveitamento escolar, o estudante que não tiver comprovado sua participação em pelo menos 75% (setenta e cinco por cento) das aulas, ou ao mesmo percentual de avaliações parciais de aproveitamento escolar.

Podem ser oferecidas, no contexto da discplina, atividades de monitoria fora do horário de aula mencionado acima. Essas atividades têm caráter complementar e de reforço e a participação dos alunos é altamente recomendada. Entretanto, a participação nessas aulas é opcional e não contam para efeito de contabilização de frequência.

Importante

  1. Esta página tem objetivo de facilitar a comunicação e a organização do curso e será feito esforço para manter a informação aqui contida correta e atualizada. Entretanto, o conteúdo desta página tem caráter fundamentalmente informativo e não-vinculativo, podendo ser modificado a qualquer altura à discrição dos professores responsáveis no melhor interesse dos objetivos didáticos e acadêmicos, bem como da observância às regras instituicionais.
  2. Sobrepõem-se às informações aqui contidas qualquer comunicado em contrário emitido publicamente em sala de aula pelos professores responsáveis.
  3. Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com os professores responsáveis.
  4. Documentos de referência:
    • Regimento da UFPE link
    • Calendário acadêmico UFPE 2013 link to PDF
    • Resolução n° 04/1994 - Estabelece normas complementares de avaliação de aprendizagem e controle da frequência nos Cursos de Graduaçãolink to document
    • Manual acadêmico UFPE 2012 link to PDF
Show Programação
Show Material
Show Notas

 

 

 

Anúncios e novidades

  • 17 Mai: Página do curso no ar.