MAC5711 - Análise de Algoritmos

Qual a matéria da prova do dia 22? Cai programação dinâmica?
Algum outro conselho que queira dar sobre a prova?

Oi,
estava fazendo o 2.7 dos opcionais e fiquei com duas dúvidas.
1) O enunciado diz que x é um numero real diferente de 1, mas pelo que temos que mostrar, o certo não seria dizer que |x| < 1?
2) Neste tipo de problema, podemos resolver por indução? Como não encontrei a base, achei que não poderia...

Ola a todos,

Gostaria de sugerir que tenhamos a aula extra na quinta-feira próxima, no horário da aula mesmo. A idéia é discutirmos os exercícios da lista opcional que mais encontramos dificuldade ou não conseguimos resolver. Isso é interessante pois todos teremos que estudar para a prova e, nada melhor que seguir esta lista.

Sugestões e/ou comentários são bem vindos.

Professor Paulo, tudo bem com relação ao dia/horário e assunto?

[]'s

Durante a aula de hoje discutimos o desempenho de melhor caso do Heapsort. O Tales e outros alunos (cujos nomes infelizmente não guardei) encontraram o seguinte artigo relacionado ao assunto:

  Bollobás, Fenner, Frize,
  "On the Best Case of Heapsort",
  Journal of Algorithms 20, pp.205-217,
  ano 1996.

O artigo é muito interessante e mostra que o vetor constante (todos os elementos iguais) é, essencialmente, a única família de instâncias em que o desempenho do Heapsort é O(n). Conforme o artigo, se nos restringirmos a vetores cujos elementos são dois a dois distintos, o Heapsort consome tempo Omega(n lg n).

(A propósito, o primeiro autor é "da pesada". Ele já esteve algumas vezes aqui na USP e foi o orientador do professor Yoshiharu. O terceiro autor também é "da pesada"; esteve aqui num workshop em 2005. Não conheço o segundo autor, mas provavelmente ele também é bamba.)

Apesar da prova me parecer um tanto complexa, achei um artigo onde dizem que, apezar de afirmado por alguns autores de que a complexidade do heapsort no melhor caso é O( n ), na verdade ela é O( n lg n ). O artigo cita uma bibliografia onde é demonstrado que a complexidade é O( n ), mas é citado que isto não está correto. Mas não prova essa afirmação.

Seria valido colocar tal demonstração para a solução do exercicio 9.3 (citando, é claro, a fonte)?

Pesquisando sobre algoritmos de ordenação nos oráculos (Google, Wikipédia), acabei me deparando com o Introsort ("Introspective Sort"). Trata-se de uma tentativa de se evitar o "azar" do pior caso do QUICKSORT, para isso definindo que se a recursão atinge uma certa profundidade, o algoritmo "troca" para o HEAPSORT.

Achei a proposta interessante, portanto coloco aqui os links para o algoritmo:

Wikipédia: http://en.wikipedia.org/wiki/Introsort

Artigo: http://www.cs.rpi.edu/~musser/gp/introsort.ps

Gostaria de convidá-los para formar um grupo de estudos para discussão das tarefas obrigatórias e exercícios opcionais às quartas e sextas às 15h30 na sala B-165 (sala de estudos da pós do 1º andar do Bloco B).


Obs.: Se a sala estiver ocupada com outra atividade fazemos uma mudança de local

Infelizmente errei o enunciado de um dos exercícios da tarefa 9 :-(

Troquei o exercício por outro (mais simples).

Lamento...

Já tenho a tarefa 8 corrigida.

O Alexandre Garcia de Oliveira pediu que eu enviasse a seguinte mensagem ao fórum:

"Segue o endereço do qual eu falei das video-aulas Professor Charles Leiserson do MIT de Análise de Algoritmos:

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/index.htm

Foi muito útil para mim, para acompanhar a turma sem ir as quintas."