Pontão Nós Digitais - Contribuições do usuário [pt-br]

Projeto e Analise de Algoritmos

2013-07-26T06:37:20Z

Cardinot: /* Duplas p/ Trabalho */

Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2013 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.

'''[[PAA2012|Link para o curso de 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 2013, voltado ao 7o. periodo de Engenharia da Computacao
* Tercas e Quintas, 10:40-12:20am, sala 212 e Lab Inf 02

=== 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] (atualizado em 8/apr/2012) - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/02-greedy-etc.odp algoritmos greedy / gulosos] - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/03-analise-e-divide_and_conquer.odp analise e divide-and-conquer] (atualizado em 20/jun/2012) - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/04-dynamic-programming.odp dynamic programming / programacao dinamica] (atualizado em 20-26/jun/2013) - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/05-network-flow.odp network flow / fluxo em redes -- Parte 1] (atualizado em 20/jun/2013) - cai na P2
* escovando bits

=== Provas ===
* P1: 27/jun/2013 [http://www.lems.brown.edu/~rfabbri/stuff/prova-p1-PAA2012.pdf (prova anterior: 2012)]
* P2:
* Sub/Final: [http://www.lems.brown.edu/~rfabbri/stuff/prova-sub-PAA2012.pdf (prova anterior: 2012)]

== 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, veja #iprj
** [[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.

=== Tarefas de 2013 ===

==== Tarefa 1 (em aula) - 2013 ====
* Enunciado: flood fill algorithm / labirinto
* Data: primeira aula
* Alunos que entregaram
** ((lista pendente))

==== Tarefa 2 - 2013 ====
* Enunciado: Topological Sort
* Estudar e comentar o funcionamento do codigo fonte do comando GNU tsort do unix
* Pesquisar como funciona a arvore utilizada no codigo
* Note que o algoritmo eh simples mas nao eh trivial de implementar bem

==== Tarefa 3 - 2013 ====
* Implementar o mergesort
* Plotar grafico do tempo de execucao minimo, maximo, e medio para diferentes tamanhos de entradas aleatoreas

=== Projetos no Top Coder ===

* Criar um login do topcoder (anonimo, so voce sabe)
* Fazer 2 SRM's (div 1 ou 2) a serem entregues em forma de relatório e apresentados ao professor no futuro. Documente sua solucao (em [[Latex]] de preferencia).
** Cada aluno deverá escolher um SRM primário, do qual será responsável, e um SRM secundário, em que deverá ajudar um outro aluno.
** Os SRMs primário deverá ser programado em maior detalhe pelos alunos responáveis, inclusive com pesquisa sobre assuntos que possam ser relevantes
** Cada aluno irá entregar um relatório e irá fazer um exame oral individual rapido para mostrar que sabe programar os problemas do seus SRMs.
** 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.
* Notas
** Cada trabalho (SRM) terá uma nota final com base na apresentacao oral ao professor e relatorio
** A nota de cada aluno sera 70% a nota do seu SRM primário mais 30% a nota final do SRM secundário
** Atencao: O peso deste trabalho poderá suplantar o da P2 caso os alunos estejam de acordo.

==== Duplas p/ Trabalho ====
* Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)
* Nao pode haver repeticao de SRMs
* Evitar repetir os colegas primarios/secundarios (mas se for necessario repetir, tudo bem)

Caio(Primário) e Pedro(Secundário): SRM 145 DIV2

Lucas Oliveira(Primário) e Rafael Erthal(Secundário): SRM 144 DIV2

Gustavo(Primário) e Marcos(Secundário): SRM 147 DIV2

Marcos(Primário) e Gustavo(Secundário): SRM 149 DIV2

Pedro(Primário) e Caio(Secundário): SRM 144 DIV1

<hr />

==== Bonus TopCoder ====
Opcionalmente, pontos extras na media serao concedido a alunos que participarem de SRM's oficiais de acordo com os seguintes criterios:
* '''Para receber o bonus o aluno tera que obter nota na P1 acima de 6'''
* Alunos que participarem de um SRM oficial e relatarem os problemas e solucoes num relatorio curto irao receber ate 1 ponto adicional na media
* Alunos que competirem entre si e obteve primeiro lugar na sala (num mesmo SRM) irao receber ate 2 pontos adicionais na media, contanto que o numero de participantes da sala seja igual ou maior que 3
* Alunos que resolverem todos os problemas dentro do tempo oficial do SRM irao obter 3 pontos adicionais na media
* Alunos que obtiverem top 5 geral no SRM irao passar com media 10
* '''Voces tem varias chances!'''
** Calendario de SRMs do topcoder (horario EST de nova yorque) [http://community.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth]

=== Tarefas de 2012 ===

==== Tarefa 1 (em aula) - 2012 ====
* Enunciado: flood fill algorithm / labirinto
* Data: primeira aula

==== Tarefa 2 - 2012 ====
* Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
* Digitar em [[Latex]] de preferencia

==== Tarefa 3 - 2012 ====
* Enunciado: BFS pode ser implementado recursivamente? ficaria a implementação?

==== Tarefa 4 - 2012 ====
* Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)

==== Tarefa 5 - 2012 ====
* Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)

==== Tarefa 6 (em aula) - 2012 ====
* Enunciado: escovando bits e bytes

==== Apresentacao - 2012 ====
* Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.

== Criterio de Avaliacao ==

* Trabalhos: 30% da media
* 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]]

Scilab

2012-04-22T13:43:59Z

Cardinot: /* Compiling */

Scilab is a programming language associated with a rich collection of numeric
algorithms for covering most aspects of computational and scientific problems.

== Cloning ==

Cloning the Scilab repository. It is a large project - you will be downloading
over 300MB of code.

=== Git ===

$ git clone git://git.scilab.org/scilab

== Compiling ==

After cloning the git repository, a good approach for installing the required dependencies is:

$ sudo apt-get build-dep scilab

or

$ sudo aptitude build-dep scilab

After that,

$ ./configure

Probably there will be a couple of dependencies which are required to be more
recent than the installed one. Look around the internet for them.

For the ''master'' branch, I had problems with libjgraphx (latest one was not available in Ubuntu 11.10).
* Download it from [http://www.jgraph.com/jgraphdownload.html official site].
* Extract and enter jgraphx/lib/
$ sudo cp jgraphx.jar /usr/share/java/jgraphx-1.9.2.5.jar
$ sudo ln -sf /usr/share/java/jgraphx-1.9.2.5.jar /usr/share/java/jgraphx.jar

The <tt>master</tt> branch also asked for updated flexdock >= 0.5.3, jrosetta and
jlatexmath. The <tt>graphic</tt> branch asked for scirenderer:
* Download them from
** http://java.net/projects/flexdock/downloads
** http://dev.artenum.com/projects/JRosetta
** http://forge.scilab.org/index.php/p/jlatexmath
** http://forge.scilab.org/index.php/p/scirenderer
* The remaining steps are like those given above for jgraphx.

If configure complains of '''missing arpack''', download from the link shown by
<tt>configure</tt>, then compile and install it as usual. Type 'ldconfig' and
then get back to compiling Scilab. If there is still any problems related to arpack/arpack-ng,
try the dirty fixes in these bug reports:
* http://bugzilla.scilab.org/show_bug.cgi?id=10646
* http://forge.scilab.org/index.php/p/arpack-ng/issues/689/ (comment 1)

If the proposed solutions above do not work, you can disable the compilation of ARPACK. Instead of using ". / Configure", do this:
$ ./configure --without-arpack-ng

If configure complains of '''missing jogl2''', this is a recently introduced problem in Scilab master branch. See
* http://bugzilla.scilab.org/show_bug.cgi?id=11030

Finally,
$ make
$ sudo make install

Build the documentation
$ make doc

Warning: this takes a long time! go sip a cup of acerola juice while you wait.

If the run scilab this error appears on the screen:

"Gtk-WARNING **: Unable to locate theme engine in module_path: "pixmap","

To fix, do this:
$ sudo apt-get install gtk2-engines-pixbuf

=== Warning! ===
If you switch branches, e.g. from 5.3 and master (6.0), and then type 'make',
you will obtain some crazy random errors; do not forget to type 'make distclean'
after every branch switch ans start it *all* again.

== Examples ==

* The Scilab package Chaos
** [http://cpc.cs.qub.ac.uk/summaries/AEAP_v1_0.html site da distribuição].
* [[SIP]] image processing toolbox

== Hacking ==

=== Navigating the souce code ===

* See the code organization at: http://doxygen.scilab.org/master_wg/

=== Branches ===

* We work at the master branch (future 5.4), but you can try YaSp (future 6.x)
* See a description of the branches [http://wiki.scilab.org/Scilab%20branch%20policies]

=== Debugging e Profiling ===

See [http://wiki.scilab.org/Debugging%20and%20Profiling%20Scilab%205 Debugging Scilab 5] at the Scilab wiki

They suggest KDbg as a graphical debugger, but it doesn't seem to be in
synaptic. Therefore, ddd continues to be the best graphical debugger in our
opinion.

Also see some useful kcachegrind tips in [[User:v1z]]'s blog.

=== Hacking Journal - xgetmouse ===
* xgetmouse is written in Java. The file is in scilab/modules/gui/src/java/org/scilab/modules/gui/events/Jxgetmouse.java
** '''very useful:''' If you change Jxgetmouse.java, you only have to type "make" inside scilab/modules/gui/src. this will recompile only this part. Then you invoke './bin/scilab' inside the scilab top directory, and you're all set! No need for a time-consuming toplevel make or make install!!
* scilab core calls xgetmouse java from C++
** a JVM gets started in C++ at scilab/modules/gui/src/jni/Jxgetmouse.cpp
** developer writes the .java, as well as a .xml (scilab/modules/gui/src/jni/Jxgetmouse.giws.xml) to interface it with scilab (enabling a scilab language call xgetmouse to get java)
** the tool to get the xml and generate the .cpp and is called [http://forge.scilab.org/index.php/p/giws/page/GIWS-tutorial/ GIWS], developed by the Sciab team to ease calling Java inside C++
** there are other files which Im not sure if they are automagically generated:
*** /scilab/modules/graphics/sci_gateway/c/sci_xgetmouse.c and /scilab/modules/gui/includes/CallJxgetmouse.h

== Collaborators within Lab Macambira ==

[[Nivaldo Bondança]]

[[GT-Video]]

[[Category:Lab_Macambira]] [[Category:Video]]

Scilab

2012-04-13T02:19:37Z

Cardinot: /* Compiling */

Scilab

2012-04-12T15:43:53Z

Cardinot: /* Compiling */