A importância da teoria para a prática, em qualquer ciência, seja factual ou exata, é imensa e  para elucidar a correlação entre ambos aspectos de uma ciência foram formuladas algumas frases consagradas tais como: "A teoria é a luz da prática'' e "A prática sem a teoria é cega, mas a teoria sem a prática é esteril''. Como é de supor, a ciência da computação, não poderia ficar alheia a esta interação, e portanto uma teoria para esta ciência se faz necessário para ``iluminar o caminho'' dos cientistas da computação (práticos), dos engenheiros em computação, dos analistas de sistemas, em fim de todos os professionais que usem a computação como objeto de estudo ou de trabalho. Assim, antes descrever que seria uma teoria para a ciência da computação, devemos exclarecer que entendemos por ciência da computação, ou simplesmente por computação.

Se entendermos por computação todo o que um computador pode realizar, devemos primeiro entender o que um computador é, cuja resposta poderia ser dada em termos de hardware e tecnologia. Mas, temos de ter cuidado, para não limitarnos á tecnologia do momento, pois nessa definição de computador devem coexistir os primeiros computadores, calculadoras,  super computadores e  futuros computadores. Ou seja, seria necessário unificar características essenciais e comuns a todos os computadores, de tal modo a distinguir um computador   de outros tipos de hardware, tais como elevadores, toca CD, etc. Isto nos levará, irremediavelmente, a definir uma noção abstrata de computador, onde ele possa ser melhor descrito em termos do que ele faz.

Teoria fornece conceitos e princípios que nos ajuda entender a natureza geral da ciência  do computador. O campo dessa disciplina inclui um vasto leque de tópicos especiais, desde projetos de máquinas até programação. O uso de computadores   no mundo real envolve uma riqueza de detalhes específicos que deve ser aprendido para uma aplicação com sucesso.  Isto faz com que a ciência da computação seja diversificada e ampla. Apesar dessa diversidade, existem alguns princípios básicos comuns. Para estudar esses princípios básicos, construiremos modelos abstratos de computadores e computação. Esses modelos contém as característcias importantes que são comuns tanto ao hardware quanto ao software, essenciais a muitos construtos especiais e complexos encontrados quando se trabalha com computadores. Mesmo que esses  modelos sejam muito simples para serem aplicados imediatamente nas situações do mundo real, o entendimento que ganhamos em estudá-los nos fornece fundamentos sobre os quais o desenvolvimento específico é baseado.  Esta abordagem não é exclusividade da ciência da computação. A construção de modelos é essencial em qualquer disciplina científica,  e a utilidade de uma disciplina depende frequentemente de teoria e leis simples, ainda que poderosas. Além do mais, as ideas que discutiremos tem algumas  aplicações imediatas e importantes. Os campos de projetos digitais, linguagens de programação e compiladores são os exemplos mais óbvios, existem porém muitos outros.

Este texto é o resultado de diversos cursos ministrados pelos autores  para a disciplina de "teoria da computação'' dos cursos de graduação em Ciências da Computação e Engenharia da Computação da UFRN. Como esta disciplina é prerequisito da disciplina "compiladores'',  emfatizamos os conceitos de linguagens formais, com suas abordagens através de autômatos e de gramáticas. Mas, como principalmente é um curso de "teoria da computação'', também estudamos a noção de computabilidade e consideramos uma breve discusão de complexidade computacional.

Os tópicos apresentados neste texto são de grande benefício para estudantes de informática, pois os coloca diante de  questões profundas de natureza computacional e de conhecimentos que não serão rapidamente obsoletos. Neste sentido, a computação passa a ser uma ciência e não uma mera tecnologia, e demonstra o poder das ferramentas matemáticas e métodos formais para modelar fenômenos da computação.

Neste texto, estudaremos diversas hierarquias de linguagens (formais), mas daremos um ênfases especial a três delas:
 

•  Linguagens regulares
• Linguagens livres de contexto
• Linguagens recursivamente enumeráveis.

Cada uma delas será abordada através de autômatos, que são modelos matemáticos de classes de computadores digitais,  e através de gramáticas, que são, basicamente, um conjunto de regras que dizem como construir palavras válidas da linguagem.

Exploramos o mais complexo destes autômatos, e observamos que ele não só tem capacidade para reconhecer linguagens formais, mas também pode transformar entradas em saídas, ou seja realizar computações como qualquer computador real faz. Este é o ponto de partida para se introduzir a noção de computabilidade e estabelecer os limites do mundo da computação.

Finalmente, com um conhecimento do que é e o que não é computável, podemos nos preocupar com analizar a qualidade das soluções, isto é, não só é importante saber se um determinado problema admite uma solução implementável num computador, mas se essa solução vai nos ser útil (se vai ser realizada em um tempo razoável, ou ainda se ela ocupa espaço de memória que dispomos). Ou seja, agora podemos nos preocupar da complexidade computacional das soluções. Para isso, introduzimos algumas medidas de complexidade baseadas no tempo de execução de um algoritmo e do espa\c co usado por ele.
 
 

Contacts

Academic Formation

Interest Areas

Curriculum Vitae

Main Publications

Students

Disciplines (in portuguese)

Research Groups

Conferences

Links

Livro