View
395
Download
2
Embed Size (px)
DESCRIPTION
Análise de Algoritmos - Programação Dinâmica - Segmento de Soma Máxima
Citation preview
Programação DinâmicaSegmento de Soma Máxima
Gabriel RamalhoTúlio Lemes
Vinicius Rodrigues
1.1 Definição do Problema: Dado a necessidade de obtermos o segmento de um vetor com a maior soma possível, se faz necessária a utilização de algoritmos.
Podemos tomar como exemplo eventos da vida real:
● Bioinformática (produzir melhor alinhamento entre sequências de DNA, RNA ou proteínas, e determinar sua similaridade através de somas)
● Monitoramento de Áreas (calcular se é preciso mais sensores de monitoramento)
1. Motivação
Representar a soma dos elementos do segmento de soma máxima, com base no conjunto numérico determinado.
1.2 Descrição Informal:
Questão: Dado uma sequência de n números inteiros, encontre a maior soma de uma subsequência presente no conjunto.
Entrada: Um conjunto numérico.
Saída: Soma dos elementos do segmento de soma máxima encontrado.
1.3 Descrição Formal:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
1.4 Exemplo:
Obs: Se a sequência de número não possuir números negativos, o segmento de soma máxima abrangerá todos elementos.
= 175 (segmento 0 até 7)
Obs2: Caso todos elementos da sequência sejam negativos, a soma será o valor de seu elemento menos negativo.
= -5 (segmento 1)
1.4 Exemplo:
2. AlgoritmoSOLIDEZ (A, p, r)
F[p] ← A[p]para q ← p + 1 até r faça
se F[q − 1] > 0então F[q] ← F[q−1] + A[q]senão F[q] ← A[q]
x ← F[p]para q ← p + 1 até r faça
se F[q] > x então x ← F[q]devolva x
3.1 Prova de Corretude:
SOLIDEZ (A, p, r)F[p] ← A[p]para q ← p + 1 até r faça
se F[q − 1] > 0então F[q] ← F[q−1] + A[q]senão F[q] ← A[q]
x ← F[p]para q ← p + 1 até r faça
se F[q] > x então x ← F[q]devolva x
3. Análise do Algoritmo
A cada iteração do loop, F[q − 1] e a firmeza de A[p...q−1]. Logo, pode-se afirmar que F[j] e a firmeza de A[p..j].
Sendo j = p, p+1,...,q−2, q−1 pode-se afirmar que o fato de F[j] ser firmeza de A[p..j] vale para j = p, p+1,..., r.
Em seu bloco final, o algoritmo percorre todo o vetor com as firmezas das subsequências registradas até então e retorna o maior valor entre elas.
3.2 Complexidade:
● A partir do loop do algoritmo podemos perceber que o tempo consumido é proporcional ao número de elementos n := r − p + 1 do vetor. Logo, o consumo de tempo do algoritmo está em:
Θ(n)
3. Análise do Algoritmo
4. Conclusão● Melhor técnica para resolver o problema.● Não é possível obter um algoritmo melhor.
Vantagens:● Algoritmo mais eficiente para a solução do problema● Menor gasto de processamento
Desvantagens:● Mais difícil de implementar● Maior gasto com memória
Bibliografia:● http://prezi.com/i1eoqtqpjgpk/problema-do-segmento-de-soma-maxima/● http://www.ime.usp.br/~cris/aulas/11_1_338/slides/aula5.pdf● http://www.ime.usp.br/~pf/livrinho-AA/AA-BOOKLET.pdf