Oferta Nacional - 234x60

Arquivo

Arquivo da Categoria ‘Ciência da computação’

Problema ‘mochila’ por programação dinâmica

Como resolver o problema ‘mochila’ usando programação dinâmica.

Parte da disciplina Algoritmos e Estruturas de Dados 2, do curso de Ciência da Computação, da UERJ.

O Problema:

Dada uma mochila com capacidade M e t ítens com peso w[i] cada, verificar se existe uma combinação de itens que preencha exatamente a mochila.

Exemplo:

Dado o conjunto de ítens {7, 3, 5, 9, 15}, é possível preencher exatamente mochilas com capacidades 25 e 27, mas não é possível preencher mochila com capacidade 26.

Implementação em HTML e Javascript, animado, no link: http://www.idealmind.com.br/exemplos/mochila.html?w=4,7,11,5,17&d=0&m=37.

Posts Relacionados:

  • Nenhum

Cálculo das probabilidades

Todas as vezes que se estudam fenômeos de observação, cumpre-se distinguir o próprio fenômeno e o modelo matemático que melhor o explique.

Os fenômenos estudados pela Estatística são fenômenos cujos resultados, mesmo em condições normais de experimentação variam de uma observação para outra.

Para a explicação desses fenômenos – fenômenos aleatórios – adota-se um modelo matemático probabilístico. Nesse caso, o modelo utilizado será o CÁLCULO DAS PROBABILIDADES.

3.1 – Experimento aleatório

Todo experimento que, repetido em condições idênticas, pode apresentar diferente resultados, recebe o nome de experimento aleatório. A variabilidade de resultados deve-se ao acaso.

A fim de se entender melhor a caracterização desses experimentos, convém observar o que há de comum nos seguntes experimentos:

E1: Retirar uma carta de um baralho de 52 cartas e observar o seu naipe.
E2: Jogar uma moeda 10 vezes e observar o número de coroas obtidas.
E3: Retirar com ou sem reposição, bolas de uma urna que contém 5 bolas brancas e seis pretas.
E4: Jogar um dado e observar o número mostrado na face de cima.
E5: Contar o número de peças defeituosas da produção diária da máquina A.

A análise desses experimentos revela:

a) Cada experimento poderá ser repetido indefinidamente sob as mesmas condições.
b) Não se conhece um particular valor do evento “a priori”, porém, pode-se descrever todos os possíveis resultados – as possibilidades.
c) Quando um experimento for repetido um grande número de vezes surgirá uma regularidade, isto é, haverá uma estabilidade da fração f = r/n (frequência relativa) onde n é o numero de repetições, e r o número de sucessos obtidos.

3.2 – Espaço Amostral

Para cada experimento aleatório E, define-se espaço amostral o conjunto de todos os resultados possíveis desse experimento.

Consideremos um experimento aleatório. O conjunto de todos os possíveis resultados desse experimento é chamado espaço amostral e indicado por Ω (letra grega Ômega).

Indicaremos o número de elementos de uma espaço amostral por n(Ω).

Exemplo 1
a) E = Jogar um dado e observar o número mostrado na face de cima: Ω = {1,2,3,4,5,6}
b) E = Jogar duas moedas e observar os resultados: Ω = {(C,C), (C,K), (K,C), (K,K)} onde C = cara e K = coroa.

Exemplo 2
Lançamos uma moeda honesta e observamos a face voltada para cima: Ω = {K,C}, onde C = cara e K = coroa. => n(Ω) = 2.

Exemplo 3
Uma urna contém 5 bolas vermelhas e 4 brancas. Duas bolas são retiradas, ao acaso, sucessivamente e sem reposição. Observamos a sequência das cores das bolsa sorteadas.
O espaço amostral é dado por Ω = {(V,V), (V,B), (B,V), (B,B)} => n(Ω) = 4. Cada par é um dos postos do espaço amostral Ω.

3.3 – Evento

Evento é um conjunto de resultados do experimento, em termos de conjuntos, é um subconjunto de Ω. Em particular, Ω e Ø (conjunto vazio) são eventos. Ω é dito o evento certo e Ø o evento impossível.

Usando as operações em conjunto, podemos formar novos eventos:

A ∪ B – é o evento que ocorre se A ocorre ou B ocorre ou ambos ocorrem.
A ∩ B – é o evento que ocorre se A e B ocorrem.
Ā – é o evento que ocorre se A não ocorre.

Exemplo 1
Seja o experimento E: jogar três moedas e observar os resultados: Ω = {(c,c,c), (c,c,k), (c,k,c), (k,c,c), (k,k,k), (k,k,c), (k,c,k), (c,k,k)}
Sejam os eventos

E1: ocorrer pelo menos duas caras. Então, E1 = {(c,c,c),(c,c,k), (c,k,c), (k,c,c)}
E2: lançar um dado e observar o número de cima. Então, E2 = Ω = {1, 2, 3, 4, 5, 6} é um evento certo.
E3: ocorrência de número maior que 8.
E3 = Ø é um evento impossível.
E4: ocorrer múltiplo de 2. Então E4 = {2, 4, 6}; observe que E4 ⊂ Ω.
E5: ocorrer número ímpar. Então E5 = {1, 3, 5}; observe que E5 ⊂ Ω.

3.4 – Probabilidade de um Evento

Agora podemos quantificar o grau de confiança de qualquer evento.
Atribuímos a cada evento um número obtido da soma das imagens de cada um de seus elementos na relação de freqüência.

Exemplo
O experimento consiste em extrair uma bola do interior de uma caixa e observar sua cor. Há um total de nove bolas na caixa: duas brancas, três vermelhas e quatro pretas. Qual será a probabilidade de tirar uma bola que não seja preta?

O espaço amostral é: Ω = {vermelha, branca, preta} ou {V, B, P}
O evento “tirar uma bola de cor diferente do preto”, A = {B,V}, consta de dois elementos.

Temos as seguintes relações de frequência, ou probabilidade, para cada cor:
(B) branca = 2/9
(V) vermelha = 3/9
(P) preta = 4/9

Então a probabilidade do evento A, indicado por p(A) é:

p(A) = p(B) + p(V) = 2/9 + 3/9 = 5/9

Em alguns experimentos aleatórios, cada um dos resultados (eventos elementares) tem a mesma freqüência relativa esperada.
Este é o caso de lançar uma moeda ou um dado e comprovar o resultado. Dizemos, então que o espaço amostral é equiprovável, e que sua probabilidade é uniforme.

Related Posts Plugin for WordPress, Blogger...

Posts Relacionados:

  • Nenhum
Categories: Ciência da computação Tags:
SEO Powered by Platinum SEO from Techblissonline