Outros problemas NP-completos

Questões-guia:

1. Mostre que CIRCUIT-SAT ≤_P SAT.  Dica: coloque nomes de variáveis para os fios também, além das entradas.
2. Mostre que SAT ≤_P 3-CNF-SAT.  Dica: a partir de uma árvore sintática para a fórmula, dê nomes de variáveis aos nós internos da árvore, construa cláusulas para cada nó interno, transforme cada cláusula em ≤3-CNF, depois em 3-CNF.
3. Mostre que 3-CNF-SAT ≤_P CLIQUE.  Dica: construa um vértice para cada literal de cada cláusula e ligue literais consistentes em cláusulas distintas.  A fórmula será satisfatível se e somente se o grafo tiver uma clique de tamanho n/3, onde n é o número total de vértices.
4. Mostre que CLIQUE ≤_P VERTEX-COVER.  Dica: use STABLE-SET como intermediário.
5. Mostre que 3-CNF-SAT ≤_P 3-COLOR.  Dica: veja Problema 34-3 do Cormen.

Exercícios:

1. Exercício 34.4-1 do Cormen.
2. Exercício 34.4-2 do Cormen.
3. Exercício 34.4-5 do Cormen.
4. Exercício 34.5-6 do Cormen.

Primeiro problema NP-completo

Questões-guia:

1. Que tipos de portas lógicas podem ser usadas em instâncias de CIRCUIT-SAT?
2. Em CIRCUIT-SAT, um único fio pode ligar quantas entradas e quantas saídas de portas lógicas?
3. O que é o fan-out de um fio?  E o fan-in?
4. Se representarmos cada porta lógica de uma instância de CIRCUIT-SAT por um vértice, e colocarmos um arco de p₁ a p₂ sempre que a saída de p₁ estiver ligada à entrada de p₂, qual propriedade este grafo orientado deverá ter?  Quantos vértices de grau de saída 0 este grafo poderá ter?
5. Com relação a instâncias de CIRCUIT-SAT, defina atribuição de valores-verdade, atribuição satisfatória e circuito satisfatível.
6. Defina a linguagem CIRCUIT-SAT.
7. Como se define o tamanho de uma instância de CIRCUIT-SAT?
8. Quais são as 6 partes que formam a configuração de uma máquina no modelo de computação utilizado por Cormen para algoritmos de verificação? Quais destas partes mudam ao longo da execução do algoritmo?  Quais não mudam?
9. O circuito construido a partir de um algoritmo verificador A para uma linguagem L tem quantas cópias do circuito M que implementa a execução de 1 instrução da máquina do modelo?  Qual o tamanho de M em função do tamanho n da entrada e da função T que é um limite superior de tempo para A?

Exercícios:

1. Exercício 34.3-1 do Cormen.
2. Discussão sobre o exercício 34.3-8 do Cormen.

Reduções

Questões-guia

1. O problema de resolver uma equação numérica de 1o. grau pode ser reduzido a resolver uma equação numérica de 2o. grau.  A fórmula de solução para equações de 2o. grau pode ser usada para resolver equações de 1o. grau?  Como?
2. Defina o que significa L₁ ≤_P L₂ para linguagens binárias L₁ e L₂.
3. O que se pode dizer de L₁ quando L₁ ≤_P L₂ e L₂ ∈ P?
4. Defina o que significa dizer que uma linguagem é NP-completa.  Como se define a classe NPC?
5. O que se pode dizer se houver uma linguagem L tal que L ∈ NPC e L ∈ P?
6. O que se pode dizer sobre NPC se P ≠ NP?
7. Defina o que significa dizer que uma linguagem é NP-difícil.
8. O que se pode dizer de L₂ quando L₁ ≤_P L₂ e L₁ ∈ NPC?

Exercícios:

1. Exercício 34.3-2 do Cormen.
2. Exercício 34.3-3 do Cormen.
3. Exercício 34.3-6 do Cormen.

Classe NP

Questões-guia:

1. Em aulas anteriores, discutimos a classe NP em termos de algoritmos não determinísticos.  Que abordagem segue o Cormen?
2. Como se define a linguagem HAM-CYCLE?  Em quanto tempo roda o algoritmo ingênuo de testar todos os possíveis ciclos?
3. O que é um algoritmo verificador para uma linguagem?
4. Como se define a classe NP?
5. Como se define a classe co-NP?  É igual à classe NP?

Exercícios:

1. Exercício 34.2-1 do Cormen (fácil).
2. Exercício 34.2-3 do Cormen.
3. Exercício 34.2-8 do Cormen (fácil).
4. Exercício 34.2-10 do Cormen (fácil).
5. Exercício 34.2-11 do Cormen.

Classe P

Questões-guia:

1. Porque problemas que podem ser resolvidos em tempo polinomial são considerados "tratáveis"?  Dê três motivos.
2. O que é um problema abstrato?
3. Para que servem codificações?
4. Defina alguns conceitos básicos da teoria de linguagens formais: alfabeto, linguagem, string vazia, linguagem vazia, operações sobre linguagens (união, intersecção, complemento, concatenação).
5. O que é o fecho de uma linguagem L, denotado por L*?
6. O que significa dizer que uma string s é aceita por um algoritmo A?  E o que é s ser rejeitada por A?
7. O que significa dizer que uma linguagem L é aceita por um algoritmo A?  E o que é L ser decidida por A?
8. O que significa dizer que uma linguagem L é aceita (decidida) por um algoritmo A em tempo polinomial?
9. Defina a classe P.

Exercícios:

1. Exercício 34.1-1 do Cormen.
2. Dê uma versão de decisão para o problema de achar uma árvore espalhada mínima num grafo não orientado ponderado.
3. Mostre que se uma linguagem L está em P, então L* também está em P.

Classes de problemas

Questões-guia:

1. Conhece-se um algoritmo polinomial para algum problema NP-completo?  Pode-se dizer que não há algoritmo polinomial para um problema NP-completo?
2. Às vezes dois problemas com enunciados semelhantes podem ser: um deles polinomial e o outro NP-completo.  Dê exemplos.
3. O que são as classes P e NP?  É verdade que P ⊆ NP?  É verdade que NP ⊆ P?
4. O que é a classe NPC?  Ela é diferente de NP?
5. Quais são os principais elementos para mostrar que um problema é NP-completo?
6. O que são problemas de decisão?  Qual sua relação com problemas de otimização?
7. O que é uma redução de um problema A para um problema B?
8. Porque precisamos de um primeiro problema NP-completo?

Exercícios:

1. Ache um problema de decisão intimamente relacionado ao problema do ciclo hamiltoniano.
2. Ache um problema de decisão intimamente relacionado ao problema de coloração de grafos.
3. O problema de saber se P=NP é um dos grandes desafios da computação contemporânea.  Qual o valor que o Instituto Clay se comprometeu a pagar ao primeiro que resolver esta questão?

Coloração de arestas

Questões-guia:

1. Como emparceirar n equipes que estejam disputando um campeonato de todos contra todos?  Quantas rodadas são necessárias?
2. Defina os seguintes termos: k-aresta-coloração, coloração própria de arestas, grafo k-aresta-colorável, índice cromático.
3. Para grafos simples G, o que pode dizer sobre a relação entre o índice cromático χ'(G) e o grau máximo Δ(G)?
4. O que é um grafo "classe 1"?  E um grafo "classe 2"?
5. A que classe pertencem os grafos bipartidos?
6. Qual a relação entre χ'(G) e Δ(G) em grafos com arestas múltiplas?
7.  O que é um grafo overfull (transbordante?)  A que classe tais grafos pertencem?
8. O que diz o Teorema de Vizing e quais os elementos principais de sua prova?  Consulte, além do livro de West, adotado nesta disiplina, um paper interessante de Misra e Gries sobre o assunto, publicado em 1990.

Exercícios:

1. Exercício 7.1.1 do West, apenas χ'(G).
2. Calcule o número de 3-aresta-colorações próprias de K_3,3.
3. Mostre um grafo G e uma escolha de emparelhamentos máximos tais que o algoritmo a seguir NÃO forneça o índice cromático de G.
   

Teorema das 4 cores

Questões-guia:

1. Porque todo grafo planar simples tem pelo menos um vértice com grau até 5?
2. Com base na questão 1, como colorir os vértices de um grafo planar usando no máximo 6 cores?
3. Como fazer para incrementar um pouco este algoritmo, através de contrações, e usar no máximo 5 cores?  Veja dicas no nosso texto auxiliar de Tarjan e colegas (1980).  Cuidado, pois há vários errinhos tipográficos neste texto.  Deve ter sido digitalizado por OCR.
4. O próximo passo seria provar que 4 cores bastam, mas isto ainda é muito difícil.  Vejamos então alguns marcos desta história:

• 1852: O que de Morgan escreveu a Hamilton nesta data?
• 1878: O que Tait provou nesta data?
• 1879: O que Kemper publicou nesta data?
• 1890: O que fez Headwood nesta data?
• 1946: Que contra-exemplo importante surgiu nesta data?
• 1968: O que Grinberg mostrou nesta data?
• 1976: O que Appel e Haken apresentaram nesta data?
• 1986: O que Appel e Haken apresentaram nesta data?
• 1996: O que Robertson, Sanders, Seymour e Thomas apresentaram nesta data?

Exercícios:

1. É verdade que sempre haverá um emparelhamento perfeito no dual de uma triangulação?
2. Ex. 7.3.14 do West.
3. Ex. 7.3.17 do West.

Planaridade

Questões-guia:

1. Como é o problema de gás-água-eletricidade?  Ele tem solução?  E se fossem 5 vizinhos querendo se conectar todos com todos?
2. O que é uma curva?  E uma curva poligonal?  O que é um desenho?  O que é um cruzamento num desenho?
3. Qual a diferença entre um grafo plano e um grafo planar?  O que é uma curva fechada?  E uma curva simples?
4. O que é um conjunto aberto?  E uma região?  O que são as faces de um grafo plano?  O que é a façe externa de um grafo plano?  Só há uma face externa num grafo plano?
5. Como se constrói o dual G* de um grafo plano G?  Dê exemplos.
6. O que é o comprimento de uma face?  A que corresponde no dual?  O que é um grafo periplanar (outerplanar)?
7. O que diz a Fórmula de Euler para grafos planos conexos?  Como se pode generalizá-la para grafos planos desconexos?
8. Um grafo simples pode ter um número quadrático de arestas, em relação ao número de vértices.  Isto pode acontecer com grafos planares simples?  Por quê?
9. O que é uma triangulação?  Quais são todos os grafos planares simples, regulares e cujo dual também é regular?  Desenhe-os no plano.  Quais deles são triangulações?

Exercícios:

1. Ex. 6.1.2 do West.
2. Ex. 6.1.14 do West.
3. Ex. 6.2.4 do West.

Coloração de vértices

Questões-guia:

1. Defina os seguintes termos: k-coloração; coloração própria; grafo k-colorável; grafo k-partido; número cromático χ(G) de um grafo G.  Dê exemplos.
2. Defina os seguintes termos: grafo k-cromático; coloração ótima; grafo k-crítico.  Dê exemplos.
3. É fácil ou difícil saber se um grafo é 2-colorável?  E 3-colorável?
4. O que é ω(G)?  Qual a relação entre ω(G) e χ(G)?
5. O grau máximo de uma grafo G é denotado por Δ(G).  Qual a relação entre Δ(G) e χ(G)?  Para quais grafos temos χ(G) = Δ(G)+1?
6. Qual é o mínimo número de arestas para um grafo com n vértices e número cromático k?  E o máximo?
7. O que é o polinômio cromático de um grafo?  Qual seria a complexidade de um algoritmo para calculá-lo com base no Teorema 5.3.6?
8. O que é um grafo cordal?  Qual a importância de grafos cordais no estudo do número cromático?

Exercícios:

1. Ex. 5.1.7 do West.
2. Ex. 5.1.29 do West.
3. Implementar MCS (algoritmo 8.1.12 do West) com LEMON.  Faça seu programa receber na linha de comando o grafo em LGF.  Aplique no grafo do exemplo 8.1.13.

Fluxos em redes

Questões-guia:

1. Problemas de fluxo máximo são estudados em certos tipos especiais de grafos chamados redes.  O que é uma rede?  O que é um fluxo numa rede?  Como se define o valor de um fluxo?
2. Cormen evita arestas antiparalelas no grafo inicial, e explica como eliminá-las.  Uma abordagem alternativa, que permite arestas antiparalelas no grafo inicial, é dada por Goldberg e Tarjan num artigo de 1988.  Quais as diferenças entre as duas abordagens?
3. O que é a rede residual?  Ela tem arestas antiparalelas?  Curiosidade: como se relacionam o fluxo máximo no grafo inicial com o fluxo máximo na rede residual?
4. O que é um caminho aumentante numa rede residual?  Como ele é usado no método de Ford-Fulkerson?
5. O que é um corte numa rede?  Como se define sua capacidade?  Qual a relação entre capacidades de cortes e valores de fluxos?
6. O que diz o teorema Max-Flow Min-Cut?  Como encontrar um corte mínimo numa rede residual sem caminho aumentante?
7. Como funciona o algoritmo de Edmonds-Karp?  Qual é sua complexidade?
8. Como se pode reduzir o problema de achar um emparelhamento máximo num grafo bipartido ao problema de fluxo máximo?  Onde entra o teorema da integralidade nesta redução?

Exercícios:

1. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.1 do Cormen.  O valor do fluxo deu igual ao do livro?  Qual foi o corte mínimo retornado pelo algoritmo?
2. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.3b do Cormen.  Como você codificou as capacidades infinitas?  Quanto deu o fluxo máximo?
3. Use um algoritmo de fluxo máximo do LEMON para achar um emparelhamento de cardinalidade máxima no grafo bipartido da Figura 26.8a do Cormen.

Caminhos mínimos

Questões-guia:

1. O que é o problema de passeios mínimos de fonte fixa num grafo orientado ponderado?
2. Vamos estudar também o problema com fonte e destino fixos?  Por quê?
3. O que é sub-estrutura ótima?  O problema de passeios mínimos tem esta propriedade?  De que forma?
4. O que ocorre se o grafo tiver ciclos negativos?  E se tiver arestas negativas, mas não ciclos negativos?  Qual a relação entre passeios mínimos e caminhos mínimos?
5. Qual é a saída típica de um algoritmo para resolver o problema de caminhos mínimos?
6. Segundo Cormen, o que são a inicialização e o relaxamento?  Por que o relaxamento tem este nome?
7. Quais as 6 propriedades fundamentais de algoritmos que usam a inicialização de Cormen e modificam as estimativas de caminhos mínimos apenas através de passos de relaxamento?
8. Faça um diagrama JSP do algoritmo de Bellman-Ford.  Tente usar não mais que 10 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?
9. Faça um diagrama JSP do algoritmo para caminhos mínimos num DAG.  Tente usar não mais que 7 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?
10. Faça um diagrama JSP do algoritmo de Dijkstra.  Tente usar não mais que 8 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?

Exercícios:

ATENÇÃO: ao testar os programas nos grafos, não construa os grafos no código.  Faça um arquivo LGF para o grafo e leia este arquivo no código.

1. Implemente Bellman-Ford em LEMON, seguindo um bom esquema JSP.  Teste com o exemplo da Figura 24.4.  A seguir, modifique o exemplo para conter um ciclo negativo, e teste novamente.
2. Implemente DAG-SHORTEST-PATHS em LEMON, seguindo um bom esquema JSP.  Teste com o exemplo da Figura 24.5.
3. LEMON já tem uma implementação de Dijsktra.  Teste com o exemplo da Figura 24.6.

Árvores geradoras mínimas

Questões-guia:

1. O que é uma árvore geradora mínima?  O que pode ser aproveitado da teoria sobre árvores geradoras mínimas se estivermos procurando uma árvore geradora máxima?
2. Como funciona o algoritmo genérico?  Como encontrar uma aresta segura?
3. Para que serve a estrutura de union-find?  Como funciona?
4. Como funciona o algoritmo de Kruskal?  Qual é sua complexidade?  Dá para pará-lo antes?  Isto modifica sua complexidade de pior caso?  Você pararia antes?
5. Para que servem heaps binários?  Como funcionam?  Que outros algoritmos os usam?
6. Como funciona o algoritmo de Prim?  Qual é sua complexidade com heaps binários?  Por que não aparece uma chamada de DECREASE-KEY nele?
7. O que poderia ser usado em lugar de heaps binários no algoritmo de Prim?  Como isto afetaria a complexidade?  Esta solução afetaria outros algoritmos, p.ex., os citados na questão 5?

Exercícios:

1. Ache uma árvore geradora mínima com o LEMON no exemplo usado no Cormen na seção 23.2.  Dica: use a função kruskal.
2. Exercício 23.1-11 do Cormen.
3. Exercício 23.2-4 do Cormen, só a primeira pergunta.
4. Exercício 23.2-5 do Cormen, só a primeira pergunta.

Emparelhamentos bipartidos

Questões-guia:

1. Quantos emparelhamentos perfeitos existem em K_n,n?
2. Para cada inteiro n ≥ 3, mostre um grafo com n vértices onde existe um emparelhanto maximal que não é máximo.  Mostre um caminho aumentante para estes emparelhamentos.
3. Qual a importância algorítmica do teorema de Hall?
4. Como coberturas por vértices podem nos ajudar a garantir que um emparelhamento é máximo?
5. Nos números α(G), α'(G), β(G), β'(G), o que significa a linha (')?  E quais destes números somam n(G)?  Em que condições?
6. O efeito do Algoritmo 3.2.1 pode ser conseguido com uma BFS ou DFS modificada?  Qual seria a complexidade deste algoritmo modificado?
7. Por que o problema de emparelhamento de peso máximo em grafos bipartidos ponderados pode ser reduzido a bipartidos completos?  E, ainda por cima, com partes do mesmo tamanho?
8. Como se generaliza a noção de cobertura por vértices em grafos bipartidos ponderados?
9. O Algoritmo Húngaro p/ resolver o problema de emparelhamento de peso máximo num grafo bipartido utiliza qual outro algoritmo como subrotina fundamental?

Exercícios:

Para entender o Algoritmo Húngaro, um bom exercício é ver as coisas acontecendo numa planilha de cálculo.  Pegue um exemplo do livro e coloque numa planilha da seguinte forma.

1. Separe uma região n × n da planilha para colocar a entrada.
2. A seguir, ao lado ou embaixo da entrada, escolha outra região n × n da planilha para codificar um emparelhamento.  Esta região terá apenas zeros e uns.
3. Numa outra região do mesmo tamanho, faça a multiplicação da região entrada pela do emparelhamento, elemento a elemento, obtendo os pesos das arestas do emparelhamento.  Faça uma célula conter o peso total deste emparelhamento.
4. Finalmente, numa outra região do mesmo tamanho, compute a matrix de excessos.  Nesta região é interessante ladear as bordas superior e esquerda com uma cobertura.  Faça uma célula conter o peso total desta cobertura.
5. Após este arranjo, o algoritmo pode ser "executado" mexendo apenas no emparelhamento e na cobertura, até que seus pesos fiquem iguais.

DFS, ordenação topológica, conexão forte

Questões-guia:

1. Qual a explicação que Cormen dá para a BFS ser single-source enquanto que a DFS é multiple-source?  Você concorda com ela?
2. Por que Cormen exemplifica BFS em grafos não orientados, e DFS em grafos orientados?  Em LEMON, dá pra rodar BFS e DFS em quais tipos de grafos?
3. Quais são as saídas mais importantes de uma DFS?
4. Por que o código da DFS é dividido em duas funções, enquanto que o da BFS fica em uma só função?
5. O que é um DAG?
6. O que é ordenação topológica e como ela pode ser resolvida por DFS?
7. O que são componentes fortemente conexas?  Como diferem das componentes conexas que vimos anteriormente?
8. Se G é um grafo orientado, o que é G^SCC?  Que propriedade interessante tem G^SCC?
9. Como obter uma ordenação topológica em G^SCC a partir de uma DFS em G?
10. Se G é um grafo orientado, o que é o grafo G^T?  Como se relacionam G^SCC e (G^T)^SCC?

Exercícios:

1. Rode uma DFS da biblioteca LEMON no grafo usado como exemplo na Figura 22.4 do Cormen.  Quantas linhas deu seu código?  Deu a mesma busca do livro?
2. Resolva o Exercício 22.4-1 com a biblioteca LEMON.  Dica: use a class DfsVisit em lugar da Dfs normal.
3. Implemente o algoritmo para componentes fortemente conexas da Seção 22.5 do Cormen usando LEMON.  Teste no grafo da Figura 22.9.  Dica: além da DfsVisit, use o adaptador de grafos que calcula G^T e controle fino de DFS com os métodos init, addSource e start.

BFS, distâncias

Questões-guia:

1. Em grafos, temos em geral dois parâmetros que medem o tamanho da entrada: V e E.  O que significa formalmente f(V,E) = O(g(V,E))?
2. Qual a diferença entre as definições de grafos em West e em Cormen?  LEMON é mais próximo de qual dos dois?
3. Quais as vantagens de desvantagens da representação por listas de adjacência, em relação a matrizes de adjacência?
4. Quais são as saídas mais importantes de uma BFS?
5. Como seria a tradução do algoritmo BFS(G,v) do Cormen (página 595) para LEMON?  O que você usaria para ENQUEUE e DEQUEUE?
6. O que é análise agregada?  Qual a complexidade de BFS em termos de V e E?
7. A árvore BFS de um grafo é única?  Se não for, dê exemplos.

Exercícios:

1. Modifique BFS para descobrir se um grafo é bipartido e, se não for, exibir um ciclo ímpar.
2. Como seria a adaptação de BFS para grafos com arestas múltiplas e laços?
3. Se fosse para imprimir um caminho mais curto de v para s, como você escreveria o algoritmo PRINT-PATH (página 601)?

Componentes conexas, bipartidos, eulerianos

Questões-guia:

1. Qual a diferença entre indução fraca e indução forte?
2. Qual a diferença entre passeio (walk), trilha (trail) e caminho (path)?  Como é o uso destes termos no Cormen?
3. Todo passeio entre u e v contém um caminho de u a v.  Contém também uma trilha? As trilhas de u a v sempre contém caminhos de u a v?
4. O que é uma componente conexa de um grafo?  Quantas componentes conexas tem um grafo conexo?
5. O que é vértice de corte?  E aresta de corte?  Uma aresta paralela pode ser de corte?
6. Um passeio fechado ímpar sempre contém um ciclo ímpar.  Um passeio fechado par sempre contém um ciclo par?
7. Qual a diferença entre união de grafos e decomposição de grafos?
8. Que propriedades deve ter um grafo para podermos desenhá-lo (vértices e arestas) sem tirar o lápis do papel e sem repetir traços?  É o mesmo que ser euleriano?
9. Para um grafo qualquer, qual o número mínimo de vezes que precisamos tirar o lápis do papel para desenhá-lo, sem repetir traços?  Expresse sua resposta em termos de parâmetros do grafo (número de vértices, graus, número de componentes conexas, etc.)
10. Qual a diferença entre máximo e maximal?  Esta diferença se aplica a números inteiros?

Exercícios:

1. Exercício 1.2.1 do West.
2. Exercício 1.2.2 do West.
3. Diagrama JSP para construir uma trilha de Euler num grafo.  Você tem duas opções aqui, uma oriunda da demostração do Teorema 1.2.26 e outra oriunda da demostração alternativa, dada no item 1.2.32, no final da página 29.  Para ajudar, veja a seguir a "primeira linha" de cada um destes diagramas:

Páginas 27 e 27:

Páginas 29 e 30:

Grafos, matrizes, isomorfismo

Questões-guia:

1. O que é um grafo?  E um grafo simples?
2. O complemento de um grafo bipartido será sempre bipartido?
3. O que se pode dizer do número cromático de um grafo k-partite?
4. Um subgrafo de um grafo conexo será sempre conexo?  Mesma questão para um grafo desconexo.
5. Como obter a matrix de adjacência A(G) a partir da matriz de incidência M(G) de um grafo sem laços?  E se o grafo tiver laços?
6. Como se relacionam as matrizes de adjacência de dois grafos isomorfos?  E as de incidência?
7. O que é um n-ciclo?  E um grafo completo?  E um biclique?  Quais são as notações para estes grafos?
8. Desenhe os seguintes grafos: triângulo, garra, pata, pipa, casa, touro, gravata-borboleta, dardo.
9. Qual a cintura do grafo de Petersen?  E de seu complemento?
10. Quais dos grafos em (8) são vértice-transitivos?  Quais tem maior número de automorfismos?

Exercícios:

1. Exercício 1.1.11 do West.
2. Exercício 1.1.15 do West.
3. Exercício 1.1.27 do West.

Lab: Apresentação

Exibir apresentação sobre LEMON.

Note que LEMON já traz vários algoritmos relacionados aos nossos tópicos de laboratório.

Apresentar ferramenta para JSP.

Ver se LEMON está instalado nos computadores do laboratório.

Praticar com alguns exercícios simples.

Revisão MC458

Questões-guia:

1. O que é um algoritmo?
2. O que é um problema computacional?
3. O que é um invariante de malha (ou de laço)? [em inglês: loop invariant]
4. Qual o modelo de computação usado no Cormen?
5. O que é o tamanho da entrada de um algoritmo?
6. Qual a diferença entre análise de caso médio e análise de pior caso?
7. O que é e para que serve uma árvore de recursão?
8. O que significa f(n) = O(g(n))?
9. O que diz e para que serve o Teorema Mestre?

Exercícios:

1. Faça o diagrama JSP para um dos seguintes algoritmos: insertion sort, merge sort, selection sort.
2. No exercício C3-3a, escolha uma linha ou uma coluna e faça o exercício só para estas funções.
3. No exercício C4-1, escolha uma das recorrências (a-g) e resolva.