|
Universidade Federal de Mato Grosso do Sul
Departamento de Computação e Estatística Fundamentos da Teoria da Computação
|
|
Principal | Informações | Livros | WWW | Diário | Tarefas |
ObjetivosA disciplina Fundamentos da Teoria da Computação tem por objetivo introduzir o estudante de graduação em Ciência da Computação às linguagens formais, à teoria dos autômatos e à complexidade computacional, com ênfase nos dois primeiros tópicos. O sucesso prático da Ciência da Computação se deve em grande parte aos seus sólidos e elegantes fundamentos. Essa ciência tem suas questões fundamentais, como por exemplo: O que é um algoritmo? O que pode e o que não pode ser computado? Quando um algoritmo pode ser considerado viável na prática? O foco do curso é justamente nessas idéias fundamentais, modelos e resultados que permeiam a Ciência da Computação e que são de certa forma seus paradigmas básicos. Matemáticos freqüentemente fornecem respostas a certas questões bem antes do mundo todo encontrar razões para fazer essas perguntas. A operação de redes de relés utilizada nos primeiros computadores é descrita exatamente pelas funções de Boole. Note que George Boole fez sua contribuição à Ciência da Computação no meio do século XIX e a álgebra de Boole é usada ainda hoje para representar circuitos TTL. Em meados de 1930, Alan Turing formalizou o conceito de um algoritmo com a apresentação de um dispositivo abstrato de computação e caracterizou as limitações de tais máquinas. Nos anos 50, a abstração dos conceitos por detrás das gramáticas de linguagens naturais forneceu as bases teóricas para o desenvolvimento de linguagens de programação. As aplicações dessa teoria são evidentes em especial na análise léxica e sintática de linguagens de programação, em modelos de sistemas biológicos, projeto de hardware e em linguagens naturais. |
Pré-requisitosFundamentos da Teoria da Computação tem como pré-requisito oficial a disciplina de Matemática Discreta. Familiaridade com conceitos como conjuntos, relações, tipos especiais de relações binárias, funções e técnicas de demonstração são muito importantes. Noções de algoritmos e de programação também são necessárias.
Tópicos
|