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
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.
