http://wiki.nosdigitais.teia.org.br/index.php?title=Projeto_e_Analise_de_Algoritmos_2012&feed=atom&action=historyProjeto e Analise de Algoritmos 2012 - Histórico de revisão2024-03-29T05:50:11ZHistórico de revisões para esta página neste wikiMediaWiki 1.39.0http://wiki.nosdigitais.teia.org.br/index.php?title=Projeto_e_Analise_de_Algoritmos_2012&diff=12688&oldid=prevV1z: archiving 2012 course2013-06-20T16:14:10Z<p>archiving 2012 course</p>
<p><b>Página nova</b></p><div>Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2012 no [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/[http://pt.wikipedia.org/wiki/IPRJ UERJ], de utilidade geral para a formacao de programadores de nivel intermediario e avancado.<br />
[[Imagem:Grafo-cidades-rj-sp-ms.png|right|550px]]<br />
== Informacoes gerais ==<br />
* Instrutor: prof. [http://www.lems.brown.edu/~rfabbri Ricardo Fabbri], Ph.D.<br />
* Periodo: 1o. Semestre de 2012, voltado ao 7o. periodo de Engenharia da Computacao<br />
* Tercas e Quartas, 9:40-11:30am, sala 211 e Lab Inf 01<br />
<br />
<br />
=== Pre-requisitos ===<br />
* Sera assumido um primeiro curso em algoritmos e estruturas de dados, porem nao e' obrigatorio.<br />
<br />
== Conteudo aproximado ==<br />
* Enfase no projeto (design) de algoritmos<br />
* Enfase em grafos<br />
* Uso do C++ e' preferivel<br />
* Enfase no uso do TopCoder para exercicios<br />
* Algoritmos gulosos / greedy<br />
* Programacao dinamica<br />
* Fluxo em redes (Network flows)<br />
<br />
== Recursos principais ==<br />
* Grupo de discussao: [http://uerj.tk uerj.tk]<br />
=== Bibliografia ===<br />
* Livro principal: "Algorithm Design" - Jon Kleinberg & Eva Tardos (ver [http://uerj.tk uerj.tk]) http://www.aw-bc.com/info/kleinberg/assets/images/cover.jpg<br />
** Trata-se do melhor livro para estudar para uma entrevista. O Autor desenvolveu ideias das mais famosas relacionados ao '''PageRank do Google''' [http://citeseer.ist.psu.edu/viewdoc/summary;jsessionid=F4971BF0251DAD6EBF655902AAD9BA17?doi=10.1.1.120.3875]<br />
* Livro interessante com foco em algoritmos geometricos: [http://books.google.com.br/books?id=Ax50ccq_kFAC&dq=algorithmic+geometry&source=gbs_navlinks_s Algorithmic Geometry]<br />
<br />
=== Top Coder ===<br />
<br />
* Inicie em http://community.topcoder.com/tc<br />
* Clique em "Register Now" ou "Login"<br />
* Clique em '''O(n)''' no canto superior esquerdo para iniciar a Arena http://blog.theroyweb.com/wp-content/uploads/2009/06/topcoderalglink.png<br />
* No ubuntu linux, abra o nautilus (navegador de arquivo) no diretorio onde foi baixado o ContestAppletProd.jnlp<br />
* Clique no ContestApplestProd.jnlp com o botao direito do mouse, e selecione "abrir com Java Webstart" ou "Iced Tea"<br />
** Caso nao tenha essa opcao, instale os pacotes iced-tea* usando o synaptic ou outro gerenciador de pacotes<br />
* Faca o Login<br />
* Selecione Practice Rooms -> SRMs -> problemas Div 1. Os Div 2 sao mais dificeis e deixe-os para depois.<br />
* Mais informacoes em [http://blog.theroyweb.com/topcoder-quickstart-tutorial Topcoder Quickstart Tutorial]<br />
* Meu template C++ para o topcoder: http://hera.ethymos.com.br:1080/reacpad/p/paa<br />
* Veja tambem os Editoriais, em que os melhores programadores explicam as solucoes de alguns SRM's e outras competicoes<br />
** http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis<br />
<br />
=== Aulas - Slides ===<br />
* [http://www.lems.brown.edu/~rfabbri/stuff/01-busca-em-grafos.odp busca em grafos - 26/mar - 4/apr] (atualizado em 8/apr)<br />
* [http://www.lems.brown.edu/~rfabbri/stuff/02-greedy-etc.odp algoritmos greedy / gulosos]<br />
* [http://www.lems.brown.edu/~rfabbri/stuff/03-analise-e-divide_and_conquer.odp analise e divide-and-conquer] (atualizado em 20/jun) - cai na P2<br />
* [http://www.lems.brown.edu/~rfabbri/stuff/04-dynamic-programming.odp dynamic programming / programacao dinamica] (atualizado em 20-26/jun) - cai na P2<br />
=== Provas ===<br />
* P1: 22 de maio [http://www.lems.brown.edu/~rfabbri/stuff/prova-p1-PAA2012.pdf]<br />
* P2: Quarta-feira dia 11 de julho<br />
* Sub: Sexta-feira dia 13 de julho 10:30am - 12pm [http://www.lems.brown.edu/~rfabbri/stuff/prova-sub-PAA2012.pdf]<br />
<br />
== Recursos adicionais ==<br />
* [http://www.cs.princeton.edu/~wayne/kleinberg-tardos/ Slides de aula em Princeton]<br />
* Site de material extra-oficial e troca p2p entre alunos: [http://uerj.tk uerj.tk]<br />
* [[Lab Macambira]]: grupo de desenvolvedores de software livre e ajuda com Linux e atividades extra-curriculares de programacao.<br />
** Confira a sala de bate papo no IRC #labmacambira (freenode) [http://labmacambira.sf.net] para discussao sobre software livre, linux, e afins.<br />
** Para discussoes gerais, podemos criar nossa propria sala de bate-papo.<br />
** [[Configuring Ubuntu for Programming]]<br />
<br />
== Tarefas ==<br />
'''Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt'''<br />
<br />
As tarefas devem ser formatadas com notacao matematica adequada, preferencialmente em [[Latex]].<br />
<br />
Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt<br />
<br />
Quando a tarefa involver qualquer programacao, o aluno devera enviar o codigo fonte. O codigo junto com a documentacao devera estar dentro de um unico diretorio comprimido com .zip ou tar, com o nome do aluno, disciplina e data.<br />
<br />
<br />
=== Tarefa 1 (em aula) ===<br />
* Enunciado: flood fill algorithm<br />
* Data: primeira aula, 14/mar/2012<br />
* Alunos que entregaram<br />
** Eduardo Neves Goulart<br />
** Lucas Vieira Souza<br />
** Izabela Bastos Noe<br />
** Lucas da Silva Oliveira<br />
** José Eduardo de A. Agres<br />
** Dario Antonio Sanches<br />
** Marcos Belchior<br />
** Romulo Henrique<br />
<br />
=== Tarefa 2 ===<br />
* Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes<br />
* Digitar em [[Latex]] de preferencia<br />
* Alunos que entregaram<br />
** Marcos Belchior<br />
<br />
<br />
=== Tarefa 3 ===<br />
* Enunciado: BFS pode ser implementado recursivamente? ficaria a implementação?<br />
<br />
=== Tarefa 4 ===<br />
* Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)<br />
<br />
=== Tarefa 5 ===<br />
* Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)<br />
<br />
=== Tarefa 6 (em aula) ===<br />
* Enunciado: escovando bits e bytes<br />
* Alunos que entregaram<br />
** Jose Ayres<br />
** Izabela Noe<br />
** Lucas Vieira<br />
** Dayany Cortes<br />
** Eduardo Goulart<br />
** Romulo Henrique<br />
** Paulo Cabral<br />
** Hamilton<br />
** Lucas Oliveira<br />
** Iwyson Thuller<br />
<br />
=== Apresentacao ===<br />
* Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.<br />
* Dayany<br />
* Marcos Belchior<br />
<br />
=== Projeto no Top Coder ===<br />
<br />
* Criar um login do topcoder (anonimo, so voce sabe)<br />
* Fazer 2 SRM's (a serem entregues no futuro). Documente sua solucao (em [[Latex]] de preferencia). Esses SRMs devem ser tais que nao ha' editorial a respeito no topcoder.<br />
** Um dos SRMs devera ser resolvido em maior detalhe, inclusive com pesquisa sobre assuntos que possam ser relevantes<br />
** Sugestoes para um trabalho bem-feito:<br />
*** Comente as partes mais obscuras do editorial do seu SRM, se disponivel<br />
*** Compare sua solucao com a solucao de outro participante mais experiente (um dos primeiros colocados do SRM)<br />
**** Em que a solucao dele difere da sua? O que ele aparenta ter feito/usado?<br />
*** Forneca desenhos, diagramas, fluxogramas explicando os conceitos e etapas do algoritmo<br />
*** Forneca trechos de livros / pesquisa bibliografica de assuntos que mais te interessaram ou que mais foram uteis na solucao de cada problema.<br />
<br />
==== Duplas p/ Trabalho ====<br />
* Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)<br />
<br />
Lucas Oliveira e José Eduardo = SRMs 536 DIV 2 e 149 DIV 2<br />
<br />
Iwyson e Romulo: SRM 262 DIV2 e 491 DIV2<br />
<br />
Marcos Belchior e Izabela Bastos : SRM 535 DIV2 SRM 281 DIV2 <br />
<br />
Lucas Vieira e Dayany Espíndola = SRM 147 DIV1 e SRM 450 DIV1<br />
<br />
Eduardo Neves e André Portes = ???<br />
<br />
Hamilton e Paulo = SRM Div2 503 e SRM 512 Div2<br />
<br />
== Criterio de Avaliacao ==<br />
<br />
* Trabalhos: 30% da media (antes era 10%)<br />
* O criterio final e simplificado ficou (favor avisar se precisar adicionar detalhes ou corrigir no caso de erro/discrepancia):<br />
<small><br />
M_p = (P1 + P2)/2 <br />
M = 0.7*M_p + 0.3*T (atualizado de 10% para 30% com acordo dos alunos), onde T é a nota dos trabalhos<br />
Se M >= 5, passa --> M<br />
Sub: repoe menor de P1, P2 (apenas se alguem faltou alguma prova ou quiser melhorar nota - mas quem entregar ira substituir)<br />
M_sub = media com sub<br />
Se M_sub >= 5, passou --> M_sub<br />
<br />
Adendo (em acordo com os alunos): a M_sub = M_f pois sera considerada a mesma prova e a prova final nao mas faz efeito real com trabalhos a 30%. Quem for usar a prova como Sub ira substituir a nota independentemente do resultado.<br />
</small><br />
<br />
* ''A prova final passa a nao ser mais obrigatoria.''<br />
<br />
[[Category:IPRJ]] [[Category:Lab Macambira]]</div>V1z