|
|
| (Uma revisão intermediária pelo mesmo usuário não está sendo mostrada) |
| Linha 1: |
Linha 1: |
| 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.
| | #REDIRECT [[Projeto e Analise de Algoritmos 2012]] |
| [[Imagem:Grafo-cidades-rj-sp-ms.png|right|550px]]
| |
| == Informacoes gerais ==
| |
| * Instrutor: prof. [http://www.lems.brown.edu/~rfabbri Ricardo Fabbri], Ph.D.
| |
| * Periodo: 1o. Semestre de 2012, voltado ao 7o. periodo de Engenharia da Computacao
| |
| * Tercas e Quartas, 9:40-11:30am, sala 211 e Lab Inf 01
| |
| | |
| | |
| === Pre-requisitos ===
| |
| * Sera assumido um primeiro curso em algoritmos e estruturas de dados, porem nao e' obrigatorio.
| |
| | |
| == Conteudo aproximado ==
| |
| * Enfase no projeto (design) de algoritmos
| |
| * Enfase em grafos
| |
| * Uso do C++ e' preferivel
| |
| * Enfase no uso do TopCoder para exercicios
| |
| * Algoritmos gulosos / greedy
| |
| * Programacao dinamica
| |
| * Fluxo em redes (Network flows)
| |
| | |
| == Recursos principais ==
| |
| * Grupo de discussao: [http://uerj.tk uerj.tk]
| |
| === Bibliografia ===
| |
| * 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
| |
| ** 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]
| |
| * 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]
| |
| | |
| === Top Coder ===
| |
| | |
| * Inicie em http://community.topcoder.com/tc
| |
| * Clique em "Register Now" ou "Login"
| |
| * Clique em '''O(n)''' no canto superior esquerdo para iniciar a Arena http://blog.theroyweb.com/wp-content/uploads/2009/06/topcoderalglink.png
| |
| * No ubuntu linux, abra o nautilus (navegador de arquivo) no diretorio onde foi baixado o ContestAppletProd.jnlp
| |
| * Clique no ContestApplestProd.jnlp com o botao direito do mouse, e selecione "abrir com Java Webstart" ou "Iced Tea"
| |
| ** Caso nao tenha essa opcao, instale os pacotes iced-tea* usando o synaptic ou outro gerenciador de pacotes
| |
| * Faca o Login
| |
| * Selecione Practice Rooms -> SRMs -> problemas Div 1. Os Div 2 sao mais dificeis e deixe-os para depois.
| |
| * Mais informacoes em [http://blog.theroyweb.com/topcoder-quickstart-tutorial Topcoder Quickstart Tutorial]
| |
| * Meu template C++ para o topcoder: http://hera.ethymos.com.br:1080/reacpad/p/paa
| |
| * Veja tambem os Editoriais, em que os melhores programadores explicam as solucoes de alguns SRM's e outras competicoes
| |
| ** http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
| |
| | |
| === Aulas - Slides ===
| |
| * [http://www.lems.brown.edu/~rfabbri/stuff/01-busca-em-grafos.odp busca em grafos - 26/mar - 4/apr] (atualizado em 8/apr)
| |
| * [http://www.lems.brown.edu/~rfabbri/stuff/02-greedy-etc.odp algoritmos greedy / gulosos]
| |
| * [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
| |
| * [http://www.lems.brown.edu/~rfabbri/stuff/04-dynamic-programming.odp dynamic programming / programacao dinamica] (atualizado em 20-26/jun) - cai na P2
| |
| === Provas ===
| |
| * P1: 22 de maio [http://www.lems.brown.edu/~rfabbri/stuff/prova-p1-PAA2012.pdf]
| |
| * P2: Quarta-feira dia 11 de julho
| |
| * Sub: Sexta-feira dia 13 de julho 10:30am - 12pm [http://www.lems.brown.edu/~rfabbri/stuff/prova-sub-PAA2012.pdf]
| |
| | |
| == Recursos adicionais ==
| |
| * [http://www.cs.princeton.edu/~wayne/kleinberg-tardos/ Slides de aula em Princeton]
| |
| * Site de material extra-oficial e troca p2p entre alunos: [http://uerj.tk uerj.tk]
| |
| * [[Lab Macambira]]: grupo de desenvolvedores de software livre e ajuda com Linux e atividades extra-curriculares de programacao.
| |
| ** Confira a sala de bate papo no IRC #labmacambira (freenode) [http://labmacambira.sf.net] para discussao sobre software livre, linux, e afins.
| |
| ** Para discussoes gerais, podemos criar nossa propria sala de bate-papo.
| |
| ** [[Configuring Ubuntu for Programming]]
| |
| | |
| == Tarefas ==
| |
| '''Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt'''
| |
| | |
| As tarefas devem ser formatadas com notacao matematica adequada, preferencialmente em [[Latex]].
| |
| | |
| Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt
| |
| | |
| 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.
| |
| | |
| | |
| === Tarefa 1 (em aula) ===
| |
| * Enunciado: flood fill algorithm
| |
| * Data: primeira aula, 14/mar/2012
| |
| * Alunos que entregaram
| |
| ** Eduardo Neves Goulart
| |
| ** Lucas Vieira Souza
| |
| ** Izabela Bastos Noe
| |
| ** Lucas da Silva Oliveira
| |
| ** José Eduardo de A. Agres
| |
| ** Dario Antonio Sanches
| |
| ** Marcos Belchior
| |
| ** Romulo Henrique
| |
| | |
| === Tarefa 2 ===
| |
| * Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
| |
| * Digitar em [[Latex]] de preferencia
| |
| * Alunos que entregaram
| |
| ** Marcos Belchior
| |
| | |
| | |
| === Tarefa 3 ===
| |
| * Enunciado: BFS pode ser implementado recursivamente? ficaria a implementação?
| |
| | |
| === Tarefa 4 ===
| |
| * Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)
| |
| | |
| === Tarefa 5 ===
| |
| * Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)
| |
| | |
| === Tarefa 6 (em aula) ===
| |
| * Enunciado: escovando bits e bytes
| |
| * Alunos que entregaram
| |
| ** Jose Ayres
| |
| ** Izabela Noe
| |
| ** Lucas Vieira
| |
| ** Dayany Cortes
| |
| ** Eduardo Goulart
| |
| ** Romulo Henrique
| |
| ** Paulo Cabral
| |
| ** Hamilton
| |
| ** Lucas Oliveira
| |
| ** Iwyson Thuller
| |
| | |
| === Apresentacao ===
| |
| * Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.
| |
| * Dayany
| |
| * Marcos Belchior
| |
| | |
| === Projeto no Top Coder ===
| |
| | |
| * Criar um login do topcoder (anonimo, so voce sabe)
| |
| * 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.
| |
| ** Um dos SRMs devera ser resolvido em maior detalhe, inclusive com pesquisa sobre assuntos que possam ser relevantes
| |
| ** Sugestoes para um trabalho bem-feito:
| |
| *** Comente as partes mais obscuras do editorial do seu SRM, se disponivel
| |
| *** Compare sua solucao com a solucao de outro participante mais experiente (um dos primeiros colocados do SRM)
| |
| **** Em que a solucao dele difere da sua? O que ele aparenta ter feito/usado?
| |
| *** Forneca desenhos, diagramas, fluxogramas explicando os conceitos e etapas do algoritmo
| |
| *** Forneca trechos de livros / pesquisa bibliografica de assuntos que mais te interessaram ou que mais foram uteis na solucao de cada problema.
| |
| | |
| ==== Duplas p/ Trabalho ====
| |
| * Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)
| |
| | |
| Lucas Oliveira e José Eduardo = SRMs 536 DIV 2 e 149 DIV 2
| |
| | |
| Iwyson e Romulo: SRM 262 DIV2 e 491 DIV2
| |
| | |
| Marcos Belchior e Izabela Bastos : SRM 535 DIV2 SRM 281 DIV2
| |
| | |
| Lucas Vieira e Dayany Espíndola = SRM 147 DIV1 e SRM 450 DIV1
| |
| | |
| Eduardo Neves e André Portes = ???
| |
| | |
| Hamilton e Paulo = SRM Div2 503 e SRM 512 Div2
| |
| | |
| == Criterio de Avaliacao ==
| |
| | |
| * Trabalhos: 30% da media (antes era 10%)
| |
| * O criterio final e simplificado ficou (favor avisar se precisar adicionar detalhes ou corrigir no caso de erro/discrepancia):
| |
| <small>
| |
| M_p = (P1 + P2)/2
| |
| M = 0.7*M_p + 0.3*T (atualizado de 10% para 30% com acordo dos alunos), onde T é a nota dos trabalhos
| |
| Se M >= 5, passa --> M
| |
| Sub: repoe menor de P1, P2 (apenas se alguem faltou alguma prova ou quiser melhorar nota - mas quem entregar ira substituir)
| |
| M_sub = media com sub
| |
| Se M_sub >= 5, passou --> M_sub
| |
| | |
| 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.
| |
| </small>
| |
| | |
| * ''A prova final passa a nao ser mais obrigatoria.''
| |
| | |
| [[Category:IPRJ]] [[Category:Lab Macambira]]
| |
