Eu quero saber se sò devo fazer uma análise de que o algoritmo é certo ou também devo fazer uma análise de complexidade?
Obrigado!
Acredito que as duas coisas.
Olá,
Eu estava dando uma revisada nas tarefas e acabei por notar algo que achei um tanto estranho.Na "Solução do João Pedro" existe o conceito de indução em r, com r sendo um número racional. Como funciona a indução nesse caso?
Eu estava dando uma revisada nas tarefas e acabei por notar algo que achei um tanto estranho.Na "Solução do João Pedro" existe o conceito de indução em r, com r sendo um número racional. Como funciona a indução nesse caso?
Funciona como qualquer outra indução.
Mas é aí que você vê as limitações
da "indução mirim" que a gente aprende
no colégio (aquela que "vai de n para n+1").
Mas é aí que você vê as limitações
da "indução mirim" que a gente aprende
no colégio (aquela que "vai de n para n+1").
Ainda não comprei o peixe. Os números racionais não são bem ordenados...
Humm...
Para qualquer racional r >= 2,
a sequência r,r/2,r/4,r/8,...
acaba caindo no intervalo (1/2, 1],
onde é fácil demonstrar a validade da proposição.
Isso não funciona?
Para qualquer racional r >= 2,
a sequência r,r/2,r/4,r/8,...
acaba caindo no intervalo (1/2, 1],
onde é fácil demonstrar a validade da proposição.
Isso não funciona?
Acho que a confusão desaparece se explicitarmos os intervalos 'i1', 'i2' ... 'in' que aparecem na prova e fazer a indução em cima desse n depois. Certo?
Pode ser. Mas acho que isso introduz
complicações desnecessárias.
Acho mais fácil imaginar que você tem
uma família infinita de recorrências,
cada qual com origem num número racional
no intervalo que serve de base da recorrência.
complicações desnecessárias.
Acho mais fácil imaginar que você tem
uma família infinita de recorrências,
cada qual com origem num número racional
no intervalo que serve de base da recorrência.