If969  -­‐  Algoritmos  e  Estruturas  de  Dados  Centro  de  Informá-ca  Universidade  Federal  de  Pernambuco  Sistemas  de  Informação    Vinicius  Cardoso  Garcia  vcg@cin.ufpe.br    

©  2011  –  Vinicius  Cardoso  Garcia  

Missão  •  Mo-var,  apresentar,  exercitar  e  consolidar  o  uso  de  algoritmos  de  programação  e  estrutura  de  dados  para  a  resolução  de  problemas  computacionáveis  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

2  

Ementa  •  Ensinar  os  conceitos  básicos  de  algoritmos;  algoritmos  e  estruturas  de  dados  dinâmicas  básicas;  técnicas  de  construção  de  algoritmos;  conceitos  de  complexidade  de  algoritmos.  Este  curso  visa  trabalhar  principalmente  introdução  a  algoritmos  e  estruturas  de  dados,  incluindo  projeto,  análise  e  implementação  na  linguagem  Java.  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

3  

Obje<vo  Geral  da  Disciplina  •  Discu-r  técnicas  de  programação  e  estruturação  de  dados  para  o  desenvolvimento  de  programas  eficientes    

4  Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

Obje<vos  Específicos  da  Disciplina  •  Revisão  dos  conceitos  fundamentais  de  computação  e  linguagens  de  programação  –  Java  e  Python  

•  Resolução  de  problemas  por  meio  do  uso  de  construções  básicas  de  programação  

•  Solução  computacional  de  problemas  u-lizando  mecanismos  de  abstração  e  estruturação  

•  U-lização  de  -pos  de  dados  estruturados  na  solução  de  problemas  computacionais  

•  Inves-gação  de  algoritmos  de  pesquisa  e  ordenação  e  seus  usos  na  resolução  de  problemas  

•  Ives-gação  de  noções  de  complexidade  computacional  

5  Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

Programa  da  Disciplina  1.  Análise  de  Algoritmos  

a.  Análise  do  Pior  Caso;  b.  Notação  Assintó-ca;  

2.  Estruturas  de  Dados.    a.  Listas  ligadas:  simples,  duplas,  circulares;    b.  Alocação  dinâmica  de  memória;  c.  Pilhas,  Filas:  alocação  está-ca  e  dinâmica;  d.  Árvores:  binárias;    

i.  Construção  recursiva  de  árvores;  ii.  Caminhamento  em  árvores:  préfixo,  pósfixo  e  central;  

e.  Grafos:  orientados  e  não-­‐orientados;    f.  Aplicações.  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

6  

Programa  da  Disciplina  3.  Pesquisas  de  Dados.  

a.  Seqüencial  e  Binária;  b.  Árvores:  busca  (largura  e  profundidade),  inserção  e  

remoção;  balanceamento;  c.  Grafos:  busca,  árvore  geradora;    d.  Aplicações.  

4.  Conceitos  Básicos  de  NP-­‐Completude    a.  Problemas  NP-­‐completos;    b.  Redu-bilidade;    c.  Aplicações.  

5.  Projeto  Final  da  Disciplina  Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

7  

Infra-­‐estrutura  de  Apoio  •  Site  da  disciplina  – hhp://viniciusgarcia.  com/courses/if969  

•  Lista  de  Discussão  [google]  

•  Referências  Bibliográficas  – Cormen,  Thomas  H.;  Leiserson,  Charles  E.;  Rivest,  Ronaldo  L.;  Stein,  Clifford;  Introduc-on  to  Algorithms  -­‐  Third  Edi-on,  MIT  Press,  2009.  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

8  

Bibliografia  Complementar  •  Estruturas  de  Dados  e  Algoritmos  em  Java.  Michael  T.  

Goodrich  &  Roberto  Tamassia.  4ª  edição.  Ed.  Bookman,  2007  

•  TENENBAUM,  A.  M.;  LANGSAN,  Y.;  AUGENSTEIN,  M.  J.  Estruturas  de  Dados  Usando  C.  São  Paulo:  Makron  Books,  1995.  

•  ZIVIANI,  Nivio.  Projeto  de  Algoritmos.  Editora  Nova  Fronteira,  2004.  

•  SEDGEWICK,  Robert.  Algorithms  in  C++.  Addison  Wesley,  2000.  

•  MANBER,  Udi.  Introduc-on  to  Algorithms:  A  Crea-ve  Approach.  Addison  Wesley,  1989.  

•  SEDGEWICK,  Robert.  and  Flajolet,  Philippe.  An  Introduc-on  to  the  Analysis  of  Algorithms.  Addison  Wesley,  1996.  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

9  

Bibliografia  Complementar  •  Boas  prá-cas  – A.  Hunt,  D.  Thoma,.  The  Pragma-c  Programmer,  Addison  Wesley,  2000  

– A.  Oram,  G.  Wilson,  Beau-ful  Code,  O’Reilly,  2007  – R.  C.  Mar-n,  Clean  Code,  Pren-ce  Hall,  2009  – How  to  Think  Like  a  Computer  Scien-st  –  Python  Version      •  hhp://www.greenteapress.com/thinkpython/thinkCSpy  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

10  

SoGware  •  Python  versão  2.7.2  – hhp://www.python.org/download/  

•  Gedit  ou  IDLE  – hhp://www.python.org/cgi-­‐bin/moinmoin/PythonEditors  

•  Eclipse  – hhp://www.eclipse.org/downloads/  

•  Netbeans    – hhp://netbeans.org/downloads/index.html  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

11  

Avaliação  •  Lista  de  Exercício:  10%  nota  – 2.0  pts    

•  Prova:  65%  nota  –  (1º  E.E.)  8.0  pts  –  (2º  E.E.)  5.0  pts  

•  Projeto:  25%  nota  – 5.0  pts  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

12  

Sobre  as  ferramentas  •  O  curso  é  Algoritmos  e  Estrutura  de  Dados  •  Linguagem  de  programação  •  Normalmente  u-liza-­‐se  C/C++  •  Nós  vamos  u-lizar  Python  para  descrever  os  algoritmos  em  sala  e  Java  para  implementação  das  Listas  –  Python:  a  melhor  LP  para  ensino  de  algoritmos  –  Sem  burocracias  (declaração  de  variáveis,  de  classes,  etc)  que  desviam  do  foco  algoritmo  

–  Roda!  (nao  é  um  pseudo-­‐código),    –  Tem  vida  (um  grupo  forte  e  crescente  de  usuários)  –  Casos  de  sucesso:  hhp://www.python.org/about/success/  

Algoritmos  e  Estrutura  de  Dados  Apresentação  do  Curso  ©  2011  –  Vinicius  Cardoso  Garcia  

13