10jun98 13jun98 14jun98

====

MAC 324 - Estruturas de Dados para Engenharia

Aula especial sobre

  Grafos e Ordenação Topológica

  Demo de Animação de Algoritmos

  Parafernália Eletrônica Usada na Apresentação
  
====

Grafos e ordenação topológica

  grafos : exemplos e representações

  caminhos mínimos

  ordenação topológica
  
    definição do problema

    exemplos de ordenação topológica

    quando a ordenação topológica é possível?

    as estruturas de dados
    
    os algoritmos

    demonstração do programa Java

    sobre o programa de demonstração

====

Ordenação Topológica

Referência para as estruturas de dados e algoritmos

N. Wirth
Algorithms + Data Strucures = Programs
Prentice Hall,Englewood Cliffs, NJ, 1976
páginas 182 a 189

====

Demo de  animação de algoritmos

  splay trees

  algoritmos de ordenação

  animação de algoritmos
  
====

Parafernália Eletrônica Usada na Apresentação

Adicionar na página de recursos:

Hardware

  Scanner UMAX Astra 610S

Software

  Presto PageManager 2.30
  NewSoft Technology Corp. 1997

  PaintShop Pro 4.14 Shareware
  Jasc Inc. 1991-1997

====

Splay Trees

Splay trees são árvores binárias de busca que a cada operação sofrem um
rearranjo de modo que o último elemento consultado passa a ocupar a raíz da
árvore.

Com isto os elementos mais recentemente consultados tendem a ficar perto da
raiz.

O rearranjo é feito por sequências de rotações de três tipos (dois deles são
as rotações de árvores AVL).

A propriedade notável das Splay Trees é que apesar de não haver qualquer
critério de balanceamento, demonstra-se que o tempo médio (amortizado) de m
operações, iniciadas numa árvore vazia, que envolvem n elementos, é O(m*log
n).

Uma boa fonte de referências é

H.R. Lewis and L. Denenberg
Data Structures & Their Algorithms
HarperCollins, NY, 1991
páginas 243 a 256

A animação se encontra em: http://gs213.sp.cs.cmu.edu/cgi-bin/splay

====

seguem as páginas ~is/ddt/mac324/ordtop/ld*.jpg

====

Demonstração de algoritmos de ordenação:

http://www.mcs.csuhayward.edu/~simon/handouts/sort/SortDemo.html

====

Grafos: vértices e arestas

as arestas podem ser orientadas ou não

====

Exemplos de grafos

  o cubo : 6 faces quadradas
ligar cópia de   http://www.ime.usp.br/~is/ddt/mac324/ordtop/cubo.jpg

  o dodecaedro : 12 faces pentagonais
ligar cópia de   http://www.ime.usp.br/~is/ddt/mac324/ordtop/dode.jpg

  um mapa de estradas
ligar cópia de   http://www.ime.usp.br/~is/ddt/mac324/ordtop/mapa.jpg

  esquema de um circuito elétrico

  um documento em hipertexto

  uma rede de computadores

  árvores = grafos conexos sem circuitos

  a teia WWW

====

Caminhos mínimos

  O algoritmo de Dijkstra encontra a distância de cada vértice do grafo a
  partir de uma origem comum.

  ligar, na sequência,  cópias dos arquivos:
  http://www.ime.usp.br/~is/ddt/mac324/ordtop 

-rw-r--r--   1 is       mac         35834 Jun 14 18:17 cubod100.jpg
-rw-r--r--   1 is       mac         90000 Jun 14 18:20 doded100.jpg

-rw-r--r--   1 is       mac         51240 Jun 14 18:18 d01-09.jpg
-rw-r--r--   1 is       mac         55454 Jun 14 18:18 d10-16.jpg
-rw-r--r--   1 is       mac         38208 Jun 14 18:18 d17-22.jpg
-rw-r--r--   1 is       mac         49479 Jun 14 18:19 d23-33.jpg

-rw-r--r--   1 is       mac         45265 Jun 14 18:19 de01-12.jpg
-rw-r--r--   1 is       mac         82052 Jun 14 18:19 de13-33.jpg

====

Formato .pdf da Adobe Acrobat

PDF = Portable Document Format

funcionalidade parecida com html
formato proprietário mas aberto (?) da Adobe
browser é Acrobat Reader, disponível em todas as plataformas
ferramentas de autoria devem ser compradas: Adobe Exchange & família

.pdf

  PostScript (da Adobe)

    LaTeX
    ASCII
    formatadores
    desenhadores (AutoCAD, etc.)
    
  Encapsulated PostScript

  Word da Microsoft

  PageMaker da Adobe

    publicações eletrônicas

  Photoshop da Adobe

    fotografias digitais

  formatos gráficos: gif, jpg, bitmap, etc.

    documentos escaneados

    software gráfico

  pode incorporar som e video

====

Algumas características do formato .pdf


rico repertório visual

grande flexibilidade de incorporação de documentos

forte fidelidade gráfica 

hipertexto

multimídia

texto indexável

permite montar e administrar bibliotecas de documentos

tamanho modesto, usa compressão

visível de qualquer plataforma

acoplado à teia mundial (permite publicação)

controle de acesso aos documentos

Referência:

Adobe Acrobat 3.0
Classroom in a book
Adobe Press, San Jose, CA, 1997

====