DEPARTAMENTO DE ENGENHARIAS E CIÊNCIA DA COMPUTAÇÃO Disciplina: Teoria da Computação Código: 30-475 Carga Horária: 40h (30h Teórica + 10h Prática) Nº de Créditos: 02
EMENTA Teoria dos Grafos. Complexidade de algoritmos. Máquinas.
OBJETIVOS Ao término da disciplina, o aluno deve ser capaz de compreender aspectos básicos relacionados com teoria dos grafos, complexidade de algoritmos e de computabilidade.
CONTEÚDOS CURRICULARES Complexidade de algoritmos Introdução, Conceitos Básicos Tipos de Complexidade de Problema Métodos de Projeto de Algoritmos Teoria dos Grafos Conceitos básicos, isomorfismo, vizinhanças, cortes e graus Caminhos e circuitos, subgrafos Emparelhamento Grafos conexos e componentes, coloração de vértices e arestas, Planaridade Máquinas Programas e Máquinas, noção de Máquinas Universais, Tese de Church
METODOLOGIA Visando desenvolver competências técnicas, cognitivas e comportamentais nos alunos, as aulas, de forma variada, terão como metodologias: (expositivo-dialogadas com estudos dirigidos), ativa e sócio-interacionista (professor como mediador de atividades em que os alunos trabalham em equipes e interagem com a comunidade universitária). Os alunos desenvolverão Trabalhos Discente Efetivos (TDEs), no total de 20h, de acordo com o planejamento do professor: estudos de caso, pesquisas bibliográficas, resolução de problemas, lista de exercícios. A fixação dos conteúdos será por meio de resolução de exercícios ou algoritmos pelo professor em sala, com discussão sobre as soluções individuais ou obtidas em grupo. No decorrer do semestre, serão utilizadas metodologias ativas com o objetivo de potencializar o processo de ensino-aprendizagem.
AVALIAÇÃO Para a avaliação da disciplina, o professor irá verificar se as competências propostas no plano de ensino foram desenvolvidas pelo acadêmico, por meio de instrumentos de avaliação que irão compor a nota final, através das seguintes avaliações: Parte da avaliação da disciplina, com peso 20%, será referente às atividades desenvolvidas nas TDEs, conforme previsto pelas regras da graduação Ativa da URI; O restante das notas consistirá em provas e trabalhos (teóricos e/ou práticos), com assuntos específicos da disciplina: trabalhos individuais, prova escrita, provas práticas de programação utilizando ambiente automatizado de correção, quiz de perguntas e respostas sobre o conteúdo e listas de exercícios. A atribuição de notas para a avaliação do desempenho do acadêmico, segue o prescreve o Regimento Geral da Universidade, Art. 88 a 92. |
BIBLIOGRAFIA BÁSICA DIVERIO, T. A., MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade. 3. ed. Porto Alegre: Bookman, 2011. v 5. (Biblioteca Virtual). SIPSER, M. Introdução à teoria da computação. São Paulo: Thomson Learning, 2007. TOSCANI, L.V., VELOSO, P. Complexidade de Algoritmos -V.13 – 3.ed. Bookman, 2012.
BIBLIOGRAFIA COMPLEMENTAR BOAVENTURA NETTO, P.O.; Grafos-Teoria, Modelos, Algoritmos 4.ed. E Blucher, 2010. JURKIEWICZ, S. Grafos - Introdução E Prática – Ed. Edgard Blucher, 2009 NICOLETTI, M. C.; HRUSCHKA JR.; R. E.. Fundamentos Da Teoria Dos Grafos Para Computação. Ed. EDUFSCAR, 2010. SEDGEWICK, R.. Algorithms in C. 3. ed. Boston (USA): Addison-Wesley, 2002. v 5.
|