| Algoritmo Bsp/cgm Para Computacao De Circuitos De Euler Em Grafos |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
12/09/2002 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Edson Norberto Caceres
- Henrique Mongelli
- Siang W. Song
|
| Resumo |
Nesta Dissertação Descrevemos E Implementamos Um Algoritmo Paralelo Utilizando O Modelo Bsp/cgm (bulk Synchronous Parallel/coarse Grained Multicomputer) Para Obtenção De Circuitos De Euler Em Grafos. Este Algoritmo é Baseado No Algoritmo Proposto Por Cáceres Et Al [cdss92] Que Utiliza O Modelo Pram (parallel Random Access Machine). Do Nosso Conhecimento, Não Há Na Literatura Outros Algoritmos Paralelos Em Modelos De Granularidade Grossa Para O Problema De Circuitos De Euler Em Grafos.
O Algorimo Proposto Foi Implementado Utilizando O Padrão Mpi (message Passing Interface) E A Linguagem C. O Programa Foi Executado No Beowulf Com 66 Nós Instalado No Instituto De Computação Da Unicamp. Os Resultados Obtidos Com A Implementa~ao Confirmaram Os Resultados Teóricos Da Complexidade Do Algoritmo, O Que é Uma Característica Do Modelo Bsp/cgm. |
| Download |
|
|
| O Problema Das Quatro Cores. |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
12/09/2002 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
- Marcelo Henriques de Carvalho
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Edson Norberto Caceres
- Marcelo Henriques de Carvalho
|
| Resumo |
é Possível Colorir Qualquer Mapa Com Não Mais Do Que 4 Cores, De Forma Que Regiões Vizinhas Recebam Cores Diferentes?. Essa Pergunta Foi Feita Pela Primeira Vez Em 1852 Por Francis Guthrie, Enquanto Coloria Um Mapa Da Inglaterra. Esse Problema é Conhecido Como Problema Das 4 Cores. Em 1878, Foi Publicada A Primeira Referência Impressa Da Conjetura, No Periódico Proceedings Of The London Mathematical Society. Essa Publicação Disparou A Febre Do Problema, Com Um Grande Número De Variações Equivalentes, Conjeturas E Falsas Demonstrações. O Problema Das 4 Cores é Responsável Por Muito Do Que Se Conhece Hoje Em Teoria Dos Grafos. A Tentativa De Resolvê-lo Possibilitou O Desenvolvimento De Vários Ramos Da Teoria Dos Grafos, Através Da Sua Equivalência Com Outros Problemas. Portanto, Existem Outros Enfoques Que Podem Ser Dados Em Um Estudo Deste Problema. No Estudo Que Desenvolvemos, Nosso Principal Objetivo Foi Estudar A última Demonstração Do Teorema Ds 4 Cores Publicada Em 1997. O Teorema Afirma Que Os Vértices De Um Grafo Planar Sem Laços Podem Ser Coloridoscom 4 Cores Distintas. Este Teorema é Equivalente Ao Problema Das 4 Cores. A Demonstração Do Teorema é Feita Por Contradição . Supõe-se A Existência De Um Contra-exemplo Para O Teorema E Estudando As Propriedades Deste Contra-exemplo Chega-se A Uma Contradição. Em Várias Partes Da Demonstração Faz-se Necessário O Uso De Programas De Computador.
O Nosso Trabalho Resume-se No Detalhamento Da Demonstração Deste Teorema. Para Isto Foi Necessário O Estudo Detalhado De Vários Outros Livros E Artigos, Alguns Destes Publicados No Início Do Século Passado E Outros Publicados Depois De 1997 Pelos Mesmos Autores, Com O Objetivo De Esclarecer Dúvidas E Explicar Com Maior Clareza Os Programas De Computador Indispensáveis Para Esta Demonstração. |
| Download |
|
|
| Algoritmos Lineares Para Teste De Planaridade Em Grafos |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
16/08/2002 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
- Marcelo Henriques de Carvalho
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Edson Norberto Caceres
- José Coelho de Pina Junior
- Marcelo Henriques de Carvalho
|
| Resumo |
Este Trabalho Trata De Reconhecer A Classe Dos Grafos Planares, Ou Seja, Grafos Que Admitem Uma Representação No Plano Sem Cruzamento De Arestas. Algoritmos Com Complexidade De Tempo Linear Para O Reconhecimento De Grafos Planares São Conhecidos Desde A Década De 70. Dois Deles São Clássicos Mas Complexos. São Eles Os Algoritmos De Hopcroft E Tarjan, E De Booth E Lueker. Mais Recentemente, Shih E Hsu Encontraram Um Outro Algoritmo Eficiente, Que Vem Sendo Considerado Mais Simples Que Os Anteriores. Examinamos Estes Três Algoritmos Eficientes Quanto à Forma Como Caracterizam Planaridade E Proporcionam Complexidade Linear Aos Algoritmos. Procuramos Apresentar De Maneira Mais Clara Possível Os Dois Algoritmos Clássicos E Discutir A Simplicidade Aparente Do Algoritmo De Shih E Hsu. |
| Download |
|
|