[Curso de AEeD - Aula 11] Tipos abstratos de dados



Ao estudar estrutura de dados uma das primeiras coisas que tropeçamos é na terminologia utilizada por profissionais da área. A seguir apresentaremos três termos que são muito utilizados e podem ser confundidos.

Algoritmo - Um algoritmo pode ser visto como uma seqüência de ações expressas em termos de uma linguagem de programação, constituindo parte da solução de um tipo determinado de problema. Ou seja, um algoritmo corresponde à descrição do padrão de comportamento associado aos elementos funcionais ativos de um processamento e deve ser expresso em termos de um conjunto finito de ações especificadas por meio de uma linguagem de programação.

Estrutura de dados - Na linguagem de programação adotada, estruturas de dados dão suporte à descrição dos elementos funcionais passivos do padrão de comportamento  acima referido, complementando o algoritmo que constitui parte da solução do problema considerado. Ambos, algoritmo e estruturas de dados, compõem o programa a ser executado pelo computador. Não é útil estudar estruturas de dados sem considerar os algoritmos básicos a elas associados. Da mesma forma, a escolha de um algoritmo depende, em geral, da estrutura de dados associada.

Programa - Um programa é uma formulação concreta, em termos de uma linguagem de programação, de um procedimento abstrato que atua sobre um modelo de dados também abstrato. Ambos, procedimento e modelo de dados, são representações abstratas de algoritmo e estruturas de dados, respectivamente, e não devem ser expressos em termos de uma linguagem de programação.


Tipos de dados

Em uma linguagem de programação, é importante classificar constantes, variáveis e valores gerados por expressões/funções de acordo com o seu tipo de dados. Um tipo de dados deve caracterizar o conjunto de valores a que uma constante pertence ou o conjunto de valores que pode ser assumido por uma variável ou gerado por uma expressão/função. 

Um tipo de dados elementar (ou simples) é caracterizado por um conjunto ¾ domínio ¾ de valores indivisíveis, tais como os definidos pelos tipos numeral, texto e símbolo da linguagem de programação Scheme. 

Um tipo de dados estruturado (ou complexo) define, em geral, uma coleção homogênea (de mesmo tipo) de valores elementares/estruturados ou um agregado de valores de tipos diferentes.


Tipo abstrato de dados


Abstraída qualquer linguagem de programação, um tipo abstrato de dados (TAD) pode ser visto como um modelo matemático que encapsula um modelo de dados e um conjunto de procedimentos que atuam com exclusividade sobre os dados encapsulados. Em nível de abstração mais baixo, associado à implementação, esses procedimentos são implementados por subprogramas denominados operações, métodos ou serviços.

Qualquer processamento a ser realizada sobre os dados encapsulados em um TAD só poderá ser executada por intermédio dos procedimentos definidos no modelo matemático do TAD, sendo esta restrição a característica operacional mais útil dessa estrutura.

 Nesses casos, um programa baseado em TAD deverá conter algoritmos e estruturas de dados que implementem, em termos da linguagem de programação adotada, os procedimentos e os modelos de dados dos TADs utilizados pelo programa.

Assim, a implementação de cada TAD pode ocupar porções bem definidas do programa: uma para a definição das estruturas de dados e outra para a definição do conjunto de algoritmos. Nessas condições, quaisquer alterações realizadas na estrutura de um dado TAD não afetarão as partes do programa que utilizam esse TAD.


Níveis de abstração 

Uma coleção de atividades, tais como inserir, suprimir e consultar, encapsulada junto com uma estrutura passiva, como um dicionário (conjunto de verbetes), pode ser considerada um tipo abstrato de dados (TAD). 

Definido dessa forma, o TAD DICIONÁRIO fica representado no nível de abstração mais alto possível: o nível conceitual. 

Em um nível de abstração mais baixo, denominado nível de design, a estrutura passiva deve ser representada por um modelo de dados (por exemplo: seqüência ou árvore binária de busca) e as operações devem ser especificadas através de procedimentos cuja representação não dependa de uma linguagem de programação. 

Em um nível de abstração ainda mais baixo, denominado nível de implementação, deve-se tomar como base o design do TAD e estabelecer representações concretas para os elementos de sua estrutura em termos de uma linguagem de programação específica. 

No exemplo do TAD DICIONÁRIO, se o design escolhido para a estrutura passiva for a árvore binária de busca, será possível implementar esse modelo de dados em Scheme, por exemplo, em termos de uma estrutura de dados do tipo lista correspondendo à representação prefixada (raiz sub-árvore-esquerda subárvore-direita). Os procedimentos serão implementados por meio dos algoritmos apropriados às operações raiz, esquerda, direita etc. utilizando-se os recursos disponíveis em Scheme para codificar estruturas ativas (operações e controle). As duas estruturas, a ativa e a passiva, do TAD poderão eventualmente constituir um encapsulamento (módulo) específico e identificável no programa construído.


Motivação do uso de TADs

Uma razão importante para programar em termos de TAD é o fato de que os elementos da estrutura passiva do TAD são acessíveis somente através dos elementos da estrutura ativa. 

No caso do TAD DICIONÁRIO, por exemplo, o acesso a qualquer elemento da estrutura de dados pode ocorrer apenas via os algoritmos correspondentes às operações inserir, eliminar e consultar. 

Essa restrição conduz a uma forma eficiente de programação defensiva, protegendo os dados encapsulados no TAD contra manipulações inesperadas por parte de outros algoritmos. 

Uma segunda razão, também importante, para programar em termos de TAD é o fato de que seu uso permite introduzir alterações nas estruturas definidas no nível de implementação ¾ visando, por exemplo, aumento de eficiência ¾ livre da preocupação de gerar erros no restante do programa. Tais erros não ocorrem porque a única conexão entre o TAD e o restante do programa é aquela constituída pela interface imutável dos algoritmos que implementam a estrutura ativa do TAD. 

Por fim, pode-se dizer que um TAD bem construído pode tornar-se uma porção de código confiável e genérica, permitindo e aconselhando seu reúso em outros programas. Dessa forma, aumenta-se a produtividade na construção de programas e, sobretudo, garante-se a qualidade dos produtos gerados



[Curso de AEeD - Aula 11] Tipos abstratos de dados [Curso de AEeD - Aula 11] Tipos abstratos de dados Reviewed by Vinicius dos Santos on 10:39:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!