Trabalho Prático 03 - Investigando Técnicas de Projeto de Algoritmos Eficientes

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Trabalho Prático 03
Investigando Técnicas de Análise de Algoritmos Eficientes
Objetivo: Exercitar o projeto de algoritmos à luz da aplicabilidade de técnicas de projeto, tais como
Backtracking, Programação Dinâmica e Método Guloso
Modalidade de desenvolvimento: equipe (até 2 componentes)
Modalidade da apresentação: envio no formato .odt1 para flaviacoelho@ufersa.edu.br
Data de entrega: Domingo, 20/11/2016
Artefatos de entrega: soluções das questões, a seguir.
Atenção: Nas justificativas, apresente todos os cálculos matemáticos relacionados.
1. (1,5 pt) [Backtracking] Em 1850, Thomas Kirkman apresentou o ‘problema das 15 alunas’,
no qual 15 alunas caminham para a escola em 5 linhas de 3 em cada dia da semana. O
objetivo é organizar uma escala diária tal que cada par não caminhe junto mais do que uma
vez. Considere que as alunas são Ana, Beatriz, Carla, Diana, Eva, Francisca, Geane, Helga,
Iana, Jeane, Katia, Luiza, Maria, Najla e Olívia. Eis uma solução, a seguir.
Seg Ter Qua Qui Sex Sáb Dom
ABC ADG AEJ AFO AHK AIM ALN
DEF BEH BFL BDM BGN BKO BIJ
GHI CJM CHO CGL CFI CEN CDK
JKL FKN DIN EIK DJO DHL EGO
Para solucionar o problema, pode-se verificar todas as possibilidades, ou seja, as 15! formas
das alunas serem organizadas por dia e (15!)7 formas semanalmente.
Sendo assim, elabore um algoritmo baseado em Backtracking para solucionar o problema e
a árvore de busca exaustiva inteligente derivada. Determine também a complexidade
assintótica (pior caso) do algoritmo elaborado.
2. (1,5 pts) [Programação Dinâmica] Considere que há vários eventos que almejam utilizar o
espaço do Centro de Convenções da UFERSA durante o intervalo de tempo que começa
1 De acordo com o modelo disponível via SIGAA.
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
numa data a e termina numa data b. Dois eventos são considerados compatíveis se os seus
intervalos de tempo são disjuntos. Cada evento possui um determinado valor e a
administração do Centro de Convenções precisa selecionar um conjunto de eventos
mutuamente compatíveis que tenha o maior valor total possível.
Sejam a1, a2, ..., an e b1, b2, ..., bn números naturais tais que ai ≤ bi para cada i. Cada índice i
representa o intervalo que tem origem ai e término bi, ou seja, o conjunto {ai, ai+1, …, bi–1,
bi}. Dois intervalos distintos i e j são compatíveis se bi < aj ou bj < ai. Um conjunto de
intervalos é viável se seus elementos são compatíveis dois a dois. A cada intervalo i está
associado um número natural vi que representa o valor do intervalo. O valor de um conjunto
S de intervalos é o número v(S) = ∑
i∈S
v i . Um conjunto viável S tem valor máximo se v(S)
≥ v(S’) para todo conjunto S’ de intervalos que seja viável. Assim, pode-se definir
formalmente o problema.
Problema dos Intervalos Compatíveis de Valor Máximo: Dados números naturais a1, ..., an,
b1, ..., bn e v1, ..., vn tais que ai ≤ bi para cada i, encontrar um subconjunto viável de {1, …, n}
que tenha valor máximo.
Observa-se que o problema possui estrutura recursiva, afinal, qualquer solução de uma
instância do problema contém soluções de instâncias menores.
E mais, para simplificar a descrição do conjunto de intervalos compatíveis com n, convém
supor que os intervalos estão em ordem crescente de términos, ou seja, que b1 ≤ b2 ≤ ··· ≤ bn.
Sob esta hipótese, o conjunto dos intervalos compatíveis com n é simplesmente {1, …, j},
sendo j o maior índice tal que bj < an. Supondo X(n) o valor de um “subconjunto viável de
valor máximo” de {1, …, n}, a estrutura recursiva do problema garante que 
X(n) = max(X(n − 1), X(j) + vn} (i)
sendo j o maior índice tal que bj < an. Se tal j não existe então (i) se reduz a
X(n) = max(X(n − 1), vn}.
Essa recorrência pode ser facilmente transformada em um algoritmo recursivo. Porém, o
algoritmo é muito ineficiente, pois resolve cada subinstância repetidas vezes. Sendo assim,
elabore um algoritmo baseado em programação dinâmica que receba n intervalos, de modo
que b1 ≤ b2 ≤ ··· ≤ bn., e retorna o valor de um subconjunto viável de valor máximo de {1, …,
n}. Determine também a complexidade computacional assintótica do algoritmo proposto.
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
3. (1 pt) [Método Guloso] Fórmulas Horn são um esquema utilizado, em Computação
(especialmente, são a base da linguagem PROLOG), para expressar fatos lógicos e derivar
conclusões. O objeto mais primitivo em uma fórmula Horn é uma variável booleana,
tomando valores verdadeiro ou falso. Por exemplo, as varáveis x, y e z poderiam denotar
possibilidades, tais como 
x ≡ o assassinato aconteceu na cozinha
y ≡ o mordomo é inocente
z ≡ o coronel estava dormindo às 8 da noite
Um literal é uma variável x ou a sua negação ~x (não x). Em fórmulas Horn, o
conhecimento sobre as variáveis é representado por dois tipos de cláusulas:
i) Implicações, cujo lado esquerdo é um AND de qualquer número de literais positivos e
cujo lado direito é um único literal positivo. Isso expressa sentenças da forma “se as
condições à esquerda valem, então as da direita também têm de ser verdadeiras”. Por
exemplo, (z AND w) → u pode representar “se o coronel estava dormindo às 8h da noite e o
assassinato aconteceu às 08h da noite, então o coronel é inocente”. 
ii) Cláusulas puramente negativas, consistindo em um XOR de qualquer número de literais
negativos, como em (~u XOR ~v XOR ~y) - “eles não podem ser todos inocentes”.
Dado um conjunto de cláusulas desses 2 tipos, o objetivo é determinar se existe uma
explicação coerente: uma atribuição de verdadeiro/falso às variáveis que satisfaça todas as
cláusulas. Sendo assim, elabore um algoritmo baseado no método guloso para o problema.
Determine também a sua complexidade computacional assintótica (pior caso).
3
	Trabalho Prático 03