Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Problema do Segmento de Soma Máxima

No description
by

Fábio Michiura

on 4 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Problema do Segmento de Soma Máxima

Acadêmicos: Fábio Kioshi Michiura R.A.: FCT1305786CIC
Fernando da Silva Poisler R.A.: FCT1305220CIC
João Edezio M. Rocha R.A.: FCT1305239CIC
João Vítor A. Ribeiro R.A.: FCT1305093CIC Segmento de Soma Máxima Referências Bibliográficas Aplicação do algoritmo de segmento de soma máxima em monitoramento de áreas Aplicação do algoritmo de segmento de soma máxima em monitoramento de áreas Aplicação do algoritmo de segmento de soma máxima em monitoramento de áreas Problema de Segmento de Soma Máxima Docente: Prof. Dr. Danilo Medeiros Eler
Turma: Ciência da Computação - 2o. Ano Aplicações de Segmento de Soma Máxima na Bioinformática O que é a Bioinformática ? É a área responsável pelo armazenamento, processamento, análise, modelação de informação biológica a diversos níveis com a ajuda das ciências e tecnologias da computação e tem como objetivo comparar sequências de DNA ou proteínas, produzindo o melhor alinhamento, caractere a caractere, entre duas sequências e determinando sua similaridade. Bioinformática - Funcionamento e Objetivos A Bioinformática tem como finalidade utilizar uma sequência de caracteres (DNA, RNA ou proteína), realizar a soma e verificar na Base de Dados se está ou não alinhada. Seu principal objetivo é comparar sequências de DNA, RNA ou proteínas, produzindo o melhor alinhamento, caractere a caractere, entre duas sequências e determinando sua similaridade. Aplicações envolvendo o Problema do Segmento de Soma Máxima Algoritmos Simulação do algoritmo de Força Bruta Programação Dinâmica Força Bruta Bioinformática - Funcionamento e Objetivos A verificação da similaridade entre as cadeias de caracteres podem ter diversas finalidades, como desenvolver a partir de uma dada sequência genética, vacinas para determinados tipos de vírus, verificar doenças genéticas hereditárias, estudo da eficiência de certas proteínas no organismo, verificar semelhança na relação entre espécies, entre várias outras aplicações. Árvore Filogenética de Relação entre as espécies Fonte: http://www.amnh.org A seguir, mostraremos a Árvore de Relação entre espécies, que como definimos, tudo o que existe, existe uma sequência genética que representa em qual natureza e a Taxonomia em que representam. ROCHA, Miguel, Seminário de Bioinformática, Disponível em: <http://wiki.di.uminho.pt/twiki/pub/Education/MICEI/MatPedSem/seminario-05-19.pdf>, Acesso em: 18/11/2012. Aplicação do algoritmo de segmento de soma máxima em monitoramento de áreas O monitoramento de área consiste em detectar certas atividades para que possa assegurar a segurança do lugar. Nos exemplos a seguir será mostrado como o algoritmo de segmento de soma máxima pode contribuir a maximizar o monitoramento de forma dinâmica e automática. A função do algoritmo consiste em receber informações de outros sensores e assim calcular se o nível de atividade de uma certa área é alto e se precisa de mais sensores monitorando. Este exemplo consiste em monitoramento de uma sala, com câmeras que detectam atividade visual e sonora. Na imagem as câmeras detectam o deslocamento de três alvos. O algoritmo de segmento de soma máxima irá coletar a informação de atividade de cada sensor, calcular o nível e assim decidir se é necessário uma câmera ser apontada para o mesmo alvo. Este exemplo é sobre o monitoramento de veículos em certas áreas de uma cidade. Os sensores usam basicamente o mesmo sistema do exemplo anterior, com a diferença que os sensores vão se distribuindo automaticamente pelos pontos onde o algoritmo julga ser necessário o monitoramento. A vantagem é que com esse sistema os sensores podem ser instalados de modo aleatório que o algoritmo vai garantir uma boa distribuição dos sensores. A. Waldock, D. Nicholson, A. Rogers, Advanced Technology Centre, BAE SYSTEMS, Disponível em: <http://eprints.soton.ac.uk/265456/1/cooperative_contol.pdf>, Acesso em: 17/11/2012. F. Alessandro, J. Nicholas, A. Rogers, Advanced Technology Centre, BAE SYSTEMS, Disponível em: <http://eprints.soton.ac.uk/265456/1/cooperative_contol.pdf>, Acesso em: 17/11/2012. Perguntas ??? Fonte: http://www.encontrasp.com.br/grajau/servicos/seguranca/simotec.html Segmento de Soma Máxima Definição: Um segmento de um vetor A[p..r ] e qualquer subvetor da forma A[i..k ],
com p <= i <= k <= r. A condição i <= r garante que o segmento não é vazio. A
soma de um segmento A[i..k ] é a soma de todos os números entre os índices
entre i e k ou seja é o numero A[i ] + A[i + i] + ... + A[k]. A soma de um segmento de soma máxima é a solidez de um vetor A [p..r ]. Sua solidez é igual a 36 e segmento de soma máximo igual a [0..7]. Segmento de Soma Máxima Outro Exemplo: Sendo o segmento de soma máximo [2..4] e a solidez do vetor sendo igual a 35. Michael Shamos professor da universidade de Carnegie-Mellon Estatístico Joseph Born Kadane
(Jay Kadane) Importantes desenvolvedores do algoritmo para
resolução do problema Por ser um típico problema de combinação, podemos inferir 3 idéias básicas necessárias para se encontrar o subsegmento de soma máxima de um conjunto de números inicial:

1. Devemos necessariamente percorrer todas as posições do vetor inicial para analisar a combinação de todos os números, pois um subsegmento pode se iniar em qualquer posição do vetor;

2. Como o tamanho do vetor inicial é maior do que 1 (para que haja combinações), podemos ir variando o tamanho de cada subsegmento analizado;

3. É preciso computar as somas dos elementos contidos em cada subsegmento de tamanho corrente (variável em cada iteração) e verificar se é maior do que a maior soma que temos atualmente. Testar todas as possíveis combinações de somas entre subsegmentos, variando tanto o comprimento quanto o início de cada subsegmento. * Fácil de implementar * Algoritmo mais natural * Repetição de chamadas * Garante a solução * Desperdício de processamento Idéia: * Menor gasto de memória Evitar recálculos de chamadas já efetuadas, aproveitando os resultados computados através do armazenamento em uma tabela (matriz) de valores. * Mais eficiente * Menor gasto de processamento * Maior gasto com memória * Algoritmo menos natural * Mais difícil de implementar Idéia: Simulação do algoritmo de Programação Dinâmica Subestruturas (relações) Ótima: Não-ótima: Algoritmo de Kadane Idéia: Usar os conceitos dos algoritmos de Força Bruta e Programação dinâmica em conjunto. Baseado no fato de que os vetores devem possuir números negativos e positivos para funcionar, "reseta" a soma atual caso o resultado da adição com o elemento atual seja negativa. Em nossa pesquisa, concluímos que é o algoritmo mais eficiente atualmente para resolver o problema.
Full transcript