GRUPO: 
Núcleo de Formação Tecnológica

GRUPO: 
Núcleo de Formação em Sistemas de Computação

OBJETIVOS GERAIS DA DISCIPLINA: 
Esta matéria aborda os tópicos fundamentais concernentes à organização e à arquitetura dos computadores. O propósito básico é apresentar clara e precisamente, tanto quanto possível, a natureza e as características dos sistemas de computadores modernos.

EMENTA DO PROGRAMA:
01. Organização de Computadores:
- Evolução e Desempenho dos Computadores
- Organização de Sistemas de Computadores
- Visão geral baseada em níveis dos computadores
 
02. Arquitetura de Computadores:
- O Sistema de Computador
- Unidade central de processamento
- Unidade de Controle
- Organização Paralela

BIBLIOGRAFIA:
01. Stallings, W., Computer Organization and Architecture, 4th Edition, Prentice, Hall, 682 pp, 1996.
02. Tanembaum, A.S.,   Structured Computer Organization, 3th ed, Prentice Hall, 459pp.

GRUPO: 
Núcleo de Formação em Sistemas de Computação

OBJETIVOS GERAIS DA DISCIPLINA: 
Abordar os fundamentos do projeto e implementação de sistemas operacionais.

EMENTA DO PROGRAMA:

Arquitetura de Sistemas Operacionais
Subsistemas do Núcleo (Kernel) 
Virtualização
Laboratório de SO

BIBLIOGRAFIA:

01. Andrew S. Tanembaum, Modern Operating Systems, Prentice Hall.
02. Maurice J. Bach.,The Desing of the Unix Operating System, Prentice Hall
03. Uresh Vahalia, UNIX Internals: The New Frontiers, Prentice Hall
04. Andrew S. Tanenbaum, “Distributed Operating Systems”, Prentice Hall. 

EMENTA

DISCIPLINA: Teoria da Computação

CÓDIGO: PGC103

CARGA HORÁRIA: 90h

CRÉDITOS: 5

OBJETIVOS GERAIS DA DISCIPLINA: O curso tem como objetivo responder às seguintes questões fundamentais: Quais são as capacidades e limitações dos computadores? O que faz com que alguns problemas sejam computacionalmente intratáveis?  Ao final do curso, o aluno estará habilitado a utilizar técnicas para demonstrar que certos problemas são impossíveis de serem resolvidos por um computador e que certos problemas, mesmo sendo possivel de ser resolvidos por uma máquina, demandam tempo e/ou espaço em memória impraticáveis.

EMENTA DO PROGRAMA:

Máquinas de Turing – Problemas Decidíveis – Problema da Parada – Redutibilidade –  Problemas Indecidíveis – Problemas Recursivamente Enumeráveis - Complexidade em Tempo – Problemas NP-completos – Complexidade em Espaço – Problemas PSPACE-completos.

DESCRIÇÃO DO PROGRAMA: 

1. Revisão de Teoria das Linguagens: Autômatos e Gramáticas Livres do Contexto Propriedades booleanas das linguagens regulares, lema do bombeamento para    linguagens regulares, gramáticas livres do contexto na forma normal de Chomsky, lema do bombeamento para linguagens livres do contexto.

2. Máquinas de Turing – Definição, Variantes (multi-fitas, não-deterministas, enumeradores)

3. Tese de Church – 10º Problema de Hilbert

4. Decidibilidade

4.1 Linguagens Recursivas (decidíveis), 

4.2 Recursivamente Enumeráveis (Turing-reconhecíveis), 

4.3 Prova da Indecidibilidade do Problema da Parada

4.4 Problemas decidíveis da teoria das linguagens formais

4.5 Problemas indecidíveis da teoria das linguagens formais

4.6 Redutibilidade 

4.7 Método do histórico das configurações

4.8 Problema de Correspondência de Post

5. Tópicos Avançados 

5.1 Teorema de Rice

5.2 Teorema da Recursão

6. Complexidade em Tempo

6.1 Classe P – Classe NP

6.2 O problema P = NP

6.3 Problemas NP-Completos : definição e exemplos

6.4 Técnicas para demonstrar NP-completude

6.5 Teorema de Cook – (demonstrar a NP-Completude do problema SAT)

6.6 Como lidar com problemas NP-completos

7. Complexidade em Espaço

7.1 Classe PSPACE 

7.2 Problemas PSPACE-completos

7.3 Teorema de Savitch

BIBLIOGRAFIA:

01. SIPSER, Michael  : Introduction to the Theory of Computation. Brooks/Cole Pub Co, 2a Edição 2005 (Livro Texto)

02. 3. LEWIS, H., PAPADIMITRIOU, C.: Elements of the Theory of Computation.  Prentice Hall. 2a Edição. 1997.

03. GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to NP-completeness. New York: H. Freeman, 1979. 

04. HAREL, David : Algorithmics – The Spirit of Computing. Addison-Wesley, 2a Edição, 1993.

05. KOZEN, D.: Theory of Computation. Springer, 2006.

06. SIPSER, Michael  : Introduction to the Theory of Computation. Brooks/Cole Pub Co, 2a Edição 2005 (Livro Texto)

07. 3. LEWIS, H., PAPADIMITRIOU, C.: Elements of the Theory of Computation.  Prentice Hall. 2a Edição. 1997.

08. GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to NP-completeness. New York: H. Freeman, 1979. 

09. HAREL, David : Algorithmics – The Spirit of Computing. Addison-Wesley, 2a Edição, 1993.

10. KOZEN, D.: Theory of Computation. Springer, 2006.

GRUPO: Núcleo de Formação Teórica

OBJETIVOS GERAIS DA DISCIPLINA: Esta disciplina tem como objetivo apresentar ao aluno os principais fundamentos da Lógica Clássica e suas aplicações em Ciência da Computação.

EMENTA DO PROGRAMA:

Parte 1 – Lógica Proposicional
- A linguagem da Lógica Proposicional
- A semântica da Lógica Proposicional
- Sistemas axiomáticos na Lógica Proposicional
- Tableaux semânticos na Lógica Proposicional
- Resolução na Lógica Proposicional
 
Parte 2 _ Lógica de Predicados
- A linguagem da Lógica de Predicados
- A semântica da Lógica de Predicados
- Sistemas axiomáticos na Lógica de Predicados
- Tableaux semânticos na Lógica de Predicados
- Resolução na Lógica de Predicados
 

DESCRIÇÃO DO PROGRAMA: 

Parte 1 – Lógica Proposicional
- A linguagem da Lógica Proposicional
- A semântica da Lógica Proposicional
- Sistemas axiomáticos na Lógica Proposicional
- Tableaux semânticos na Lógica Proposicional
- Resolução na Lógica Proposicional
 
Parte 2 _ Lógica de Predicados
- A linguagem da Lógica de Predicados
- A semântica da Lógica de Predicados
- Sistemas axiomáticos na Lógica de Predicados
- Tableaux semânticos na Lógica de Predicados
- Resolução na Lógica de Predicados
 

BIBLIOGRAFIA:

01. CHANG, C.L., Lee. R.C.T., Symbolic Logic and Mechanical Theorem Proving, Academic Press, 1973.
02. EBBINGHAUS, H.D., et all. Mathematical Logic, Springer Verlag, 1994.
03. EDERTON, H.B., A Mathematical Introduction to Logic, Academic Press, 1972.
04. KELLY, J., The essence of Logic, Prentice Hall, 1997
05. LLOYD, J.W., Foudations of Logic Programming, Springer Verlag, 1984.
06. MENDELSON, E., Introduction to Mathematical Logic, Wadsworth, 1987. 
07. SOUZA, J.N. Lógica para Ciência da Computação. Texto Técnico, UFU, 1999.
08. FITTING, M., First-Order Logic and Atomated Theorem Proving, Springer Verlag, 1990.

GRUPO: Núcleo de Formação Teórica

OBJETIVOS GERAIS DA DISCIPLINA: Introduzir as técnicas básicas de eficiência de algoritmos, com cálculo de tempo de pior caso e tempo médio. Isto é feito com a apresentação de um grande número de algoritmos que servem de ponto de partida para o desenvolvimento de novos algoritmos. Considera-se também uma introdução ao estudo comparativo dos principais métodos de computação, particularmente nos aspectos de complexidade de tempo e de espaço de problemas computacionais.

EMENTA DO PROGRAMA:

- Análise de Algoritmos –  Tempo de Execução - Notação assintótica

- Técnicas de estruturação de Algoritmos.

- Algoritmos de Ordenação, 

- Estruturas de dados elementares e avançadas

- Programação dinâmica – algoritmos gulosos

- Algoritmos de Busca em grafos.

DESCRIÇÃO DO PROGRAMA: 

1. Fundamentos

• Algoritmos – Análise de Algoritmos  – Tempo de Execução no pior caso e caso médio  Projeto de Algoritmos

• Crescimento de funções – notação assintótica

• Recorrência 

• Análise probabilistica e algoritmos aleatórios

2. Algoritmos de Ordenação

• Heapsort

• Quicksort

• Ordenação em tempo linear

• Medianas e estatísticas de ordem

3. Estrutura de Dados Elementares

• Pilhas, filas, listas, ponteiros e objetos

• Tabela Hash

• Arvores binárias

• Estatisticas de ordem dinâmicas

4. Técnicas Avançadas de Projeto e Análise

• Programação dinâmica

• Algoritmos Gulosos

5. Estruturas de Dados Avançadas

• Arvores B

• Heaps binomiais

• Heaps de Fibonacci

• Estruturas de dados para conjuntos – Algoritmos de Manipulação de Conjuntos

6. Algoritmos de grafos

• Algoritmos elementares de grafos

• Arvores espalhadas mínimas

• Caminhos mais curtos – de única origem e de todos os pares

• Algoritmo de Floyd-Warshall

• Algoritmo de Johnson para grafos esparsos

• Fluxo Máximo – Método de Ford-Fulkerson

• Emparelhamento bipartido máximo

• Algoritmos de push-relabel

BIBLIOGRAFIA:

01. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 3ª Edição,  2009.
(Edição em portugues : “Algoritmos-Teoria e Prática”, Editora Campus 2003)

02. David Harel and Yishai Feldman. Algorithmics: The Spirit of Computing, 3a Edição, Addison Wesley, 2004. 

03. Steven S. Skiena: The Algorithm Design Manual.  Springer, 2a Edição., 2008. 

04. Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.  (Series in Computer Science & Information Processing) Addison-Wesley Professional, 2011. 

05 Bernhard Korte, Jens Vygen. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), 4a Edição, 2010.

06. Vijay V. Vazirani. Approximation Algorithms. Addison-Wesley 2001

EMENTA:

A ementa está relacionada com o tema da Dissertação escolhido dentro de cada Linha de Pesquisa.

BIBLIOGRAFIA:

Relaciona-se com o acervo recomendável correspondente ao tema da Dissertação.

DESCRIÇÃO DO PROGRAMA:

O tema da Dissertação escolhido dentro de cada Linha de Pesquisa.