Exercício 4.3-1 Cormen

[Igor Medeiros]

Pessoal, gostaria de discutir uma "solução" que encontrei para o exercício abaixo, do livro do cormen

4.3-1 Mostrar que a solução de T(n) = T(n-1) + n é O(n²)

eu fiz o seguinte

H.I. 

T(k) <= ck² para k < n

Passo:

T(n) = T(n-1) + n

     <= c(n-1)² + n

     = c( n² -2n + 1 ) + n

     = cn² -2cn + c + n

     = cn² - (2c - 1)n + c

     <= cn² quando -(2c-1)n + c <= 0

o que acontece quando c >= 1

Não sei se é bem isso porque eu faltei as duas aulas que abordaram resolução de recorrência por indução, então gostaria que alguém comentasse algo pra ver se estou no caminho certo.

obrigado.

[João Paulo Pereira Zanetti]

Numa olhada rápida, parece ser isso mesmo, até porque na verdade essa
recorrência é a soma dos n primeiros inteiros. Só faltou a base da
indução. E nesse caso você não precisaria usar a indução forte, mas
não tem problema, na maioria das recorrências você usa.

[Igor Medeiros]

obrigado joão. E o que seria essa indução forte?

Em 25/03/12, João Paulo Pereira Zanetti<jppza...@gmail.com> escreveu:

[Carla Négri]

Está certo a resolução sim.

E uma indução forte seria o caso de você, ao invés de supor T(n) <= cn², supor algo do tipo T(n) <= cn² + b, onde b é constante.
Um exercício que precisa realmente da indução forte é o 4.3-7.
Esse 4.3-1 não precisa mesmo dela..

--
Carla Négri Lintzmayer (@carlanegri)
Mestranda em Ciência da Computação pela Universidade Estadual de Campinas
Bacharel em Ciência da Computação pela Universidade Estadual de Maringá

"Política é para o presente, mas uma equação é para a eternidade." (Albert Einstein)

[Igor Medeiros]

obrigado carla.

[Igor Medeiros]

tenho mais uma dúvida sobre esse assunto

T(n) >= 2( c |_ n/2  _| lg |_ n/2 _| ) + n

eu posso jogar fora os pisos??? e dizer

T(n) >= 2( c( n/2 )log( n/2 ) ) + n   ???

porque num dos exemplos o professor joga fora os pisos mas ele aumenta o divisor. e nesse caso eu deixei o mesmo divisor de n

Obrigado

[Pedro Mesquita Moura]

Se estiver usando no método da arvore, você pode assumir que n é uma potência de 2 e desconsiderar os pisos e tetos, mas depois você tem que provar que a recorrência vale para todos os inteiros usando outro método como indução.

--
Atenciosamente,
Pedro Mesquita Moura

[Igor Medeiros]

mas me refiro no caso da indução mesmo. porque eu achei uma solução para um problema mas não sei se está correta porque eu joguei fora os pisos

provar que T(n) = 2T( |_ n/2 _| ) + n é ômega(n log n)

T(n) = 2T( |_ n/2 _| ) + n

      >= 2( c |_ n/2 _| log |_ n/2 _| ) + n

      >= 2( c( n/2 ) log( n/2) ) + n               *aumentar o divisor aqui ou não???    T(n)  >= 2( c( n/4 ) log( n/4 ) ) + n

      >= 2( c( n/2 )( log n - log2 )  ) + n

      >= 2( c( n/2 )log n - 2c( n/2 ) ) + n

      >= cn log n - 2cn + n

      >= cn log n, se -2cn + n >= 0

Mas se eu aumentar o divisor, as contas não batem.

[Igor Medeiros]

ou talvez eu deva usar indução forte nessa questão. não sei.

[L.]

oi igor,

em sua caso, voce tem dois pisos

onde cumple
c(n/2) >= c |_ n/2  _|, certo??

então, só em este caso voce pode,

como consequença de desigualdade

em geral

a gente não pode fazer esso!!!

a gente tem que provar desigualdade..


abraços


Rommel

2012/3/25 Igor Medeiros <igorosb...@gmail.com>

--
"No debe haber barreras para la libertad de preguntar. No hay sitio
para el dogma en la ciencia. El cienti­fico es libre y debe ser libre
para hacer cualquier pregunta, para dudar de cualquier aseveracion,
para buscar cualquier evidencia, para corregir cualquier error"
(Oppenheimer)

[Igor Medeiros]

ok rommel, vi que tem erro de conta no meu desenvolvimento log2 = 1  

rs mas isso nao muda muita coisa. e também acho que não dá pra dizer que

T(n) >= cn log n, se -cn + n >= 0 

[L.]

complementando,

T(n) >= 2( c |_ n/2  _| lg |_ n/2 _| ) + n   ...... (a)


temos

c(n/2) >= c |_ n/2  _|    .... 1
c(n/2) >= c |_ n/2  _|    .....2

nos multiplicamos  1 x 2

c(n/2) * c(n/2) >= c |_ n/2  _| * |_ n/2  _| .... 3


3  em  (a)

mais diretamente no pode

tem que fazer algum artifiço matematico


Voce que quere provar??

Ate

Rommel

2012/3/25 L. <lro...@gmail.com>

[Igor Medeiros]

Eu quero provar que T(n) = 2T( |_ n/2 _| ) + n é ômega(n)

[Carla Négri]

Quando você estiver com

T(n) >= 2( c |_ n/2  _| lg |_ n/2 _| ) + n

você tem que achar algo menor que essa expressão para retirar o piso e manter o sinal " >= "
Como |_ n/2 _| >= n/4 sempre, vc pode trocar por isso (você poderia trocar por n/5, n/8...), e vai ficar 
T(n) >= 2( c |_ n/2  _| lg |_ n/2 _| ) + n >= 2( c n/4 lg(n/4) ) + n

Quando você estiver com

T(n) <= 2( c |_ n/2  _| lg |_ n/2 _| ) + n

aí você troca por algo maior para manter o " <= "
No caso, |_ n/2 _| <= n/2 (também poderia trocar pelo próprio n, n-1...) sempre, então fica
T(n) <= 2( c |_ n/2  _| lg |_ n/2 _| ) + n <= 2( c n/2 lg n/2) + n

O importante é manter o <= ou o >=

[Igor Medeiros]

Alguém conseguiu resolver a questão 4.3-3 do livro do cormen?

tentei de tudo e não consegui =\

[João Paulo Pereira Zanetti]

On Sun, Mar 25, 2012 at 2:53 PM, Igor Medeiros <igorosb...@gmail.com> wrote:
> Alguém conseguiu resolver a questão 4.3-3 do livro do cormen?
>
> tentei de tudo e não consegui =\

Qual é essa questão? Estou só com a segunda edição aqui e os
exercícios são diferentes.

[Igor Medeiros]

Eu estou com a terceira edição.

O exercício é

4.3-3 mostrar por indução que T(n) = 2T|_ n/2 _| + n é O(n lgn)

[Igor Medeiros]

errei no email anterior.

Eu estou com a terceira edição.

O exercício é

4.3-3 mostrar por indução que T(n) = 2T|_ n/2 _| + n é OMEGA(n lgn)

[Ricardo Correa]

http://www.csee.umbc.edu/~nam1/TA/HWSols/hw2sol.pdf

Esta descrito como 4.1-2, deve ser baseado em outra edição. Bom, não tenho certeza se esta correto, mas era neste caminho que eu estava indo tb.
Só não ficou muito claro ainda quando eu posso simplesmente retirar o piso (ou teto) e quando eu tenho que mudar o valor, tipo aumentado o denominador.
Será que eu posso simplesmente dizer que estou considerando um n par ?

Abs,
Ricardo.

2012/3/25 Igor Medeiros <igorosb...@gmail.com>

[atilio gomes]

Oi Ricardo,

Acho que essa solução não está correta. Observe que da primeira para a segunda linha ele usou uma afirmaçao falsa, ele disse que:

|_n/2_| >= n/2

O que é falso para n ímpar.

Se supormos que estamos trabalhando apenas com n par isso seria correto, mas a questão
não fala nada sobre a possibilidade de fazer essa suposição.

T (n) ≥ 2c⌊n/2⌋ lg(⌊n/2⌋) + n      ---- linha 1
        ≥ cn lg(n/2) + n               ---- linha 2 (errado)

Tentei varias coisas aqui, mas ainda não consegui resolver essa por indução.
Atilio.

[Igor Medeiros]

obrigado ricardo

[Ricardo Correa]

Oi Atilio,

Entendi o que vc esta falando, então este não é o caso de aumentar o denominador para um numero maior que 2 (por exemplo 4) e assim garantir que |_n/2_| > n/2 ?
Voce tentou desta forma ?

Obrigado,
Ricardo

2012/3/25 Igor Medeiros <igorosb...@gmail.com>

[atilio gomes]

Oi Ricardo, tentei dessa forma também, mas não conseguir provar a hipótese de indução.
Mas estava aqui pensando: será que teria problema se supossemos n sendo par? Acho que não.

[Igor Medeiros]

Em 25 de março de 2012 17:46, atilio gomes <gomes....@gmail.com> escreveu:

Oi Ricardo, tentei dessa forma também, mas não conseguir provar a hipótese de indução.
Mas estava aqui pensando: será que teria problema se supossemos n sendo par? Acho que não.

No caso da indução não podemos supor que n é par ( ou multiplo de 2 ). A prova por indução tem o objetivo de provar pra qualquer n



 

[Ricardo Correa]

Não é assim?

T(n/4) = c*n/4*Lg(n/4)

T(n) >= 2 T(|_n/2_|) + n
T(n) >= 2 T(n/4) + n  (com o denominador menor, garantimos a inequação)
T(n) >= 2(c*n/4*lg(n/4)) + n
T(n) >= (cn)/2(lgn - lg4) + n
T(n) >= ((c*n)/2) lgn) - cn + n
 É verdade p/ c/2 <= 1 ou seja é valido para c <=2

2012/3/25 Igor Medeiros <igorosb...@gmail.com>

[Carla Négri]

Só ficou errado na parte final Ricardo..

T(n) >= ((c*n)/2) lgn) - cn + n (ainda não acabou aqui)
Você tem que deixar isso só com a cara T(n) >= cn lgn

Então desenvolvendo aquela expressão sua ali:
((c*n)/2) lgn) - cn + n = cn lgn - (cn/2) lgn - cn + n e isso é >= cn lgn se
- (cn/2) lgn - cn + n  >= 0
E isolando o c, eu fiquei com a expressão c <= 2 / (lgn + 2)
E esse está sendo o meu problema.. não consigo fixar um valor de c para isso..
Não consigo ver o que está dando errado mais =(

[L.]

provar que T(n) = 2T( |_ n/2 _| ) + n é ômega(n log n)

ok

T(n)>=c n log(n) ... e lo que queremos provar (A)

Caso base,  e trivial

1 >= 2C ,  c<= 1/2

Partimos de (n/2) para provar (A)

HI:  T(n)>=c n log(n)

a gente tem o recurrença T(n) = 2T( |_ n/2 _| ) + n

recurrença em  (HI)

T(n) > =  2 c ( |_ n/2 _| ) log( |_ n/2 _| ) + n    ..... (B)

de aqui deberia dar para provar


T(n) > =  2 c ( |_ n/2 _| ) log( |_ n/2 _| ) + n >= c n log(n)

agora   |_ n/2 _| >= ( n - 1 ) / 2  .....(C)

(C) em (B)

T(n) > =  2 c ( ( n - 1 ) / 2 ) log( |_ n/2 _| ) + n    ..... (D)
 
tambem   |_ n/2 _| >= n/4  .......(E)

(E) em (D)

T(n) > =  2 c ( ( n - 1 ) / 2 ) log(  n/4 ) + n   .....(F)

Operando

T(n) >= c (n - 1) log(  n/4 ) + n

T(n) >= cn log(  n/4 ) - c log(  n/4 ) + n  .... (G)

tambem   log(  n/4 ) = log n  - 2   .... (H)

(H) em (G)

T(n) >= cn log n - 2 cn - c log (   n/4 ) + n >= cn log n  ... (Z)

Debe cumplirse

- 2 cn - c log (   n/4 ) + n  >= 0

n ( 1 - 2c ) >= c log (n /4)  ....  (I)

sabemos

n >= log(n) >= log (n /4)   for all   n>1  ....(J)

De (J) é (I)

1 - 2 c > = c

c < = 1 /3 .... isto prova que é posivle , (Z) é certo



Espero suos observaçoes


Obrigado

Rommel



 

2012/3/25 L. <lro...@gmail.com>

[Carla Négri]

Hmmmm boa saída...
O problema é que a gente estava confundindo, tentando substituir |_ n/2 _| pela mesma coisa..
Muito bem lembrado isso =)

Em 25 de março de 2012 20:10, L. <lro...@gmail.com> escreveu:

provar que T(n) = 2T( |_ n/2 _| ) + n é ômega(n log n)

ok

T(n)>=c n log(n) ... e lo que queremos provar (A)

Caso base,  e trivial

1 >= 2C ,  c<= 1/2

Partimos de (n/2) para provar (A)

HI:  T(n)>=c n log(n)

a gente tem o recurrença T(n) = 2T( |_ n/2 _| ) + n

E) em (

[Greice Mariano]

Boa noite Pessoal,

Eu acompanhei a discussão sobre exercício e fiquei com uma dúvida, tanto nas aulas quanto no livro Cormem, para esta mesma recorrência, ele ignora o piso, e simplifica a expressão, seguindo essa ideia, fiz assim:

Caso base: T(1) >= c n log(n)  = c (1) log(1) = 0, o que torna a sentença verdadeira.

HI: T(k) >= c k log(k), k < n

Passo:

T(n) >= 2T( |_ n/2 _| ) + n

      >= 2. (c( |_ n/2 _|) log(|_ n/2 _|) ) + n

      >= cn*log(|_ n/2 _|) + n

      >= cn*log(n) - cn*log2 + n

      >= cn*log(n) - cn + n, 

onde -cn + n >= 0, 

o que me dá que c <= 1

Dessa forma fica errado? Fico em dúvida como e quando considerar o piso e o teto, ou quando devo simplesmente ignorá-los.

Agradeço a ajuda.

Greice

--

Greice Mariano

 

[Carla Négri]

Boa noite Greice,
Desta forma fica errado, pois você baseia sua prova numa "mentira".
O problema é que |_ n/2 _| não é maior ou igual a n/2  para todo n (faz n = 3 por exemplo)
Então se você for ignorar piso ou teto, já diz logo no começo "essa prova só vale para múltiplos de 2"
Mas se quiser provar para todos os n possíveis, tem que usar o piso e ir "dando um jeitinho" de trocar os pisos por algo menor ou maior, dependendo do que vc está tentando provar.

[Jhonatan Raphael]

Para quem estava com dúvida sobre pisos e tetos em provas por indução.

Perguntei isso para o professor em aula, se podemos desconsiderar pisos e tetos em uma prova por indução (a dúvida veio pois toda prova por indução é 'exata'). Ele disse que podemos mas que devemos tomar cuidado em provas exatas devidos aos casos base (o que acho correto). Acho que não fiz a pergunta corretamente, deveria ter dito no passo da indução.

O fato é que podemos desconsiderar pisos e tetos no passo da indução. Sabemos que no final das contas que fatores constantes não têm relevância nos limites assintóticos. Na pag. 91 da terceira edição do Cormen tem um exemplo dele desconsiderando (argumenta tal fato nas páginas anteriores). Já nos casos bases, devemos considerar os pisos e tetos, pois estes podem ser modificados.

Outro fato importante desses pisos e tetos é em relação ao método da árvore. Depende se o exercício pede para provar um limite assintótico de forma exata ou não.

Só pra deixar claro =)

--

Att.

Jhonatan Ríchard Raphael

Bacharel em Ciência da Computação - UEMS
Mestrando em Ciência da Computação - UNICAMP

[Leandro]

Oi, pessoal. Boa noite!

Fiquei com uma dúvida em relação à solução do Rommel:
Queremos provar que T(n)>=c.n.log(n)

Aplicando a hipótese à recorrência, tem-se:

T(n) > = 2 c ( |_ n/2 _| ) log( |_ n/2 _| ) + n ..... (B)

Rommel, no passo C, você considerou |_n/2_| >= (n-1)/2, o que está correto.
No entanto, como queremos provar B, temos que substituir os valores
de |_n/2_| por valores maiores que ele, certo? Afinal, se for válido
para um valor maior que |_n/2_|, será válido para |_n/2_| também. Você
substituiu |_n/2_| por um valor menor que ele. Se T(n) for maior ou
igual a todo o lado direito da equação B para um valor menor que
|_n/2_|, não há garantia que será para |_n/2_|.

Meu raciocínio está errado?
Não deveríamos substituir |_n/2_| por {(n/2)+1), por exemplo?

Abraços.

Em 25 de março de 2012 21:27, Carla Négri <carla...@gmail.com> escreveu:

--
Prof. Leandro Luque
FATEC-Mogi das Cruzes
Universidade de Mogi das Cruzes

[Leandro]

Meu raciocínio está errado. É justamente o contrário...

[L.]

eu pense esto
|_ n/2 _| + |_ n/2 _| + 1 >= n

>>>> agora   |_ n/2 _| >= ( n - 1 ) / 2  .....(C)

eu penso que esta correto,  observaçoes?


Rommel

2012/3/25 Leandro <leandr...@gmail.com>

[Leandro]

Você está certo Rommel.
Confundi-me com os pisos e tetos e inverti as coisas.
Seu raciocínio está perfeito.

[Greice Mariano]

Então Carla ainda tenho uma dúvida: para essa prova eu entendi que não se procura um número maior que |_n/2_|, mas algo equivalente que possa substituí-lo mantendo a desigualdade, e segundo o Cormen, e até as próprias aulas do professor, ele pode ser ignorado, e confesso que isso me confundiu.

Mas vou tentar fazer da outra forma, como você colocou.

Obrigada,

Greice

Em 25 de março de 2012 21:27, Carla Négri <carla...@gmail.com> escreveu:

--

Greice Mariano

 

[L.]

Obrigado,

Eu penso que exito de demostraçao, é por fazer

um factor  (n - cte)  perto al logaritmo

é logaritmo entre cte  é  destruido com  log(n)  -  cte

eu penso que alli esta o centro de demostração


abraços

Rommel

2012/3/25 Leandro <leandr...@gmail.com>

[Thiago S. A.]

Olá Rommel,

no passo H, vc fez:

 log(  n/4 ) = log n  - 2  

mas o passo Z (quando vc faz a substituição) não deveria ser: 

T(n) >=cn lg(n-2) - clg(n/4) +n ?

[L.]

Oi,

 log(  n/4 ) = log n  - 2 

é

 log(  n/4 ) = log(n)  - log(4) 


e

T(n) >= cn log n - 2 cn - c log (   n/4 ) + n >= cn log n  ... (Z)

Debe cumplirse

- 2 cn - c log (   n/4 ) + n  >= 0

isto sae de desigualdade

( c n log n )     - 2 cn - c log (  n/4 ) + n >=    ( c n log n )  + 0

onde  

( c n log n )  é  eliminado



abraços


Rommel

2012/3/25 Thiago S. A. <thiag...@gmail.com>

[Igor Medeiros]

uma dúvida, vou reescrever a prova do rommel pra deixar as coisas mais enxutas

T(n) = 2T( |_ n/2 _| ) + n

       >= 2( c |_ n/2 _| lg |_ n/2 _|  ) + n

       >= 2( c ( (n-1)/2 ) lg ( n/4 )  ) + n

       = c( n-1 ) lg( n/4 ) + n

       = cn lg( n/4 ) - c lg( n/4 ) + n

       = cn lgn -2cn -c lg( n/4 ) + n

       

aqui concluimos que

T(n) >= cn lgn -2cn -clg( n/4 ) + n

      = cn lgn + n( 1 -2c ) - clg( n/4 )

      >= cn lgn, se n( 1-2c ) >= clg( n/4 )

     

n( 1-2c ) >= nc  //aqui o rommel trocou lg (n/4) por uma coisa maior, 

                        //ou seja, por n. eu acho que isso não assegura a desigualdade

1-2c >= c

1 >= 3c

1/3  >= c

pessoal, por favor vejam se meu questionamento é coerente. eu posso estar me equivocando em algum lugar.

igor

[L.]

Oi igor,

voce esta certo...!

mais

e suficiente
que    1-2c > 0     e   c > 0

lo que da  c<1/2

c < 1/3  tambien cumple

y era suficiente para la prueba


obrigado

Rommel

n ( 1 - 2c ) >= c log (n /4)  ....  (I)

n >= log(n) >= log (n /4)   for all   n>1  ....(J)

De (J) é (I)

1 - 2 c > = c

c < = 1 /3 .... isto prova que é posivle , (Z) é certo

mais (I) não precisa de  (J) 

2012/3/26 Igor Medeiros <igorosb...@gmail.com>

[Sigrid Ortiz]

Disculpa voce nao tem o analisis da perguntinha problema 2-1 do cormen pelo amor de Deus me ayude

[L.]

qual versao do cormem?

--
Você recebeu essa mensagem porque está inscrito no grupo "Algorítmos-1s-2012" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para algoritmos-1s-2...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.