Resumo de Estruturas de Dados

Nesse post, irei citar o resumo que fiz, para a matéria de Estruturas de Dados, sendo que os temas abordados são os temas básicos da matéria de estruturas de dados.

Abordagens e trechos extraídos dos materiais seguintes:

Apostila Estrutura de Dados[ CAELUM ] – Todas apostilas que li até o momento são excelentes, portanto, recomendo!

Estruturas de Dados e Algoritmos[ Bruno R. Preiss – Elsevier ] – O livro é grande, mas bem explicativo e com vários exemplos.

1-      Algoritmo

Algoritmo, resumidamente, é um procedimento passo a passo para se chegar com sucesso a um fim. Em um algoritmo sempre haverá uma entrada, um processamento e uma saída. Informalmente, os algoritmos são processos, métodos ou funções, de “como” irá se comportar um programa.

2-      Análise de Algoritmos

Com algoritmos, podemos então, rodar em uma máquina para  ver se o resultado que ele irá apresentar é realmente, o resultado que se esperava. Observa-se então o comportamento do algoritmo. Porém, no caso geral, isto não é de muita utilidade, ou pode-se dizer que não é o suficiente. Tal comportamento observado fica muito restrito, pois se tem pouca informação.

A fim de ter uma maior compreensão sobre o algoritmo, pode-se então, analisá-lo. Ou seja, estudar as especificações do algoritmo e tirar conclusões sobre como a implementação daquele algoritmo irá se comportar em geral.

Itens que podem ser analisados seriam esses:

  • • tempo de processamento em função dos dados de entrada;
  • • espaço de memória total requerido para os dados;
  • • comprimento total do código;
  • • correta obtenção do resultado pretendido;
  • • robustez (como comporta-se com as entradas inválidas ou inesperadas).

3-      Complexidade

A medição de complexidade de algoritmo consiste na quantidade de trabalho necessário para a sua execução, sendo expressas em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados. Ao medir a complexidade, deve-se trabalhar lado a lado com a performance no sentido de escolher entre vários algoritmos o mais eficiente para se utilizar, desenvolver novos algoritmos para problema que já possuem solução, mas que se deve talvez ter um certo aprimoramento, para isso deve-se então, desenvolver algoritmos mais eficientes (melhorar/refatorar os algoritmos), devido ao aumento constante do volume de problemas a serem resolvidos.

A partir dessas medidas citadas, juntamente com parte computacional, pode-se então determinar se a implementação de determinado algoritmo é viável.

            Precisa-se definir alguma medida que expresse a eficiência do algoritmo. Costuma-se medir um algoritmo em termos de tempo de execução ou o espaço (ou memória) usado. Para o tempo, pode ser considerado o tempo absoluto (em minutos, segundos, etc.). Medir o tempo absoluto não é interessante por depender da máquina, por isso, em Análise de Algoritmos conta-se o número de operações consideradas relevantes realizadas pelo algoritmo e expressa-se esse número como uma função de n. Essas operações podem ser comparações, operações aritméticas, atribuições, etc.. Em ambos os casos, a complexidade é medida de acordo com o tamanho dos dados de entrada (N). Um dos fatores importantes no ato de medir a complexidade do algoritmo é o tempo de execução que depende de uma série de fatores, como:

 -Cresce com o tamanho da entrada.

-Afetado pelo hardware(SO, linguagem de programação, compilador, interpretador, etc..)

Ainda em complexidade e análise de algoritmos deve-se definir um conjunto de operações primitivas de alto nível que são independentes da linguagem de programação usada e podem ser identificadas no pseudocódigo (é uma forma genérica de escrever um algoritmo, utilizando uma linguagem simples) produzido. As seguintes operações estão incluídas entre as operações primitivas:

– atribuição de valores a variáveis

– chamadas de métodos

– operações aritméticas

– comparação de dois valores

– acesso a um Array/Arranjo

– seguir uma referência a um objeto, ou seja, acessar um objeto

– retorno de um método

                        Em complexidade existem 3 escalas de complexidade, á de Melhor caso, Caso médio e Pior caso. Em sequencia, elas tem relação ao resultado das funções obtidas através do análise de algoritmos relacionando as operações primitivas.

4-      Definição de Dados

Informalmente, uma informação armazenada em algum lugar, torna-se um

dado. Dado então é qualquer elemento identificado em sua forma bruta que, por si só, não conduz a uma compreensão de determinado fato, situação ou um comportamento.

5-      Tipo de Dados

Uma unidade básica de memória em um computador é chamada de bit( binary digit), sendo 0 e 1 usados para representar os dois possíveis estados de um bit. Uma memória do computador é constituída de uma grande quantidade de bits que, uma vez agrupados e devidamente interpretados, são capazes de representar uma enorme e variedade de informações.

Em um programa de computador, áreas de memória para armazenamento de dados são chamadas de variáveis. A forma como os bits numa variável são agrupados, interpretados e manipulados pelo computador é definida pelo seu tipo de dados.

Em outras palavras, um tipo de dado consiste da definição do conjunto de valores que uma variável pode assumir ao longo da execução de um programa e do conjunto de operações que podem ser aplicadas sobre ele.

Felizmente, as principais linguagens de programação oferecem uma grande variedade de tipos de dados, classificados em básicos e estruturados.

Os tipos de dados básicos, também conhecidos como tipos primitivos não possuem uma estrutura sobre seus valores, ou seja, não é possível decompor o tipo primitivo em partes menores. Portanto, os tipos básicos são indivisíveis. As principais linguagens de programação oferecem um elenco de tipos primitivos, como inteiro (para valores inteiros), real (para valores fracionários), lógico (para valores booleanos), etc..

Os tipos de dados estruturados permitem agregar mais do que um valor em uma variável, existindo uma relação estrutural entre seus elementos. As linguagens de programação oferecem mecanismos para estruturar dados complexos quando esses

dados são compostos por diversos campos. Os principais tipos de dados estruturados fornecidos pelas linguagens de programação são: arranjos(também denominados vetores e matrizes, utilizados para agregar componentes do mesmo tipo, com um tamanho máximo predefinido), registros (para agregar componentes de tipos diferentes).

Existem ainda os tipos de dados definidos pelo usuário. São também tipos de dados estruturados, construídos hierarquicamente através de atributos, os quais são de fato tipos de dados primitivos e/ou estruturados. Um tipo definido pelo usuário é constituído por um conjunto de atributos, que pode ser de tipos diferentes, agrupados sob um único nome. Normalmente, os elementos desse tipo estruturado têm alguma relação semântica.

6-      Variáveis e Constantes

Variáveis são representações simbólicas dos elementos de um certo conjunto. Cada variável corresponde a uma posição de memória como já citada em um trecho acima, cujo conteúdo pode ser alterado ao longo do tempo durante a execução de um algoritmo/programa. Embora uma variável possa assumir diferentes valores, ela só poderá armazenar apenas um valor a cada instante.

Constante é um valor fixo que não se modifica ao longo do tempo durante a execução de um algoritmo/programa. Conforme o seu tipo de dado, ela assumirá o seu elemento, e terá um mesmo valor sempre.

7-      Operações com Dados

As operações são utilizadas para representar expressões de cálculo, comparação, condição e atribuição. Temos os seguintes tipos de operadores: de atribuição, aritméticos, relacionais e lógicos. Os operadores de atribuição são utilizados para expressar o armazenamento de um valor em uma variável. Operadores aritméticos são utilizados para a realização dos diversos cálculos matemáticos. Por sua vez, os operadores relacionais são utilizados para estabelecer uma relação de comparação entre valores e expressão. O resultado dessa comparação é sempre um valor lógico que poderá assumir como verdadeiro(1) ou falso(0). E, os operadores lógicos são utilizados para concatenar ou associar expressões que estabelecem uma relação de comparação entre valores. O resultado dessas expressões é sempre o valor lógico (booleano) verdadeiro ou falso.

E, sem esquecer os operadores utilizados para medir a complexidade dos algoritmos que são os operadores primitivos, ao quais podem ser: Atribuição de valores a variáveis, chamadas de métodos, operações aritméticas, comparação de dois números , acesso a elemento de um array, ter/seguir uma instância de um objeto e o retorno de um método.

8-      Tipos de Dados Abstratos

 O tipo de dados abstrato é um modelo matemático definido por um conjunto de valores e por um conjunto de operadores que atuam sobre esses valores. Quando empregados para a solução de problemas por computador, TDAs servem tanto para especificar características relevantes das entidades envolvidas nos problemas, quanto para definir que forma elas se relacionam entre si e como podem ser manipuladas. A especificação de um TAD corresponde à escolha de uma boa maneira de armazenar os dados e à definição de um conjunto adequado de operações para atuar sobre eles.

A característica essencial de um TAD é a separação entre conceito e implementação, ou seja, existe uma distinção entre a definição do tipo e a sua representação, e a implementação das operações. Um TAD é, portanto, uma forma de definir um novo tipo de dados juntamente com as operações que manipulam esse novo tipo de dados.

Anúncios

Obrigado pelo comentário.

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s