Mudanças entre as edições de "Tecnicas Computacionais"

De Pontão Nós Digitais
(versao 1)
 
(→‎Tarefa 10 - Prova Mestrado)
 
(66 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 1: Linha 1:
−
== Tecnicas Computacionais ==
+
Esta é a pagina principal de um curso de tecnicas computacionais sendo ministrado em 2019 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, principalmente nos campos de computacao cientifica e multimidia (jogos, simuladores,etc). Trata-se de uma disciplina de nivelamento. Disciplinas mais avancadas sao tratadas em [[PP]].
 +
[[Imagem:Hacking-keyboard.gif|right|360px]]
  
 +
== Informacoes Gerais ==
 +
* Instrutor: prof. [http://rfabbri.github.io Ricardo Fabbri]
 +
* Periodo: 1o. Semestre de 2019, voltado ao 1o. periodo do Mestrado em Modelagem Computacional - Capes 6
 +
* Horario: Tercas e Quintas, 9:40-11:30am, sala 206. '''Reposicao: 29Abr19, 20Mai19, 8Jul19, todos M3-M6 (8:50-12:20) sala 110'''
 +
* Lista de emails: [https://groups.google.com/forum/#!aboutgroup/iprj-tc-2019 <tt>iprj-tc-2019@googlegroups.com</tt>]
  
−
=== Palavras-Chave ===
+
=== Pre-requisitos ===
−
Programacao, Computacao Cientifica, linguagem C, algoritmos e estruturas de dados
+
* Teorico: Nenhum. Familiaridade com programacao sera assumida. Porem, trata-se de um curso intensivo.
 +
* Pratico: Linux devera ser instalado no computador do aluno. Ajuda devera ser procurada com o professor.
 +
 
 +
== Conteudo aproximado ==
 +
== Recursos Principais ==
 +
=== Bibliografia ===
 +
[[Imagem:C-book-v2.jpg|right|thumb|none|Principal livro texto [https://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628 K&R]]]
 +
==== Livros Principais ====
 +
* Parte 1: [https://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628 The ANSI-C programming language, de Kernighan & Ritchie ]
 +
* Parte 2: "Algorithm Design" - Jon Kleinberg & Eva Tardos http://www.aw-bc.com/info/kleinberg/assets/images/cover.jpg
 +
** 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]
 +
 
 +
==== Outros Livros ====
 +
 
 +
=== 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://sourceforge.net/p/labmacambira/utils/ci/master/tree/templates/topcoder/a.cc
 +
* 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  ===
 +
Os seguintes videos sao versoes resumidas do conteudo tratado em aula e nao substituem as aulas.
 +
* https://www.youtube.com/watch?v=Gru0DnXWr0g
 +
* https://www.youtube.com/watch?v=k0KfKildD-U
 +
Slides
 +
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qyQTZ4RE1hd3ZSX2c busca em grafos]
 +
 
 +
=== Provas ===
 +
*P1: 6Jun19 [https://drive.google.com/open?id=1eUQsqWmiLg-VkY9ZeypLb2cvb85x9Wal (pdf)]
 +
*P2: 11Jul19
 +
 
 +
== Recursos adicionais ==
 +
== Tarefas ==
 +
'''Somente serao aceitos arquivos eletronicos no formato PDF'''
 +
 
 +
Todo material submetido eletronicamente deve ser enviado ao email do professor, com a string "<tt>[iprj-tc]</tt>" no subject do email. Voce devera receber uma confirmacao automatica.
 +
 
 +
A cada data de entrega (exceto a primeira tarefa) ate 3 alunos serao sorteados para apresentar.
 +
 
 +
 
 +
 
 +
=== Tarefa 1: Entrega dia 4/Abril/2019 ===
 +
* K&R 1-1, 1-4, 1-5 (se conseguir Tarefa 2 completa, ganha 10 nesta sem precisar fazer)
 +
 
 +
=== Tarefa 2: Entrega dia 9/Abril/2019 ===
 +
* K&R 1-13 (horizontal), 1-13 (vertical)
 +
 
 +
=== Tarefa 3: Entrega dia 11/Abril/2019 ===
 +
* K&R 1-17, 1-19
 +
 
 +
=== Tarefa 4: Entrega dia 16/Abril/2019 ===
 +
* K&R 1-20, 1-21, 1-23 (se fizer apenas 1-23 ja ganha 10).
 +
 
 +
=== Tarefa 5: Inversao de matrizes, Entrega dia 25/Abril/2019 ===
 +
* Dada uma matriz nxn, com n <= 4, calcule sua inversa de forma explicita
 +
* Bonus: utilize uma biblioteca e compare a velocidade com seu proprio codigo
 +
 
 +
=== Simulado presencial: 30/Abril/2019 ===
 +
* Dois dos exercicios das tarefas 1-4
 +
* Em laboratorio (nao usando computador do aluno)
 +
 
 +
=== Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA) ===
 +
* Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',
 +
e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.
 +
* A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
 +
* Sera dado um grande bonus.
 +
 
 +
    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa  a
 +
    8  8              8              8          8                  8  8
 +
    8  8  aaaaaaaaa  8  aaaaa  aaaa8aaaa  aaaa8  aaaaa  aaaaa  8  8
 +
    8              8      8  8          8          8  8  8      8  8
 +
    8aaaaaaaa  a  8aaaaaaa8  8aaaaaaaa  8aaaa  a  8  8  8aaaaaaa8  8
 +
    8      8  8              8          8  8  8  8  8          8  8
 +
    8  a  8aaa8aaaaaaaa  a  8  aaaaaaaa8  8aaa8  8  8aaaaaaaa  8  8
 +
    8  8              8  8  8      8          8          8      8  8
 +
    8  8aaaaaaaaaaaa  8aaa8  8aaaa  8  aaaaa  8aaaaaaaa  8  aaaa8  8
 +
    8          8      8  8      8  8      8          8  8          8
 +
    8  aaaaa  8aaaa  8  8aaaa  8  8aaaaaaa8  a  a  8  8aaaaaaaaaaa8
 +
    8      8      8  8  8      8      8      8  8  8      8      8
 +
    8aaaaaaa8aaaa  8  8  8  aaaa8aaaa  8  aaaa8  8  8aaaa  8aaaa  8
 +
    8          8  8          8      8  8      8  8      8          8
 +
    8  aaaaa  8  8aaaaaaaa  8aaaa  8  8aaaa  8aaa8  aaaa8aaaaaaaa  8
 +
    8  8      8          8          8      8  8  8              8  8
 +
    8  8  aaaa8aaaa  a  8aaaa  aaaa8aaaa  8  8  8aaaaaaaaaaaa  8  8
 +
    8  8          8  8  8  8  8          8              8  8      8
 +
    8  8aaaaaaaa  8  8  8  8aaa8  8aaaaaaa8  aaaaaaaaa  8  8aaaaaaa8
 +
    8  8      8  8  8          8          8  8      8              8
 +
    8  8  aaaa8  8aaa8  aaaaa  8aaaaaaaa  8aaa8  a  8aaaaaaaa  a  8
 +
    8  8                  8          8              8              8  8
 +
    8  8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8
 +
 
 +
=== Tarefa 6: Estruturas de dados basicas 23Mai19 ===
 +
* Entrada
 +
** Digite o tipo de implementacao de lista: (1) Encadeada (2) Duplamente encadeada (3) Buffer circular
 +
** Para cada opcao: digite (i) para inserir (d) deletar. Para cada dessas opcao: escolher posicao para inserir e posicao para deletar
 +
** As listas sao todas de strings
 +
** Nao pode ser usada STL, mas bonus sera dado a quem comparar com STL.
 +
 
 +
==== Tarefa 7 - Busca Binaria 30Mai19 ====
 +
* Implementar busca binaria de um vetor ordenado de floats
 +
* Utilizar apenas linguagem C e sua propria implementacao
 +
* Bonus: implementar em C++ usando a biblioteca padrao
 +
 
 +
==== Tarefa 8 - Ordenacao 6Jun19 ====
 +
* Implementar o mergesort, o quicksort e o insertion sort
 +
* Plotar grafico do tempo de execucao minimo, maximo, e medio para diferentes tamanhos de entradas aleatoreas
 +
==== Tarefa 9 - P1 resolvida 18Jun19 ====
 +
* Entregar sua implementação da P1, funcionando (compilando e executando, conforme especificado em aula).
 +
 
 +
==== Tarefa 10 - Prova Mestrado 9Jul19 ====
 +
* Entregar sua implementação da prova de técnicas computacionais (qualify).
 +
 
 +
==== Lista de exercicios para a P1 (sem entrega) ====
 +
* Exercicios de ponteiros: https://www.geeksforgeeks.org/c-language-2-gq/pointers-gq/
 +
** Fazer todos exercicios
 +
** Nao precisa entregar - mas cai na prova uma questao parecida com estes
 +
** Sera permitido descartar as questoes com termos nao vistos em aula.
 +
* Todos do K&R cap 1 e secoes relevantes cap 2-6 vistas em aula (quase tudo)
 +
* Todas tarefas ate tarefa 7
 +
* Garantido cair uma questao da tarefa 6
 +
* Demais exercicios podem ser sobre todo conteudo dado em aula
 +
** Praticar implementar algoritmos dados em 23Maio19
 +
*** Insercao em vetor ordenado
 +
*** Merge de dois vetores ordenados
 +
*** Particao de um vetor em elementos menores e maiores que um dado valor t
 +
 
 +
<!--
 +
=== Outras tarefas (ainda nao agendadas) ===
 +
==== Tarefa - Eliminacao de Gauss ====
 +
* Implementar Eliminacao de Gauss para resolver um sistema quadrado Ax = b
 +
* Formato: double
 +
* Bonus: o codigo mais rapido da turma para uma matriz 10x10 ganhara +1 ponto na media
 +
* Grupos de ate 2 alunos
 +
* Assumir A inversivel
 +
-->
 +
 
 +
=== Bonus ===
 +
==== Bonus FriScience ====
 +
==== Bonus Vim/Emacs ====
 +
* Aluno que aprender ou ja souber editores de programador Vim/Emacs
 +
* Aluno que entregar tarefas em Latex.
 +
 
 +
== Criterio de Avaliacao ==
 +
  M_p = (P1 + P2)/2 
 +
  M = 0.7*M_p + 0.3*T
 +
 
 +
== Palavras-Chave ==
 +
Programacao, Computacao Cientifica, Linguagem C, Algoritmos e Estruturas de Dados para Pos Graduacao
 
[[Category:Lab Macambira]] [[Category:IPRJ]] [[Category:Redes]]
 
[[Category:Lab Macambira]] [[Category:IPRJ]] [[Category:Redes]]

Edição atual tal como às 19h24min de 17 de julho de 2019

Esta é a pagina principal de um curso de tecnicas computacionais sendo ministrado em 2019 no IPRJ/UERJ, de utilidade geral para a formacao de programadores de nivel intermediario e avancado, principalmente nos campos de computacao cientifica e multimidia (jogos, simuladores,etc). Trata-se de uma disciplina de nivelamento. Disciplinas mais avancadas sao tratadas em PP.

Hacking-keyboard.gif

Informacoes Gerais

  • Instrutor: prof. Ricardo Fabbri
  • Periodo: 1o. Semestre de 2019, voltado ao 1o. periodo do Mestrado em Modelagem Computacional - Capes 6
  • Horario: Tercas e Quintas, 9:40-11:30am, sala 206. Reposicao: 29Abr19, 20Mai19, 8Jul19, todos M3-M6 (8:50-12:20) sala 110
  • Lista de emails: iprj-tc-2019@googlegroups.com

Pre-requisitos

  • Teorico: Nenhum. Familiaridade com programacao sera assumida. Porem, trata-se de um curso intensivo.
  • Pratico: Linux devera ser instalado no computador do aluno. Ajuda devera ser procurada com o professor.

Conteudo aproximado

Recursos Principais

Bibliografia

Principal livro texto K&R

Livros Principais

Outros Livros

Top Coder

Aulas

Os seguintes videos sao versoes resumidas do conteudo tratado em aula e nao substituem as aulas.

Slides

Provas

  • P1: 6Jun19 (pdf)
  • P2: 11Jul19

Recursos adicionais

Tarefas

Somente serao aceitos arquivos eletronicos no formato PDF

Todo material submetido eletronicamente deve ser enviado ao email do professor, com a string "[iprj-tc]" no subject do email. Voce devera receber uma confirmacao automatica.

A cada data de entrega (exceto a primeira tarefa) ate 3 alunos serao sorteados para apresentar.


Tarefa 1: Entrega dia 4/Abril/2019

  • K&R 1-1, 1-4, 1-5 (se conseguir Tarefa 2 completa, ganha 10 nesta sem precisar fazer)

Tarefa 2: Entrega dia 9/Abril/2019

  • K&R 1-13 (horizontal), 1-13 (vertical)

Tarefa 3: Entrega dia 11/Abril/2019

  • K&R 1-17, 1-19

Tarefa 4: Entrega dia 16/Abril/2019

  • K&R 1-20, 1-21, 1-23 (se fizer apenas 1-23 ja ganha 10).

Tarefa 5: Inversao de matrizes, Entrega dia 25/Abril/2019

  • Dada uma matriz nxn, com n <= 4, calcule sua inversa de forma explicita
  • Bonus: utilize uma biblioteca e compare a velocidade com seu proprio codigo

Simulado presencial: 30/Abril/2019

  • Dois dos exercicios das tarefas 1-4
  • Em laboratorio (nao usando computador do aluno)

Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA)

  • Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',

e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.

  • A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
  • Sera dado um grande bonus.
   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa   a
   8   8               8               8           8                   8   8
   8   8   aaaaaaaaa   8   aaaaa   aaaa8aaaa   aaaa8   aaaaa   aaaaa   8   8
   8               8       8   8           8           8   8   8       8   8
   8aaaaaaaa   a   8aaaaaaa8   8aaaaaaaa   8aaaa   a   8   8   8aaaaaaa8   8
   8       8   8               8           8   8   8   8   8           8   8
   8   a   8aaa8aaaaaaaa   a   8   aaaaaaaa8   8aaa8   8   8aaaaaaaa   8   8
   8   8               8   8   8       8           8           8       8   8
   8   8aaaaaaaaaaaa   8aaa8   8aaaa   8   aaaaa   8aaaaaaaa   8   aaaa8   8
   8           8       8   8       8   8       8           8   8           8
   8   aaaaa   8aaaa   8   8aaaa   8   8aaaaaaa8   a   a   8   8aaaaaaaaaaa8
   8       8       8   8   8       8       8       8   8   8       8       8
   8aaaaaaa8aaaa   8   8   8   aaaa8aaaa   8   aaaa8   8   8aaaa   8aaaa   8
   8           8   8           8       8   8       8   8       8           8
   8   aaaaa   8   8aaaaaaaa   8aaaa   8   8aaaa   8aaa8   aaaa8aaaaaaaa   8
   8   8       8           8           8       8   8   8               8   8
   8   8   aaaa8aaaa   a   8aaaa   aaaa8aaaa   8   8   8aaaaaaaaaaaa   8   8
   8   8           8   8   8   8   8           8               8   8       8
   8   8aaaaaaaa   8   8   8   8aaa8   8aaaaaaa8   aaaaaaaaa   8   8aaaaaaa8
   8   8       8   8   8           8           8   8       8               8
   8   8   aaaa8   8aaa8   aaaaa   8aaaaaaaa   8aaa8   a   8aaaaaaaa   a   8
   8   8                   8           8               8               8   8
   8   8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8

Tarefa 6: Estruturas de dados basicas 23Mai19

  • Entrada
    • Digite o tipo de implementacao de lista: (1) Encadeada (2) Duplamente encadeada (3) Buffer circular
    • Para cada opcao: digite (i) para inserir (d) deletar. Para cada dessas opcao: escolher posicao para inserir e posicao para deletar
    • As listas sao todas de strings
    • Nao pode ser usada STL, mas bonus sera dado a quem comparar com STL.

Tarefa 7 - Busca Binaria 30Mai19

  • Implementar busca binaria de um vetor ordenado de floats
  • Utilizar apenas linguagem C e sua propria implementacao
  • Bonus: implementar em C++ usando a biblioteca padrao

Tarefa 8 - Ordenacao 6Jun19

  • Implementar o mergesort, o quicksort e o insertion sort
  • Plotar grafico do tempo de execucao minimo, maximo, e medio para diferentes tamanhos de entradas aleatoreas

Tarefa 9 - P1 resolvida 18Jun19

  • Entregar sua implementação da P1, funcionando (compilando e executando, conforme especificado em aula).

Tarefa 10 - Prova Mestrado 9Jul19

  • Entregar sua implementação da prova de técnicas computacionais (qualify).

Lista de exercicios para a P1 (sem entrega)

  • Exercicios de ponteiros: https://www.geeksforgeeks.org/c-language-2-gq/pointers-gq/
    • Fazer todos exercicios
    • Nao precisa entregar - mas cai na prova uma questao parecida com estes
    • Sera permitido descartar as questoes com termos nao vistos em aula.
  • Todos do K&R cap 1 e secoes relevantes cap 2-6 vistas em aula (quase tudo)
  • Todas tarefas ate tarefa 7
  • Garantido cair uma questao da tarefa 6
  • Demais exercicios podem ser sobre todo conteudo dado em aula
    • Praticar implementar algoritmos dados em 23Maio19
      • Insercao em vetor ordenado
      • Merge de dois vetores ordenados
      • Particao de um vetor em elementos menores e maiores que um dado valor t


Bonus

Bonus FriScience

Bonus Vim/Emacs

  • Aluno que aprender ou ja souber editores de programador Vim/Emacs
  • Aluno que entregar tarefas em Latex.

Criterio de Avaliacao

 M_p = (P1 + P2)/2   
 M = 0.7*M_p + 0.3*T

Palavras-Chave

Programacao, Computacao Cientifica, Linguagem C, Algoritmos e Estruturas de Dados para Pos Graduacao

Disponível em "http://wiki.nosdigitais.teia.org.br/index.php?title=Tecnicas_Computacionais&oldid=40965"