Exibir código-fonte para SCC-216(rminghim)

''' SCC-216 - Modelagem Computacional em Grafos ''' [[https://uspdigital.usp.br/jupiterweb/obterDisciplina?sgldis=SCC0216=  ementa]]



'''Professora:''' Rosane Minghim (rminghim at icmc.usp.br)

Horário de atendimento: Quartas-feiras 17:00 às 19:00

Sala: 4-206


'''Estagiário PAE:''' Henry Heberle (henry at icmc.usp.br) - Adicionar ao assunto do e-mail: [SCC-216]

Horário de atendimento: Quintas-feiras 18:00 às 20:00 - '''Com agendamento por e-mail'''.

Sala: 4-001


'''Monitor:''' Denis Reis (denismr at gmail.com)

Horário de atendimento: Segundas-feiras 16:00 às 18:00

Sala: lab 7, CISC



== Avisos ==
* [[Media:Cronograma_e_Avaliação,_SCC216-2013.pdf‎|Cronograma do curso, Cálculo da média, etc.]]
* '''19/03''' - Descrição do '''Trabalho 1''';
* '''20/03''' - Foi definida a data final de entrega do '''Trabalho 1''';
* '''27/03''' - Foi alterada a data de entrega do '''Trabalho 1''';
* '''03/04''' - Dúvidas/Problemas com o '''Trabalho 1''' devem ser tratados diretamente com o estagiário PAE pelo e-mail acima.
* '''05/04''' - Mais uma dica adicionada à seção do Trabalho 1, um .txt
* '''06/04''' - Adicionado .txt com observações sobre as duplas e os envios (Trab1). Tratar sobre problemas do trab1 por '''e-mail''' com o PAE, '''com assunto''': '''Problemas do Trabalho 1 [SCC-216]'''
* '''11/04''' - Descrição do '''Trabalho 2''';
* '''15/04''' - Data do '''Trabalho 2''' definida;
* '''15/04''' - Arquivo de info. sobre duplas e envios do '''Trabalho 1''' atualizado. Lembre-se de verificar este arquivo para ver se você recebeu nota, etc. Qualquer problema relacionado, seguir a instrução do dia '''06/04''';
* '''26/04''' - '''Trabalho 2''' adiado para dia 29/04/2013. Após essa data será descontada da nota 7% a cada dia de atraso, podendo ser submetido até quinta-feira (dia 2);
* '''02/05''' - Leia as descrições de envio e de duplas, bem como as informações sobre elas depois de formadas, e sobre os envios, tudo está na Wiki, ou em forma de arquivo .txt também na Wiki. Lembrem-se também de que vale a nota do último arquivo submetido ao sistema SQTPM. Cuidado para não diminuir sua nota por causa erro com relação a isso;
* '''03/05''' - Informações sobre as duplas, as submissões e os plágios atualizadas. Verificar o .txt respectivo. Certifique-se de que seu navegador não está exibindo a versão antiga, armazenada em cache. E-mails sobre problemas deste trabalho devem ter no assunto: '''Problemas do Trabalho 2 [SCC-216]'''. Lembre-se: '''Trabalhos similares e sem dupla definida -> Plágio -> Nota = zero''';
* '''06/05''' - [[Media:NotasP1_grafos.zip|Notas da P1 divulgadas  - ainda SEM somar o bônus]];
* '''10/05''' - Trabalho 3 e data de entrega definidos;
* '''28/05''' - Trabalho 4 e data de entrega definidos;
* '''11/06''' - [[Media:NotasTrab1a4.zip|Notas dos Trab+Lab 1 a 4]] (com senha)

<!-- <span style="color:red"></span> -->

== Material Didático ==

# [[Media:00_-_Aplicações_e_Visualização_-_sem01_-_Henry.pdf‎|Redes: Aplicações e Visualização]]
# [[Media:2013_-_01_-_Introdução_a_Grafos.pdf‎|Introdução a Grafos]]
# [[Media:2013_-_02_-_Estruturas_de_Dados.pdf‎|Estruturas de Dados para Grafos]]
# [[Media:2013_-_03_-_Travessias.pdf‎|Travessias]]
# [[Media:2013_-_04_-_Ordenação_Topológica_e_Componentes_Fortemente_Conectados.pdf‎‎|Ordenação Topológica e Componentes Fortemente Conectados]]
# [[Media:2013_-_05_-_Árvores_Geradoras_Mínimas.pdf‎|Árvores Geradoras Mínimas]]
# [[Media:2013_-_06_-_Caminhos_Mínimos.pdf‎|Caminhos Mínimos]]
# [[Media:Aula_redes_complexas.pdf.part1.rar‎|Redes Complexas - part1]] [[Media:Aula_redes_complexas.pdf.part2.rar‎‎| - part2]] [[Media:Aula_redes_complexas.pdf.part3.rar‎| - part3]] (unir as 3 partes)

== Laboratório ==
Obs. Dúvidas e problemas com o SQTPM, tratar direto com o estagiário PAE.
<!--
* '''Teste''': Testar o sistema de submissão de trabalhos [http://lcadfs2.lcad.icmc.usp.br/cgi-bin/scc216/turma2/sqtpm.pl SQTPM].
:::[[Media:Lab_0_-_Exercício_de_teste_do_SQTPM.tar.gz|Arquivo com descrição do exercício e programa a ser testado e corrigido]]
-->
* [[Media:Lab_1_-_Estruturas_de_dados_e_Travessias.pdf‎|'''Lab1 - Descrição''']]

* [[Media:Lab_2_-_Componentes_e_Ordenação_Topológica.pdf‎|'''Lab2 - Descrição''']]

* [[Media:Lab_3_-_Detecção_de_Ciclos,_Árvores_geradoras_e_Caminhos_mínimos.pdf‎|'''Lab3 - Descrição''']]

* [[Media:Lab_4_-_Redes_Complexas_2013_scc216.pdf‎|'''Lab4 - Descrição''']]
* '''Lab5 - Descrição'''

== Trabalhos ==
Obs. Dúvidas e problemas com o SQTPM, tratar direto com o estagiário PAE.
* [http://lcadfs2.lcad.icmc.usp.br/cgi-bin/scc216/turma2/sqtpm.pl SQTPM]
* '''Trab1''':
** Deadline para entrega: 05/04/2013;
** Trabalho em dupla ('''no próximo trabalho, e em outros, a dupla não pode ser a mesma'''). Enviar Nome e N USP dos integrantes da dupla deste trabalho para o PAE. Escrever no assunto do e-mail: '''Grupo do Trabalho 1 [SCC-216]'''.
** Pode ser feito individualmente. Neste caso, o e-mail acima não precisa ser enviado. Ele só serve para eu não identificar dois trabalhos 100% iguais como plágio.
** '''Ambos os integrantes da dupla devem enviar o trabalho (ambos enviam o mesmo arquivo, idêntico) ao SQTPM'''. Quem não enviar terá nota igual a zero.
** A descrição do trabalho é longa. Então, recomendo a todos que leiam '''atentamente'''; e tentem executar a rota descrita em '''Dica'''.
** [[Media:Trab_1_-_Estruturas_de_dados_e_Travessias.pdf‎|Descrição do Trabalho 1]]
** [[Media:Mapa.png|Rascunho de um dos mapas do casal]]
** Se houver dúvidas sobre este trabalho, entre em contato diretamente com o estagiário PAE (Henry).
** Lembre-se de ler o último quadro da descrição, sobre plágio (o 'individual' no quadro se refere à dupla).
** Se o SQTPM acusar erro de formatação, tente por um "\n" ao fim da saída/resultado.
** Dica Final: [[Media:Dica Trabalho1.txt|Dica final para o Trabalho 1]] (Esta é só uma dica e expressa a ideia principal, não deve ser seguida como se fosse a especificação, pois pode estar diferente - tempo, decisões, etc.).
** Documento com informações sobre os envios de trabalho: [[Media:Duplas_trabalho1.txt|info_trabalho1.txt]]


* '''Trab2''':
** Deadline para entrega: 26/04/2013;
** As regras são similares ao Trabalho 1, inclusive sobre o envio.
** Trabalho em dupla, que não pode ser a mesma do Trabalho 1. Enviar Nome e N USP dos integrantes da dupla deste trabalho para o PAE. Escrever no assunto do e-mail: '''Grupo do Trabalho 2 [SCC-216]'''. Perceba que a identificação da dupla é por e-mail, como descrito aqui! Não pelo código do programa. 
** Pode ser feito individualmente. Neste caso, o e-mail acima não precisa ser enviado. Ele só serve para eu não identificar dois trabalhos 100% iguais como plágio.
** Ambos os integrantes da dupla devem enviar o trabalho (ambos enviam o mesmo arquivo, idêntico) ao SQTPM. Quem não enviar terá nota igual a zero.
** [[Media:Trab_2_-_Componentes_e_Ordenação_Topológica.pdf‎|Descrição do Trabalho 2]]
** Se houver '''dúvidas sobre este trabalho, entre em contato diretamente com o monitor da disciplina (Denis)''' preferencialmente, ou com o Henry no caso do Denis estar indisponível. No caso de dúvida sobre SQTPM, fale com o PAE Henry.
** Arquivo com as duplas registradas: [[Media:Duplas_T2_SCC216_2013.txt‎|info_trabalho2.txt]]


* '''Trab3''':
** Deadline para entrega:  '''27/05/2013''', com penalidade de 7% por dia de atraso, podendo entregar até  31/05/2013. '''Não há possibilidade de adiar este trabalho'''.
** Trabalho em dupla ou individual. A dupla pode ser a mesma do Trabalho 1 ou do Trabalho 2, ou uma nova. A dupla deve enviar Nome e N USP dos integrantes para o PAE. Escrever no assunto do e-mail: '''Grupo do Trabalho 3 [SCC-216]'''. 
** Não é necessário colocar o nome da dupla no Código! Colocar a dupla no código não elimina a necessidade de '''identificar a dupla por e-mail'''.
** Trabalhos semelhantes e sem '''dupla definida por e-mail''' implica em nota zero, pois indica plágio.
** Pode ser feito individualmente. Neste caso, o e-mail tratado acima não precisa ser enviado.
** '''Ambos os integrantes da dupla devem enviar o trabalho (ambos enviam o mesmo arquivo, idêntico) ao SQTPM'''. Quem não enviar terá nota igual a zero, mesmo que tenha identificado a dupla.
** Se houver dúvidas sobre este trabalho, entre em contato diretamente com o Denis ou com o Henry.
** Lembre-se de ler o último quadro da descrição, sobre plágio.
** [[Media:Trab_3_-_Detecção_de_Ciclos,_Árvores_geradoras_e_Caminhos_mínimos.pdf‎|Descrição do Trabalho 3]]
** Documento com informações sobre os envios de trabalho e duplas: [[Media:Duplas2013scc216_trab3.txt|info_trabalho3.txt]]
** '''Nota''': um canal liga uma base a um satélite, não liga duas bases. Então, quando S=1 não tem como duas bases se comunicarem por satélite. Apenas para S>1 há comunicação entre bases por satélite.


* '''Trab4''':
** Deadline para entrega:  '''10/06/2013'''; '''Não há possibilidade de adiar este trabalho. Penalização por dia de atraso: 100%.'''.
** Trabalho em dupla ou individual. A dupla '''não pode''' ser a mesma do '''Trabalho 3'''. A dupla deve enviar Nome e N USP dos integrantes para o PAE. Escrever no assunto do e-mail: '''Grupo do Trabalho 4 [SCC-216]'''. 
** Não é necessário colocar o nome da dupla no Código! Colocar a dupla no código não elimina a necessidade de identificar a dupla por e-mail.
** Trabalhos semelhantes e sem dupla definida por e-mail implica em nota zero, pois indica plágio.
** Pode ser feito individualmente. Neste caso, o e-mail tratado acima não precisa ser enviado.
** '''Ambos os integrantes da dupla devem enviar o trabalho (ambos enviam o mesmo arquivo, idêntico) ao SQTPM'''. Quem não enviar terá nota igual a zero, mesmo que tenha identificado a dupla.
** Se houver dúvidas sobre este trabalho, entre em contato diretamente com o Henry ou com o Denis.
** Lembre-se de ler o último quadro da descrição, sobre plágio.
** [[Media:Trab_4_-_Redes_Complexas_scc216_2013.pdf‎|Descrição do Trabalho 4]]
** Documento com informações sobre os envios de trabalho: [[Media:Duplas_scc216_2013_1_trabalho4.txt|info_trabalho4.txt]]

* '''Trab5''':

== Bibliografia==

Texto:
* CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Editora Campus. 2002.
* ZIVIANI, N. - Projeto de algoritmos: com implementações em Pascal e C. 2a. Edição. Pioneira Thomson Learning, 2005.
* Bibliografia dos slides.
* Texto disponíveis no site.

Bibliografia Complementar:
* HOROWITZ,E.; SAHNI,S. Fundamentals of Data Structures in Pascal, Computer Science Press, 1990.
* TENEMBAUM,A.M. et alli Data Structures Using C, Prentice-Hall, 1990.
* SZWARCFITER,J.L. Grafos e Algoritmos Computacionais. Editora Campus, 1983.
* AHO,A.V.; HOPCROFT,J.E.; ULLMAN,J.D. Data Structure and Algorithms. Readings, Addison Wesley, 1982.

== Links Interessantes ==

* [http://flowingdata.com/category/visualization/network-visualization/ Exemplos de visualização de redes sociais, políticas, de influência histórica, de mapeamento da ciência, de citações, de sabores de comida, etc.]
* [http://www.autodeskresearch.com/projects/citeology '''''Citeology''''' - uma árvore genealógica de artigos.]
* [http://www.uncannyxmen.net/images/article/relationship/relationshipmapv1.htm ''X-Men Universe Relationship Map'']
* [http://ceur-ws.org/Vol-559/Poster3.pdf Integração de dados biológicos, análise visual e ] [http://pt.wikipedia.org/wiki/Ontologia_(ciência_da_computação) Ontologia].

== Ferramentas ==

* [http://www.cytoscape.org/ Cytoscape] - Análise e visualização de redes.
* [http://gephi.org/ Gephi] - Análise e visualização de redes.
* [http://biologicalnetworks.net/ BiologicalNetworks] - Análise de redes biológicas.
* [http://ccl.northwestern.edu/netlogo/ NetLogo] - Modelagem de redes dinâmicas.
* [http://igraph.sourceforge.net/ iGraph] - Biblioteca para programação.
* [http://pajek.imfm.si/doku.php Pajek] - Windows-only.
* [http://nodexl.codeplex.com/ NodeXL] - Integrado ao Excel.
* [http://networkx.lanl.gov/ NetworkX] - Para usar com Python; trabalhar com grandes redes, levando vantagem de bibliotecas em C e Fortran para cálculos com matrizes.
* [http://infoserver.lcad.icmc.usp.br/infovis2/PExGraph PEx-Graph] - Visualização de redes sociais via arquivo VNA ou Bibtex.
* [http://infoserver.lcad.icmc.usp.br/infovis2/VisPipelineGraph VisPipeline-Graph] - Extensão do PexGraph.
* Se tiver sugestões de outras ferramentas, envie para o assistente PAE.

== Recursos online ==

* Simulações Gerais - em cada página há sua descrição
** [http://www.ladamic.com/netlearn/NetLogo501/ErdosRenyiDegDist.html ErdosRenyiDegDist]
** [http://ccl.northwestern.edu/netlogo/models/GiantComponent GiantComponent]
** [http://www.ladamic.com/netlearn/NetLogo501/LatticePercolation.html LatticePercolation]
** [http://www.ladamic.com/netlearn/NetLogo501/ErdosRenyiTwoComponents.html ErdosRenyiTwoComponents]
** [http://www.ladamic.com/netlearn/nw/RandomGraphs.html RandomGraphs]
** [http://www.ladamic.com/netlearn/NetLogo501/RAndPrefAttachment.html RAndPrefAttachment]
** [http://www.ladamic.com/netlearn/GUESS/pagerank.html Pagerank]
** [http://www.ladamic.com/netlearn/NetLogo502/OpinionFormationModelToy.html OpinionFormationModelToy]
** [http://www.ladamic.com/netlearn/nw/Cliques.html Cliques]
** [http://www.ladamic.com/netlearn/NetLogo4/SmallWorldWS.html SmallWorldWS]
** [http://www.ladamic.com/netlearn/NetLogo4/SmallWorldSearch.html SmallWorldSearch]
** [http://www.ladamic.com/netlearn/nw/howwhysmallworlds.html HowWhySmallWorlds] 
** [http://spark-public.s3.amazonaws.com/sna/netlearn/NetLogo4/SmallWorldDiffusionSIS.html SmallWorldDiffusionSIS]
** [http://spark-public.s3.amazonaws.com/sna/netlearn/NetLogo502/GraphColoring.html GraphColoring] 
** [http://spark-public.s3.amazonaws.com/sna/netlearn/NetLogo502/CascadeModel.html CascadeModel]
** [http://spark-public.s3.amazonaws.com/sna/netlearn/NetLogo502/SmallWorldInnovation.html SmallWorldInnovation]