Departamento de Electrónica, Telecomunicações e Informática

Algoritmos e Complexidade - Aulas Práticas

A componente prática da disciplina é composta por uma aula de 2h. As aulas práticas permitem desenvolver, implementar e testar diferentes algoritmos, estruturas de dados e tipos de dados abstratos, permitindo a aplicação e a exploração das matérias ensinadas nas aulas teóricas. É usada a linguagem de programação C.

O Guião das Aulas Práticas só está disponível em formato de papel na portaria do DETI

Aulas nº 1, nº 2, nº 3 e nº 4 - Análise Empírica da Complexidade de Algoritmos

 

Aulas nº 5 e nº 6 - Tipos de Dados Abstratos Simples Baseados em Arrays  e Listas

  • Tipo de dados abstrato Fraction

           Interface  fullfraction.h      Implementação  fullfraction.c      Makefile mkfraction

           Programa gráfico de simulação simfraction.c      English simulation program engsimfraction.c

  • Tipo de dados abstrato Egyptian Fraction

           Interface  egyptianfraction.h      Makefile mkegyptian

           Programa gráfico de simulação simegyptian.c      English simulation program engsimegyptian.c

           Versão estática com array     Implementação  arrayegyptianfraction.c

           Versão dinâmica com lista ligada     Implementação  listegyptianfraction.c

 

Aulas nº 7 e nº 8 - Recursividade

  • Aula nº7 - programa de teste - aula7.c

  • Aula nº8 - programa de teste - aula8.c

 

Filas e Pilhas

  • Fila dinâmica genérica                     Interface  queue.h       Implementação  queue.c

  • Pilha dinâmica genérica                   Interface  stack.h        Implementação  stack.c

 

Aulas nº 9 e nº 10 - Árvores ABP

  • TDA Fraction simplificado             Interface  fraction.h        Implementação fraction.c

  • Programa de teste  testfraction.c     Makefile  mktest

  • Árvore Binária de Pesquisa             Interface  abp.h       Implementação  abp.c      Makefile  mkabpfraction

  • Programa de teste das funções fornecidas   testabp.c      Árvores  abp0.txt   abp1.txt  abp2.txt

  • Árvore Binária de Pesquisa de Inteiros             Interface  intabp.h       Implementação  intabp.c

  • Programa que simula a inserção e a remoção de elementos numa ABP  simabp.c     Makefile  mkabp

 

Árvores AVL

  • Árvore Adelson-Velskii Landis      Interface  avl.h       Implementação avl.c

  • Programa que simula a inserção de elementos numa AVL  simavl.c     Makefile  mkavl

 

Aula nº 11 - Filas com Prioridade

  • Fila com Prioridade orientada aos máximos            Interface  pqueue.h       Implementação  pqueue.c

  • Programa de teste  testpqueue.c      Programa de simulação gráfica  simpqueue.c            Makefile mkpqueue

 

Aulas nº 12 e nº 13 - Grafos

  • Tipo de dados abstrato Dígrafo/Grafo              Interface  digraph.h        Implementação  digraph.c

  • Programa de simulação  simdigraph.c      English simulation program engsimdigraph.c         Makefile  mkdigraph

  • Fila dinâmica genérica para o Dígrafo                Interface  queuedig.h       Implementação  queuedig.c

  • Dígrafos para simular os algoritmos (Simulation Digraphs)   digrafo5.txt    digrafo6.txt

  • Programa para testar o trabalho (Test Program)    testdigraph.c

  • Resultados do programa de teste para o dígrafo 5 (Result for digraph 5)  result.txt