A Matemática Discreta

Projete um algoritmo para encontrar os k menores elementos de um conjunto n˜ao ordenados de n inteiros em tempo O(n + klgn).

2. Projete um algoritmo eficiente para calcular a uni˜ao dos conjuntos n˜ao ordenados A e B, onde n = max(|A|,|B|). A sa´ıda deve ser um vetor de elementos distintos que formam a uni˜ao dos conjuntos. O algoritmo projetado deve ter complexidade de tempo O(nlgn).

3. Considere o conjunto num´erico X com 2n elementos. O problema proposto consiste em particionar o conjunto X em dois conjuntos A e B, onde |A| = |B| = n, de forma que maximize o valor X a∈A a−X b∈B b. Desenvolva um algoritmo guloso para esse problema. O tempo do seu algoritmo deve ser de O(nlgn).

4. Considere um conjunto de n livros, onde cada livro i, 1 ≤ i ≤ n, possui peso pi e 0 < pi ≤ 5. O problema proposto consiste em dividir os n livros no menor nu´mero poss´ıvel de envelopes de modo que cada envelope tenha no m´aximo 2 livros e o peso do conteu´do de cada envelope seja no m´aximo 5. Desenvolva um algoritmo guloso para esse problema. O tempo do seu algoritmo deve ser de O(nlgn).

5. Considere o problema de escalonar n processos com tempos de execuc¸˜ao t1,t2,··· ,tn conhecidos parar serem executados por um processador com um u´nico nu´cleo. Os processos podem ser executados em qualquer ordem, mas apenas um de cada vez. Vocˆe deseja escolher uma ordem que minimize o tempo total de espera de todos os processos. O tempo de espera de um processo ´e definido como a soma dos tempos dos processos que executam antes dele, e o tempo total de espera ´e a soma dos tempos de espera de cada processo. Desenvolva um algoritmo guloso para esse problema e demonstre que a estrat´egia gulosa usada sempre gera a soluc¸˜ao ´otima do problema.

6. Considere o trecho da BR-122 entre Quixad´a e Quixeramobim, onde as casas ao longo das margens se distribuem bem esparsamente. Os moradores dessa regi˜ao, para n˜ao ficarem fora das novidades do mundo, s˜ao ´avidos usu´arios de celulares. Uma empresa de telecomunicac¸˜oes deseja espalhar suas antenas em certos pontos ao longo dessa rodovia para atender os clientes dessa regi˜ao de forma que todos estejam a um m´aximo de 4km de alguma antena. Fornec¸a um algoritmo que, dada a quantidade n de residˆencias e as distˆancias de cada uma delas, em km, at´e o ponto inicial do trecho, determine em que os pontos devem ser instaladas as antenas de forma minimizar a quantidade necess´aria.

7. Existem n caiaquistas que precisamos distribuir em caiaques de dois lugares de forma a respeitar o peso m´aximo suportado pelo caiaques. Desejamos usar o m´ınimo de caiaques poss´ıvel. Vocˆe deve considerar que: • O peso m´aximo suportado por cada caiaque ´e K; • O caiaquista i, com 1 ≤ i ≤ n, possui um peso pi;