dojo@centro 19/12/2012 – Dojo de Natal && Último dojo de 2012

Olá, pessoas queridas.

O dojo de encerramento de 2012 e o de natal foi uma orgia alimentar com casa cheia \o/.

De panetone até biscoito de gengibre, teve de tudo. Este dojo foi um dojo especial também pela escolha do problema ter a ver com a data. Houve pessoas que pediram que o problema fosse o fim do mundo (é, pessoal, acho que o mundo não acabou no dia 21/12/2012, mas continuem tentando :P), mas o de natal ganhou mesmo

O problema foi:

Imagine que o segredo do Papai Noel não esteja na velocidade em que ele trabalha para atender as crianças do mundo inteiro, mas no fato de que ele pode duplicar seu trenó em qualquer ponto da viagem para atender outras crianças simultaneamente.

Mas se fosse só isso, ele poderia criar tantos trenós quantas crianças existem e entregar no menor tempo possível. O problema é que o trenó é movido por um pó mágico. Cada trenó que ele cria gasta pó proporcional à distância que ele percorre. E esse pó é muito caro (custa muitas boas ações das crianças). Então, dada uma lista de crianças, o Papai Noel quer saber qual o mínimo de pó que ele precisa para entregar presentes na casa de todas elas. 

Dependendo dessa lista, pode ser uma boa alternativa usar um trenó só, ou duplicar o trenó depois de atender uma certa criança específica, ou até mesmo usar N trenós para as N crianças. Depende muito da lista. ”  – http://goo.gl/AKgYO

Esse é um clássico problema de grafos e a solução se encaminhou naturalmente para uma implementação do algoritmo de Prim
O algoritmo de Prim destina-se a achar as arestas que compõem a árvore geradora mínima (ou seja, uma árvore com todos os vértices, mas ligados pela menor quantidade de arestas)  e tem várias aplicações interessantes :D.
A wikipedia salvadora explica o algoritmo da seguinte forma:
“Um algoritmo genérico para o algoritmo de Prim é dado da seguinte forma:

Escolha um vértice S para iniciar o subgrafo

enquanto há vértices que não estão no subgrafo

selecione uma aresta segura
insira a aresta segura e seu vértice no subgrafo        “
Uma aresta segura, no caso do algoritmo de Prim, é:
“A aresta segura é sempre a aresta de peso mínimo que conecta a árvore a um vértice não presente no conjunto X (subgrafo).”  Fonte: Universidade Federal de Alfenas.
No nosso problema, as casas das crianças são os vértices e o caminho entre as casas são as arestas selecionadas. O peso mínimo significa que escolheremos a casa mais próxima de onde o Papai Noel está, desde que ela não tenha sido visitada antes.  Com isso temos: Enquanto há casas de crianças que não foram visitadas, escolha a casa mais próxima, desde que ela não tenha sido visitada antes.
A solução de até onde conseguimos evoluir está no repositório do dojo no github
E os gulosos foram:
  • Thiago Belem
  • Juan Lopes
  • Eduardo Stalinho
  • Otávio Cardoso
  • Carlos Cunha
  • Henrique Bastos
  • Israel Teixeira
  • Lucas R. Martins
  • Diogo Vincenzi
  • Jacqueline Abreu
  • Jonatas Emidio

E as carinhas boazinhas (que ganharão presentes lindos), foram :D:

  • Comida (panetone +, cachorro quente, biscoitos bel[eé]m de gengibre ++++)
  • Pessoas
  • Problema+++++++++
  • Papai Noel na velocidade da luz (é possível?? Saiba mais no próximo episódio de “O Dojo de Natal – aventura no mundo das conjecturas” XD). ++
  • Python +
  • Primeira participação no dojoRio o/
  • Boa divisão do problema – dividimos o problema em partes (metas) para resolvê-lo melhor, em partes
  • Fim do mundo na sexta (acho que não foi, nê…)
  • Volta da galera antiga e galera nova aparecendo
  • Apelidos fofos sendo revelados – alguém agora ganhou a alcunha de “Xuco-Xuco” +
  • Meninas programando
  • O twitter do dojoRio voltou – Sigam o @dojoRio  #FF @dojoRio 😀 +
  • Participação da Galera – a vergonha dos novatos está diminuindo \o/
  • 2012 foi um ano muito legal para o dojoRio
  • Partials (Python) +
  • Prim
  • Casa cheia
  • Escolha prévia do problema
  • Guardaram biscoito para mim (mim = Jonatas Emidio, Jacqueline Abreu e Valéria Parajara #ProntoFalei e #ObrigadaCissa)
  • Espírito Natalino

As carinhas malvadas – essas não ganham presente, foram 😦 :

  • Atraso ++
  • Não acompanhar a evolução do problema +
  • Só abordamos as crianças malvadas
  • Muito tempo sem dojoRio
  • Não enrolar tanto para começar o dojo
  • Atrasos pessoais de 2012
  • Bagunça durante os dojos de 2012
  • Último dojoRio de 2012

Esse foi o último dojo de 2012 no Centro, mas em 2013 tem mais. O dojoRio – Centro volta com as atividades no dia 9 de janeiro de 2013, por isso, não deixe de estar conosco na Íparos Av Treze de Maio, 13 – sala 616. O pessoal começa a chegar entre 18:30 e 19:00 e para voltar, tem o metrô Cinelândia pertinho :D.

Esperamos todos vocês lá \o/

Anúncios

Comentários encerrados.

%d blogueiros gostam disto: