Tetris - Java

MESTRADO INTEGRADO EM ENGENHARIA INFORMÁTICA E COMPUTAÇÃO | 2º ANO
EIC0110 | CONCEPÇÃO E ANÁLISE DE ALGORITMOS | 2012-2013 – 2º SEMESTRE

Exame Época Normal

Prova com consulta. Duração: 2h00m.

Nome do estudante: ........................................................................................... Nº ...................
Informação aos estudantes: A consulta permitida inclui slides das aulas teóricas, livros e outros materiais impressos. Não serão permitidas folhas manuscritas avulsas de qualquer tipo ou acesso à Internet (Tablets, portáteis, etc.) Telemóveis deverão permanecer DESLIGADOS durante a duração do exame. Responder as questões 1 e 2, 3 e 4, 5 e 6 em folhas separadas.

1. [4 Valores] Suponha que está a planear uma longa viagem. Ao longo do caminho existem n hotéis aos quilómetros a1 < a2 < ... < an (ai corresponde, portanto, à distância desde o inicio da viagem, de a0). Quando pretender parar para passar a noite, terá de o fazer, obrigatoriamente num destes hotéis (mas pode escolher em que hotéis pernoitar). É obrigatório parar no último hotel, pois este é o seu destino final. Foi decidido que a distância ideal para viajar diariamente é, sensivelmente, 300 Km. Logo, se x for o número de quilómetros que se viajou num dia, assume-se que a função de custo a minimizar é (300 – x)2.
a) [1.5 valores] Elabore e descreva uma solução gananciosa, de tempo linear, para a escolha de quais os hotéis a pernoitar. Indique qual a complexidade temporal da sua solução.
b) [1.5 valores] Sendo a fórmula de recorrência que minimiza a função de custo:

Escreva um algoritmo (em pseudo-código) que, utilizando programação dinâmica, permita obter a solução ótima para este problema.
c) [1 valores] Analise o algoritmo quanto à sua complexidade temporal e espacial.

2. [3 Valores] Atente ao seguinte grafo não-dirigido, e determine qual o caminho mais curto entre os nós a e g, indicando qual o algoritmo que utilizou e mostrando todos os passos