MAC5711 - Análise de Algoritmos

No enunciado do ex 12.4 diz
"todo elemento de S pertence a algum dos cliques da coleção"
significa que todo elemento de S pertence a apenas um dos cliques da coleção, ou a pelo menos um dos cliques da coleção?

Obrigado,
Ariel

Na aula 12, slide 124, eu criei a impressão
de que "estrutura gulosa" é o mesmo que
"todo maximal é máximo". Isso não está certo.

Se todo maximal é máximo então o problema
tem estrutura gulosa, mas a recíproca não é
verdadeira. Veja, por exemplo, o problema
da coleção disjunta máxima de intervalos.

Olá professor,

O enunciado do execício 11.1 diz que temos que montar um programa. Qual tipo de entrada e saída devemos admitir? Podemos seguir as do problema original que esta em http://online-judge.uva.es/p/v102/10261.html ?

Grato,

No exercício 11.1 vocês escreverão um algoritmo. No entanto apenas um pseudo-código não será suficiente. Na solução do exercício também deve estar claro o que é uma instância do problema, a recorrência e o significado das entradas da matriz de programação dinâmica.

Eu sei que deveria ter esclarecido isso antes, mas se você já escreveu um algoritmo não terá problemas para escrever o resto.

Publiquei as notas da prova 1.

As sentenças abaixo estão corretas?

    "O algoritmo executou."

    "O Heapsort executa em tempo O(n lg n)."

Eu acho que está faltando o objeto, não?
Quem executa, executa alguma coisa.

Eu entendo "O engenheiro executou a obra",
mas não entendo "O engenheiro executou".

Eu entendo "O pianista executou uma peça de Bach"
mas não entendo "O pianista executou".

Eu entendo "O carrasco executou o condenado"
mas não entendo "O carrasco executou".

Opiniões?

Sem discutir o restante do enunciado, é valido já fazer a prova a partir da recorrência ou eu deveria primeiro achar a formula fechada?

Ola a todos.
Gostaria de uma avaliação sobre as respostas a seguir para maior esclarecimento.

Exr 4.6) discuta a seguinte afirmação: "n é O(2^n) para n >=4"

R1: Quer dizer que n pertence a um conjunto de funções com crescimento
assintótico, em que 2^n também pertence, porém a recíproca não é verdadeira. E
Nesta afirmação o n>=4 nos dá apenas uma informação adicional, porém já embutida
em "n é O(2^n)".

-----------------------------------------------------------------------------
Exr 4.7) discuta a seguinte afirmação: "n² - n=O(n²) p/ c=2 e N=1"

R1: Quer dizer que n²-n está limitado assintóticamente por cima por n². E "Para c=2 e N=1" não se faz necessário para o entendimento de "n²-n=O(n²)"

-----------------------------------------------------------------------------
Exr 4.9) discuta a seguinte afirmação: "f não é O(g)"

R1: A afirmativa quer dizer que: "g não é um limite assintótico de f."
----------------------------------------------------------------------------

Agradeço.


Wesley

Algumas pessoas tiveram dificuldade de resolver o seguinte exercício
do caderno de exercícios opcionais (é o exercício Exr 6.13 na versão
atual do caderno):

  Considere a função T definida pela seguinte recorrência sobre os
  racionais positivos:

    T(r) = 1                            se 0 < r <= 1
    T(r) = T(r/3) + T(2r/3) + 5r  se r > 1.

Infelizmente, essa recorrência está torta (eu errei...) pois o
intervalo entre 0 e 1/3 em nada contribui para definir T e atrapalha
a solução. Faz muito mais sentido usar a seguinte definição:


  Considere a função T definida pela seguinte recorrência sobre os
  racionais maiores que 1/3:

    T(r) = 1                            se 1/3 < r <= 1
    T(r) = T(r/3) + T(2r/3) + 5r  se r > 1.


Queremos mostrar que T(r) = O(r lg(r)). Para isso, vamos mostrar que

                  T(r) < 90r lg(r) + lg(r) + 60

para todo racional r > 1/3.

Prova, por indução em r:

Como vamos precisar de lg(3), observe desde já que 1.58 < lg(3) < 1.59.
Para começar, tome um racional r tal que 1/3 < r <= 1. Então

  90 r lg(r) + lg(r) + 60 > 90 (1/3) lg(1/3) + lg(1/3) + 60
                          = -30 lg(3) - lg(3) + 60
                          = -31 lg(3) + 60
                          > -50 + 60
                          > 1
                          = T(r).

Isto conclui a base da indução. Suponha agora que r > 1. Então, por
hipótese de indução, temos

T(r) = T(r/3) + T(2r/3) + 5r

    < 90(r/3)lg(r/3) + lg(r/3) + 60 + 90(2r/3)lg(2r/3) + lg(2r/3) + 60 + 5r

    = 30r lg(r/3) + lg(r/3) + 60 + 60r lg(2r/3) + lg(2r/3) + 60 + 5r

    = 30r lg(r/3) + lg(r/3) + 60 + 60r(lg(r/3)+lg(2)) + lg(r/3)+lg(2) + 60 + 5r

    = 30r lg(r/3) + lg(r/3) + 60 + 60r lg(r/3) + 60r + lg(r/3) + 1 + 60 + 5r

    = 30r lg(r/3) + 60r lg(r/3) + lg(r/3) + 60  + 60r + lg(r/3) + 61 + 5r

    = 90r lg(r/3) + lg(r/3) + 60 + 65r + lg(r/3) + 61

    = 90r (lg(r)-lg(3)) + lg(r)-lg(3) + 60 + 65r + lg(r)-lg(3) + 61

    = 90r lg(r) + lg(r) + 60 - 90 lg(3) r + 65r + lg(r) - 2lg(3) + 61

    < 90r lg(r) + lg(r) + 60 - 142r + 65r + lg(r) - 3 + 61

    = 90r lg(r) + lg(r) + 60 - 77r + lg(r) + 58

    < 90r lg(r) + lg(r) + 60 - 77r + r + 58

    = 90r lg(r) + lg(r) + 60 - 76r + 58

    < 90r lg(r) + lg(r) + 60.

Fim da prova.

Publiquei as notas da tarefa 9.