ANALISE E COMPLEXIDADE DE ALGORITMOS

Sumário

1 Escalonamento de Intervalo (Ex. 8)
Imagine que vários eventos querem usar certo centro de convenções. Cada evento gostaria de usar o centro durante o intervalo de tempo que começa numa data e termina numa data . Dois eventos são considerados compatíveis se os seus intervalos de tempo são disjuntos. Cada evento tem certo valor e a administração do centro precisa selecionar um conjunto de eventos mutuamente compatíveis que tenha o maior valor total possível.
1.1 Iterativo escalonaIterativo (b, e, n) y = −1 X = [ ] i = 0 para k = 1 até n faça se bk > ei então X = X ∪ [k] i = k devolva X
1.2 Recursivo escalonaRecursivo (b, e, n) se (n ≤ 1) então se (n = 0) então devolva [ ] senão devolva [1] senão L = escalonaRecursivo (b, e, n−1) i = n faça (i = i−1) até que i = 0 ou bi < en La = escalonaRecursivo (b, e, i) devolva max(L , La ∪ [n])
1.3 Programação Dinâmica
1.3.1 Recorrência e Indução do algoritmo
1.3.1.1 Análise de Complexidade

1.3.1.2 Recorrência

p/ n = 1

p/ n = n - 1

p/ n = n + 1

1.3.1.3 Indução

1.4 Teste de Mesa
Dado o intervalo:

2 As linhas de um Parágrafo (Ex. 9)
Um parágrafo de texto é uma sequência de palavras, sendo cada palavra uma sequência de caracteres. Queremos imprimir um parágrafo em uma ou mais linhas consecutivas de uma folha de papel de tal modo que cada linha tenha no máximo caracteres. As palavras do parágrafo não devem ser quebradas entre linhas e cada duas palavras consecutivas numa linha devem ser separadas por um espaço. Para que a margem direita fique razoavelmente uniforme, queremos distribuir as palavras pelas linhas de modo a minimizar a soma dos cubos dos espaços em branco que sobram no fim de todas as linhas exceto a última.
2.1 Iterativo

2.2 Recursivo

2.3 Programação Dinâmica
2.3.1 Recorrência e Indução do algoritmo
2.3.1.1 Análise de Complexidade