Lista 1 - Linguagens de Programação 2022-2

Lista 1 de Algoritmos 1 - 2022.2 Prof. Vinicius Fernandes dos Santos Instru¸c˜oes: 1. Em quest˜oes envolvendo algoritmos, a complexidade do algoritmo deve ser t˜ao boa quanto poss´ıvel; 2. A menos que o enunciado diga o contr´ario, ´e permitido o uso de algoritmos vistos em sala como “caixa preta”, mas caso o algoritmo seja alterado, ´e necess´ario reescrevˆe-lo com a devida altera¸c˜ao; 3. Os algoritmos podem ser feitos em pseudo-c´odigo ou em C/C++; 4. A entrega da lista dever´a ser feita na semana posterior `a prova, conforme instru¸c˜oes a serem dadas. 1. Nesta quest˜ao, estamos interessados em determinar se um grafo ´e conexo. Para isso faremos algoritmos que recebem um grafo e retornam 1 se o grafo ´e conexo e 0 caso contr´ario. (a) Escreva um algoritmo para resolver este problema baseado em Busca em Largura; (b) Escreva um algoritmo para resolver este problema baseado em Busca em Profundidade; (c) Escreva um algoritmo para resolver este problema baseado no Dijkstra; 2. Um grafo ´e bipartido se seus v´ertices podem ser particionados em dois conjuntos X e Y de forma que toda aresta conecte um v´ertice de X a um v´ertice de Y . Equivalentemente, um grafo ´e bipartido se seus v´ertices podem ser particionados em dois conjuntos X e Y de forma que n˜ao haja arestas entre dois v´ertices de um mesmo conjunto. (a) Note que se um grafo ´e conexo, existem apenas duas maneiras de se particionar o grafo. Explique porque este ´e o caso. (b) Se o grafo possui k componentes conexas, de quantas maneiras podemos particionar o grafo? (c) Escreva um algoritmo para determinar se um grafo ´e bipartido. Em caso afirmativo, o algoritmo deve encontrar uma parti¸c˜ao v´alida e imprimir os elementos de X. O algoritmo pode encontrar qualquer parti¸c˜ao v´alida. 3. A vers˜ao do algoritmo de Dijkstra mais eficiente vista em sala tem complexidade O((m+n) log n). Quando m = Θ(n2), esta complexidade se torna O(n2 log n). Entretanto, sem a utiliza¸c˜ao de listas de prioridade, ´e poss´ıvel implementar o algoritmo de forma que ele possa ser executado em tempo O(n2). Escreva a vers˜ao de tempo O(n2) do algoritmo de Dijkstra. 4. Seja G um grafo direcionado ac´ıclico e sem loops, com v´ertices {1, . . . , n}. (a) Se n = 3 e ⟨1, 2, 3⟩ ´e uma ordena¸c˜ao topol´ogica de G, qual o maior n´umero poss´ıvel de arestas que G pode ter? (b) Se n = 5 e ⟨1, 2, 3, 4, 5⟩ e ⟨5, 4, 3, 2, 1⟩ s˜ao ordena¸c˜oes topol´ogicas de G, qual o maior n´umero poss´ıvel de arestas que G pode ter? (c) Se n = 5 e ⟨1, 2, 3, 4, 5⟩ e ⟨3, 1, 4, 5, 2⟩ s˜ao ordena¸c˜oes topol´ogicas de G, qual o maior n´umero poss´ıvel de arestas que G pode ter? 5. Explique como o Algoritmo de Floyd-Warshall pode ser utilizado para detectar a existˆencia de um ciclo negativo em um grafo direcionado. Escreva um algoritmo para reconstruir tal ciclo. 6. Seja G um grafo n˜ao direcionado com pesos nas aretas. Assuma que os pesos pertencem ao conjunto {1, . . . , 10}. Explique como o problema da ´Arvore Geradora M´ınima pode ser resolvido em tempo O(n+m). 7. Uma ideia comum para se tentar resolver caminho m´ınimo em grafos com pesos positivos e negativos ´e somar uma constante grande em todos os pesos, tornando-os todos positivos. (a) Explique porque esta estrat´egia n˜ao funciona. Forne¸ca um exemplo ilustrando sua explica¸c˜ao. (b) Se usarmos a mesma estrat´egia em uma instˆancia de ´Arvore Geradora M´ınima, ela funcionaria? Isto ´e o conjunto de arestas encontrado ap´os somarmos tal constante seria, de fato, uma ´arvore geradora m´ınima do grafo original? 8. O problema de fluxo visto em sala era apenas para grafos direcionados e com capacidades nas arestas. (a) ´E poss´ıvel resolver o problema de fluxo em grafos n˜ao direcionados. Explique como e porquˆe. (b) ´E poss´ıvel resolver o problema de fluxo com capacidades nos v´ertices (e n˜ao nas arestas). Explique como.