Navegar

17 de novembro de 2016, 16:25h

Aspectos Teóricos da Computação

Aspectos Teóricos da Computação
Autor :
Páginas : 292
Publicação : IMPA, 1979
ISBN: 978-85-244-0111-4
1ª edição

Conteúdo

Prefácio

Parte A Programação de Computadores

Capítulo I – Programação de Computadores e Indução Matemática

1. Introdução
2. Procedimentos e algoritmos
3. Programas e linguagens de programação
4. Iteração e recursão
5. Exemplos de aplicação

Exercícios
Notas bibliográficas

Parte B Complexidade de Algoritmos

Capítulo I – Complexidade de Algoritmos: Noções Básicas

1. Introdução
2. Máquinas de Turing
3. A tese de Church
4. Medidas de complexidade de máquinas de Turing

Exercícios
Notas bibliográficas

Capítulo II – Problemas Indecidíveis

1. Introdução
2. Um problema indecidível de computação
3. Conceitos básicos
4. O resultado principal
5. Redutibilidades
6. Outros problemas indecidíveis em Matemática

Exercícios
Notas bibliográficas

Capítulo III – Produto Eficiente de Matrizes

1. Introdução
2. O algoritmo de Strassen
3. Problemas correlatos
4. Limites inferiores

Exercícios
Notas bibliográficas

Capítulo IV – É Mais Fácil Verificar a Solução do Que Encontrá-la?

1. Introdução
2. Conceitos básicos
3. Eficiência
4. Fórmulas do cálculo proposicional
5. Redutibilidade e conjuntos NP-m-completos
6. Outros problemas NP-m-completos

Exercícios
Notas bibliográficas

Parte C Teoria dos Grafos

Capítulo I – Grafos e Subgrafos

1. Grafos e grafos simples
2. Algumas representações de grafos no computador
3. Isomorfismo entre grafos
4. Cardinalidade e inclusão. Subgrafos
5. Graus
6. Passeios
7. Componentes, conexão e cortes

Exercícios
Notas bibliográficas

Capítulo II – Florestas

1. Florestas e árvores
2. Subflorestas maximais

Exercícios
Notas bibliográficas

Capítulo III – Emparelhamentos e Coberturas

1. O problema dos casamentos
2. Uma igualdade minimax

Exercícios
Notas bibliográficas

Capítulo IV – Coloração de Vértices e o Teorema de Brooks

1. Coloração de vértice

Exercícios
Notas bibliográficas

Capítulo V – O Teorema de Ramsey e Suas Aplicações

1. Introdução
2. O Teorema de Ramsey
3. O caso particular dos grafos (k=2)
4. Outras aplicações do teorema de Ramsey

Exercícios
Notas bibliográficas

Capítulo VI – Grafos Orientados

1. Introdução
2. O teorema da dicotomia
3. Grafos fortemente conexos
4. Grafos acíclicos

Exercícios
Notas bibliográficas

Parte D Teoria dos Autômatos Finitos

Capítulo I – Relações, Funções e Monóides

1. Relações e funções
2. Monóides

Exercícios
Notas bibliográficas

Capítulo II – Conjuntos Racionais e o Teorema de Kleene

1. Autômatos, conjuntos reconhecíveis e conjuntos racionais
2. Operações sobre conjuntos reconhecíveis
3. Sistemas de equações lineares
4. O Teorema de Kleene
5. Monóide de um autômato e o monóide sintático

Exercícios
Notas bibliográficas

Capítulo III – Conjuntos Inteiros e o Teorema de Schützenberger

1. Conjuntos inteiros e monóides aperiódicos
2. Algumas propriedades de monóides aperiódicos
3. Demonstração do Teorema 1
4. Um exemplo

Exercícios
Notas bibliográficas

Bibliografia

Índice de Notações

Índice Alfabético

Autores

Cláudio L. Lucchesi
Imre Simon
Istvan Simon
Janos Simon
Tomasz Kowaltowski

Os autores iniciaram-se em Computação em torno do saudoso computador IBM 1620, instalado em 1962, no então Centro de Cálculo Numérico da Escola Politécnica da Universidade de São Paulo. Formaram-se Engenheiros Eletrônicos por aquela Escola. Realizaram estudos de pós-graduação no exterior, obtendo o grau de Ph.D. em Computação.

Cláudio Lucchesi formou-se em 1968 e obteve o grau de Ph.D. na Universidade de Waterloo em 1976. Atualmente é Professor na UNICAMP. Suas áreas de interesse são: teoria dos grafos e síntese de algoritmos eficientes.

Imre Simon formou-se em 1966, e obteve o grau de Ph.D. na Universidade de Waterloo em 1972, Imre é Professor na USP. Suas áreas de interesse são: Pseudovariedades de linguagens e semigrupos, Teoria da multiplicidade do semiring tropical, palavras, automata e algoritmos.

Istvam Simon formou-se em 1969, e obteve o grau de Ph.D na Universidade de Stanford em 1977, foi Professor na USP. Suas áreas de interesse são: análise de algoritmos e teoria da complexidade.

Janos formou-se em 1969 e obteve o grau de Ph.D na Universidade de Cornell em 1974. Foi Professor na UNICAMP. Suas áreas de interesse são: teoria de computabilidade e complexidade concreta de algoritmos.

Tomasz formou-se em 1966 e obteve o grau de Ph.D na Universidade da California, Berkeley em 1973. Tomasz foi Professor da USP e atualmente é diretor do Instituto de Computação da UNICAMP. Suas áreas de interesse são: projeto, implementação e semântica de linguagens de programação e verificação formal da correção de programas.