Anais do 13O Encontro de Iniciação Científica e Pós-Graduação do ITA – XIII ENCITA / 2007
Instituto Tecnológico de Aeronáutica, São José dos Campos, SP, Brasil, Outubro, 01 a 04, 2007.
ALGORITMOS EXATOS E PROBABILÍSTICOS PARA
PROBLEMA DE CORTE E SEQÜENCIAMENTO
Cesário Bruno de Barros Martins
Instituto Tecnológico de Aeronáutica – Rua H8C, nº205, S. José dos Campos, SP, Brasil, CEP 12228-461
Bolsista PIBIC-CNPq
[email protected]
Nei Yoshihiro Soma
Instituto Tecnológico de Aeronáutica – Pr. Mal. Eduardo Gomes, 50, S. José dos Campos, SP, Brasil, CEP 12228-900
[email protected]
Resumo. Com base em algoritmos e em técnicas computacionais conhecidas, modela - se abstratamente situações de tal forma que
a sua solução torne – se mais eficiente. Técnicas, como programação dinamica e iterações, e algoritmos, como o algoritmo de
Dijkstra – para calcular menor caminho de uma única origem – e o algoritmo de Ford-Fulkerson – para calcular o menor custo de
um certo fluxo em rede – são abordados.
Palavras chave: programação dinâmica, grafos, bicoloração, Dijkstra, Ford-Fulkerson
1. Introdução
Após o advento da computação, a capacidade humana de registrar e manipular dados em grandes quantidades
com precisão e rapidez cresceu intensamente. A manipulação da imensa quantidade de informação que tem-se hoje em
dia só e possível graças à evolução da informática.
Há mais de 2000 anos o homem tenta produzir algo que o auxilie de alguma forma. Na história da computação,
observa-se várias etapas até chegar no nível da tecnologia de hoje em dia.
O modelo dos computadores atuais segue a proposta do matemático húngaro John Von Neuman (1903 – 1957)
na qual define um computador seqüencial digital cujo processamento das informações é feito passo a passo,
caracterizando um comportamento determinístico, isto é, os mesmos dados de entrada produzem sempre a mesma
resposta.
Paralelamente à evolução das máquinas, surgiu a evolução dos algoritmos para resolução de problemas. Podese definir um algoritmo como uma seqüência não ambígua de instruções que é executada até que determinada condição
se verifique.
Não adianta a existência de uma supermáquina se não sabe-se quão bem utiliza – lá. O estudo dos algoritmos
permite encontrar passos bem definidos para a resolução de um certo tipo de problema.
Um bom algoritmo possui três importantes características:
1. O algoritmo realmente é correto. Usando este algoritmo em qualquer conjunto de dados relacionados ao
problema sempre fornecerá uma resposta correta.
2. O algoritmo é eficiente, isto é, ele procura fazer apenas passos necessários para a resolução do problema,
diminuendo assim o tempo de execução.
3. O algoritmo utiliza apenas a memória necessária.
O conhecimento de algoritmos já estudados é de enorme importância, pois muitos problemas computacionais
são modeláveis por eles. Abstraindo um problema, pode-se resolver-lo de diversas formas, e, cabe a nós escolher a mais
eficiente.
A seguir, utiliza-se técnicas computacionais e algoritmos já conhecidos, descritos por Cormen[1] e
Jungnickel[2], para se modelar abstratamente uma situação de tal forma que a solução do problema seja correta e
eficiente. As situações abordadas fazem parte de um acervo de problemas e podem ser acessadas pelo site da
Universidad de Valladolid[3] ou no site da XI Maratona de programação dos alunos da USP[4].
2. Situação 1
Nome original: This Sentence is False
Origem: ACM - Latin America - South America - 2002/2003
Site: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2612 acessado em 08/2007
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
2.1. Descrição
Em um reino tomado por intrigas e conspirações, o serviço secreto do rei encontrou um misterioso documento
que pode fazer parte de um perverso esquema. O documento é composto por várias sentenças que sustentam a falsidade
ou veracidade das outras sentenças. As sentenças são da forma “Sentença X é verdadeira/falsa”, em que X indica uma
das sentenças.
A tarefa é, com este documento em mãos, descobrir se as sentenças são consistentes e, se forem consistentes, o
maior número de sentenças verdadeiras.
Para melhor entendimento, exemplifica-se dois exemplos na Tab.1.
Tabela 1. Exemplos da entrada de dados da 1º situação apresentada.
Entrada
Entrada
1
Sentença 1 é falsa.
5
Sentença 2 é falsa.
Sentença 1 é falsa.
Sentença 3 é verdadeira.
Sentença 3 é verdadeira.
Sentença 4 é falsa.
0
Saída
Inconsistente
Saída
3
2.2. Comentário
Uma soluça ingênua para este problema seria, para cada sentença, supor que ela é falsa ou verdadeira e
verificar a consistência das frases como um todo. Posto que este procedimento é da ordem exponencial, mostra-se uma
solução elegante utilizando teoria dos grafos.
2.3. Solução
Pelo enunciado, cada sentença relaciona – se com outra em uma relação de verdade ou falsidade. Se o
documento for consistente, todas as frases são consistentes. Se pelo menos uma frase não for consistente, o documento
será inconsistente.
Para cada sentença, tem-se três variáveis: o estado da sentença de origem, o estado da sentença destino e o
estado da afirmação.
Sabe-se que cada estado pode ser verdadeiro ou falso. Indicando por V o estado verdadeiro e por F o estado
falso, tem-se um total de 8 situações possíveis, mostradas na Fig.1.
Sentença
origem
V
V
F
F
afirmação
V
F
V
F
Sentença
destino
Sentença
origem
V
F
V
Situações
consistentes
V
F
F
V
F
afirmação
V
Sentença
destino
F
F
V
F
V
Situações
inconsistentes
V
F
Figura 1 – Situações possíveis relacionando as sentenças.
Assim, para as situações consistentes, nota-se que, se a afirmação possuir estado verdadeiro, os estados das
sentenças de origem e destino serão iguais, e se a afirmação possuir estado falso, os estados das sentenças serão
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
diferentes. Este fato é uma invariante do problema, e pode-se basear nele para saber se o documento é consistente ou
não.
Baseado nas sentenças, cria-se um grafo em que os vértices são as sentenças e as arestas são as relações entre
elas.
Considere um grafo com sentenças consistentes. Suponha que existe um par de arestas ligando os mesmos
vértices em sentidos opostos. Se estas arestas tiverem estados diferentes, os estados dos vértices têm que, ao mesmo
tempo, ser iguais e diferentes. Como chega-se em um absurdo, tem-se que, em um grafo com sentenças consistentes, as
arestas serão não-direcionadas.
Usando esta construção, o grafo, formado pelas sentenças do exemplo 2 deste problema, será:
Figura 2 - Grafo formado pela entrada do exemplo 2.
Então, para todas as sentenças serem consistentes, o grafo tem que ser não-direcionado e o estado dos vértices
ligados por uma aresta têm que ser consistente com o estado da aresta, isto é, têm que ser iguais, se o estado da aresta
for “V”, ou diferentes, se o estado da aresta for “F”.
Como, para completar o grafo, deve-se preencher os vértices com seus estados, isto é, com “V” ou “F”, pode-se
tratar o problema como a coloração do grafo com as “cores” V ou F. Neste caso, o nosso problema de achar o maior
número de frases verdadeiras, torna – se achar a maior quantidade de vértices que possuem a cor V.
Para isso, nota-se que cada componente conexo do grafo é independente. Assim, após pintar um componente por
inteiro, pode-se inverter as cores de todos os vértices a fim de deixar a componente na configuração de máximos
vértices na cor V.
Portanto, comentado todos os passos, pode-se descrever a solução da questão da seguinte maneira:
1 – Montar o grafo cujos vértices são os números de 1 a N.
2 – Traçar as arestas de acordo com o estado da afirmação que relaciona as sentenças. Se existir duas sentenças
relacionando os mesmos vértices com afirmações diferentes, o documento é inconsistente.
3 – Executar um algoritmo de busca no grafo para percorrer cada componente conexo. Enquanto percorre cada
componente, pinta – se os vértices de tal forma que as sentenças fiquem consistentes. Caso não exista uma configuração
que vá de acordo com a consistência das frases, o documento será inconsistente. Escolhe – se a configuração com o
maior número de vértices com a cor V.
4 – Caso o documento seja consistente, calcula a maior quantidade de vértices com a cor V. Caso contrário, apenas
imprimi que o documento é inconsistente.
Para o algoritmo de busca do passo 3, pode ser usado o algoritmo BFS (Breadth First Search – busca em largura
em inglês) que determina o menor caminho de uma origem a um dado vértice em um grafo não ponderado. Esse
algoritmo possui O(V^2) se o grafo for implementado na estrutura de matriz de adjacência.
3. Situação 2
Nome original: Overlaying Maps
Origem: ACM - Asia - Dhaka - 2004/2005
Site: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3013 acessado em 08/2007
3.1. Descrição
Na figura 3, pode-se observar dois retângulos ABCD e A1B1C1D1 que representam mapas de escalas diferentes de
AD
uma mesma área retangular, isto é, AB A B
A D .
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
y
D1
D
C
Ponto E denota a mesma localização geográfica
nos dois mapas.
C1
A1
B1
A
B
x
Figura 3 – Retângulos que representam mapas de uma mesma área retangular
De acordo com os matemáticos, sempre existirá um ponto que representa a mesma locação geográfica nos dois
mapas. Dados a orientação de dois mapas de uma mesma área retangular, a tarefa é achar este ponto especial.
Assume – se que o ponto A encontra – se na origem e os lados do maior mapa são paralelos aos eixos x e y.
3.2. Comentário
Para este problema, pode-se pensar em uma fórmula geométrica que calcula exatamente a localização do ponto
especial. Mas, na solução proposta, usa-se a técnica de iterações.
3.3. Solução
Pelos dados do problema, tem-se os dois primeiros retângulos que são mapas de uma mesma área retangular.
Pela descrição do problema, se houvesse um terceiro retângulo A2B2C2D2 dentro do segundo, representando a
mesma área retangular, iria existir um ponto especial tal como descrito anteriormente. Se a proporção entre o retângulo
A2B2C2D2 e A1B1C1D1 for igual à proporção entre os retângulos A1B1C1D1 e ABCD, e se a posição relativa entre os
mesmos pares de retângulos forem iguais, o ponto especial relacionado aos pares de retângulos A2B2C2D2 e A1B1C1D1
será o mesmo ponto relacionado com os pares A1B1C1D1 e ABCD.
y
D1
D
C
D2
A2
C1
E
A1
C2
B2
A
B1
B
x
Figura 4 – Figura que mostra o retângulo A2B2C2D2, criado após a primeira iteração
Esse raciocínio pode ser utilizado diversas vezes. A cada iteração, pode-se relacionar os dois últimos
retângulos e criar um novo que possui o mesmo ponto especial. Assim, existirão vários retângulos e apenas um ponto
que representa a mesma posição geográfica em todos eles.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
y
D1
D
C
C1
A1
A
B1
B
x
Figura 5 – Vários retângulos criados a partir de iterações sucessivas
Nota-se que, a cada iteração, diminui-se o tamanho do novo retângulo. Então, para achar qual o ponto especial,
itera-se diversas vezes até que o retângulo criado seja tão pequeno que os quatro pontos que o definem sejam
praticamente iguais. Assim, a solução do problema será qualquer um dos quatro pontos do último retângulo gerado.
4. Situação 3
Nome original: Back to the Future
Origem: X Maratona de Programação dos Alunos da USP - 2006
Site: http://www.ime.usp.br/~cef/Xmaratona/problems/prova.pdf acessado em 08/2007
4.1. Descrição
Um grupo de amigos precisa fazer uma viagem aérea gastando a menor quantidade possível de dinheiro.
Analisando as rotas aéreas disponíveis, perceberam que, em todas as rotas, o número de assentos disponíveis nos aviões
era sempre o mesmo, a rota entre duas cidades sempre existia nos dois sentidos e cada rota poderia ser utilizada apenas
uma vez.
Dados as cidades pertencentes às rotas aéreas, a quantidade de amigos no grupo, a capacidade das rotas, o
custo unitário da passagem aérea, e as cidades de origem e destino, a tarefa é , caso seja possível, calcular a menor
quantidade possível de dinheiro que os amigos vão gastar para realizar a viagem.
4.2. Comentário
Pela formulação deste problema, pode-se pensar em um simples algoritmo guloso para a solução: enquanto
ainda existir amigos que não viajaram, calcular o trecho que possui o menor custo da cidade de origem à cidade destino
e embarcar a maior quantidade possível de amigos nesse trecho.
Pelo exemplo abaixo, em que os vértices são as cidades e as arestas representam as rotas ponderadas
por seus custos unitários, nota-se que este pensamento não nos dá uma solução válida:
Capacidade das rotas: 10
Quantidade de amigos: 15
Figura 6 – Exemplo em que o pensamento guloso nos dá uma resposta errada
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
Utilizando o pensamento guloso, seria impossível transportar os 20 amigos da cidade origem à cidade destino,
pois, primeiramente, transporta-se 10 amigos no trecho com um custo de 11(trecho de custo menor possível) e depois
não existiriam trechos disponíveis para transportar os outros 5 amigos que sobraram.
Para este exemplo, o menor custo de transportar os 15 amigos possui um total valor de 225 (15 * 10 + 15 * 5) .
Em uma solução válida, modela-se o problema usando a teoria de fluxo em redes e usa-se o algoritmo
“minimum cost flow” para concluir a tarefa.
4.3. Solução
O algoritmo “minimum cost flow” calcula o custo mínimo de mandar uma especificada quantidade de fluxo de
certo destino a certa origem em um grafo de fluxo em rede. Então, para obter a solução, basta modelar o problema de
modo que se possa utilizar tal algoritmo.
Na modelagem, considera-se o número de amigos a serem transportados como sendo a quantidade especificada
de fluxo. As cidades serão os vértices e as rotas serão as arestas do grafo de fluxo em rede. O custo e a capacidade de
cada aresta serão, respectivamente, o preço da passagem e a capacidade de cada rota.
Portanto, definindo por V o conjunto dos vértices e E o conjunto das arestas tem-se um fluxo em rede G =
(V,E) que satisfaz as seguintes propriedades:
- Restrição de capacidade: Para todo ,
, tem-se
,
, , em que
, representa o fluxo
que passa pela aresta que liga o vértice ao vértice e
, representa a capacidade dessa aresta.
- Anti-simetria oblíqua: todo ,
,
, =
, .
- Conservação do fluxo: Sendo o vértice de origem e o vértice destino, para todo
, tem-se
∑
,
0 , isto é, fluxo não é acumulado no vértice .
Para o algoritmo do “minimum cost flow”, utiliza-se o algoritmo “Ford-Fulkerson” modificado em que os
caminhos aumentantes são encontrados utilizando o algoritmo “Bellman-Ford” para encontrar o menor caminho entre a
origem e o destino em termos de custo.
Em termos de pseudo – código, a implementação do algoritmo fica:
FORD-FULKERSON-MODIFICADO(G,s,t,d)
Inicializar fluxo f com 0
enquanto (existir caminho aumentante p em termos de custo e o fluxo total f ≤ quantidade d de fluxo
requerida) faça
ampliar fluxo f ao longo de p
retorna f
Assim, utilizando o algoritmo em nosso fluxo em rede já modelado, tem-se a solução do problema.
5. Situação 4
Nome original: Fill
Origem: Bulgarian National Olympiad in Informatics 2003
Site: http://acm.uva.es/p/v106/10603.html acessado em 08/2007
5.1. Descrição
Existem 3 jarros de volumes a,b e c (inteiros positivos não maiores que 200). Inicialmente, os dois primeiros jarros
encontram-se vazios e o terceiro encontra-se completamente cheio de água. É permitido passar água de um jarro a outro
até que ou primeiro esvazie ou o segundo torne-se cheio.
Sua tarefa é escrever um programa que calcula a menor quantidade total de água que precisa ser movimentada para
que, no mínimo, um dos jarros tenha uma quantidade d(d é um inteiro positivo não maior que 200) de litros. Se não for
possível medir d litros desta maneira, seu programa deve encontrar a maior quantidade de litros d’ < d que pode ser
produzida e calcular a menor quantidade de litros movimentada pra produzir tal montante em, no mínimo, um dos
jarros.
5.2. Comentário
Em uma primeira abordagem, pode-se usar uma técnica chamada backtracking para simular todas as
movimentações possíveis. Neste processo, pode-se chegar em uma mesma configuração dos três jarros por
movimentações diferentes. Logo, teria-se que simular todas as movimentações possíveis, transformando nossa solução
em um algoritmo não-polinomial.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
A solução proposta baseia-se na teoria de grafos. Usa-se um algoritmo de achar o menor caminho entre
vértices para que a tarefa seja concluida.
5.3. Solução
No grafo, consideram-se as possíveis configurações simultâneas dos 3 jarros como sendo o conjunto de
vértices e as movimentações necessárias para passar de uma configuração para outra como sendo o conjunto de arestas.
Nota-se que, pelas regras de movimentação estabelecidas pelo problema, cada vértice no grafo possuirá, no
mínimo, ou um jarro vazio ou um jarro cheio e o volume inicial de líquido se conserva. Estes fatos fazem com que o
número de configurações simultâneas possíveis fique bastante reduzido, tornando assim o grafo bastante reduzido.
Assim, sendo a,b e c respectivamente os volumes totais dos três jarros, na configuração inicial, tem-se:
Capacidade: a
Capacidade: b
Capacidade: c
Vol. utilizado: 0
Vol. utilizado: 0
Vol. utilizado: c
Jarro 1
Jarro 2
Jarro 3
Figura 7 – Configuração inicial dos jarros.
Depois de gerar o grafo, a tarefa consiste em achar o menor caminho entre os vértices inicial e qualquer vértice
que, em sua configuração, possua um dos jarros com capacidade d.
Para exemplificar, suponha os números 5,7 e 10 como sendo, respectivamente, a capacidade dos 3 jarros e a
quantidade requerida d é 2. Assim, uma parte do grafo seria da forma:
Figura 8 – Grafo relativo às configurações válidas.
Neste exemplo, ao utilizar o Dijkstra, um algoritmo que calcula o caminho de menor custo em um grafo
ponderado com valores não negativos, entre o vértice inicial(de configuração 0 – 0 – 10) e o vértice mais próximo que
contém o número d na configuração(no nosso caso, vértice 5 – 2 – 3), será calculado um valor de 12 como menor
caminho, que é o resultado correto.
Caso todo o grafo seja percorrido e não seja encontrado um vértice com o número d em sua configuração, escolhese o vértice com o maior número d’ < d em sua configuração e o resultado será o menor caminho entre este vértice e o
vértice inicial (valor já calculado).
Portanto, comentado todos os passos, pode-se descrever a solução da questão da seguinte maneira:
1 – Montar o grafo descrito anteriormente.
2 – Usar o algoritmo de Dijkstra para encontrar o menor caminho entre o vértice inicial e o primeiro vértice que
possuir o número d em sua configuração.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
3 – Caso o algoritmo percorra todo o grafo e não encontre tal vértice, encontrar um novo vértice com configuração
que possua o maior número d’ < d e considerar como resposta o menor caminho entre o este vértice e o vértice
inicial(valor já calculado pelo passo 2).
O algoritmo de Dijkstra, implementado com uma matriz de adjacência possui, uma ordem de execução de O(V^2).
Em termos de pseudo – código, tem-se:
DIJKSTRA(G,w,s) {
para cada vértice v ∈ a V faça
d[v]
∞
π[v] nulo
d[v] 0
enquanto Q
0
u
extraia min Q
S
S
u
para cada vértice v adjacente a u faça
se d[v] > d[u] + w(u,v)
então d[v] d[u] + w(u,v)
π[v] u
}
Nesta implementação d[v] é o vetor de distâncias de s até cada v, [v] identifica o vértice de onde se origina uma
conexão até v de maneira a formar um caminho mínimo, S é um conjunto que representa todos os vértices v cujos
caminhos mínimos desde s até já foram calculados e Q é um conjunto que contém todos os outros vértices, isto é, Q = V
– S.
6. Situação 5
Nome original: Trigran
Origem: Aquecimento para a XI Maratona de Programação dos Alunos da USP – 2007
Site: http://www.ime.usp.br/~cef/XImaratona/tar/prova.pdf acessado em 08/2007
6.1. Descrição
O dono de uma fábrica de brinquedos decide criar um quebra-cabeça que utiliza apenas peças triangulares.
Para a fabricação do jogo, uma peça de madeira, que possui a figura convexa a ser montada, é mandada a uma
marcenaria para que sejam feitos os cortes.
Sabendo que a marcenaria cobra pela quantidade total de madeira cortada, sua tarefa é criar um programa para
o dono da fábrica de modo que, dado uma peça inicial (N pontos), determine como ela deve ser cortada em triângulos
de forma a minimizar o custo de fabricação da peça.
6.2. Comentário
Para a solução deste problema, utiliza-se a técnica de programação dinâmica, uma abordagem muito aplicada
em algoritmos de otimização que se baseia nas idéias de subestruturas ótimas, isto é, uma solução ótima para o
problema contém em seu interior soluções ótimas para subproblemas.
6.3. Solução
Para resolver uma situação usando a técnica de programação dinâmica, deve-se encontrar a subestrutura ótima
e depois usá – la para construir uma solução ótima para o problema a partir de soluções ótimas para subproblemas.
Neste problema, tem-se, como entrada, um polígono convexo de N pontos (P1P2P3...PN) e deve-se calcular
uma triangularização de tal forma que a soma das diagonais seja mínima.
Avaliando a seqüência de pontos PiPi+1...Pj, onde i j, nota-se que qualquer triangularização ótima para o
polígono convexo formado por esses pontos deve dividi – lo em dois poligonos convexos PiPi+1...Pk-1Pk e PiPkPk+1...Pj
,para algum i 1 k
, que possuem uma triangularizações ótimas. Esse fato ocorre pois, caso contrário, tem-se
uma situação melhor de triangularizar o polígono inicial, indo de encontro a nossa suposição. A figura abaixo ilustra
essas observações:
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
Pj
Pi
Pi+1
Pk+1
Pk-1
Pk
Figura 9 – Divisão ótima de um polígono convexo com os vértices PiPi+1...Pj
Outro importante fato é que, caso a aresta PiPj não coincida com a aresta P1PN, isto é, caso i
1ej
N, essa
aresta não existe e deve-se adiciona – la na quantidade total da triangularização do polígono PiPi+1...Pj para que todas as
diagonais sejam contabilizadas corretamente.
Então, considerando m[i,j] como a soma mínima das diagonais do polígono formados pelos pontos PiPi+1...Pj,
tem-se:
m i, j
0,
0,
min
1
,
,
,
Em que
d i, j
0,
1
0,
2
distância cartesiana entre os ponto P e P
Com a implementação destas duas funções, resolve-se a tarefa requerida. Pela definição, a solução será m[1,N]. A
ordem de execução deste algoritmo é da ordem de O(N^3).
Em pseudo-código, tem-se:
d(inteiros i,j){
se i=1 e j=N
então retorna 0
se j - i<2
então retorna 0
retorna distância cartesiana entre os pontos Pi e Pj
}
TRIGRAN(pontos p) {
para i=1 até i=N faça
m[i,i] = 0
para i=1 até i=N-1 faça
m[i,i+1] = 0
para h=2 até h=N-1 faça
para i=1 até i=N-h faça
j i+h
para k=i+1 até k=j-1 faça
m[i,j] = minimo(m[i,k]+m[k,j]+d(i,j))
}
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
7. Conclusão
Ao longo da iniciação científica, um estudo generalista em relação às áreas de computação foi produzido. Não
focamos em apenas um tipo de resolução de problemas, e sim, focamos em estudar as mais diversas áreas possíveis.
Deste modo, criamos uma habilidade de modelagem que nos permite utilizar diversas técnicas para um mesmo
problema. Procuramos produzir esse fato neste relatório final. Abordagens diferenciadas foram utilizadas para a solução
de 5 problemas.
Esta habilidade é de grande valia no ramo da computação. Assim, os conhecimentos adquiridos neste projeto
servirão de base para estudos futuros e para a solução de problemas em campeonatos de computação.
8. Agradecimentos
Aos meus pais, por tudo.
Aos meu amigos Helder Suzuki e Henry Hsu, pelas lições em computação.
Ao Prof. Nei Yoshihiro Soma, pela orientação e dedicação neste trabalho de iniciação centifica.
Ao Prof. Armando Gouveia, pelo apoio.
Ao amigo Humberto Naves, pelos conhecimentos passados.
Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) pelo Programa Institucional de
Bolsas de Iniciação Cientifica(PIBIC), do qual participei na condição de bolsista.
9. Referências
[1] CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L., STEIN, C., ALGORITMOS – Tradução da 2º edição
americana – Teoria e Prática, Editora CAMPUS, Rio de Janeiro, 2002.
[2] JUNGNICKEL, D., Graphs, Networks and Algorithms. Ed. Springer, New York, 1999.
[3] Universidad de Valladolid – Problem Set Archive. Disponível em <http://amc.uva.es/p>. Acesso em agosto
de 2007.
[4] XI Maratona de programação dos alunos da USP. Disponível em <http://www.ime.usp.br/~cef/XImaratona>.
Acesso em agosto de 2007.