Trabalho De Estrutura De Dados

FACULDADE DE TECNOLOGIA DE TAQUARITINGA

TRABALHO DE ESTRUTURA DE DADOS

TAQUARITINGA

2012

THALES CESAR DEL VECCHIO DA SILVA

TRABALHO DE ESTRUTURA DE DADOS

Trabalho desenvolvido durante a disciplina de Estrutura de Dados, como parte de avaliação referente ao 2º Bimestre de 2012.

Professor: Fabio Takeda

TAQUARITINGA

2012

SUMÁRIO

1 RESUMO DE MÉTODOS DE ORDENAÇÃO 4

1.1 BUBBLE SORT 4

1.2 INSERTION SORT 4

1.3 MERGE SORT 4

1.4 HEARPSORT 4

1.5 QUICK SORT 5

2 RESUMO DE ÁRVORES BINÁRIAS E AVL 5

3 RESUMO DE ÁNALISE DE COMPLEXIDADE DE ALGORITMO 6

4 RESUMO DE RECURSIVIDADE 7

REFERÊNCIAS 9

1 RESUMO DE MÉTODOS DE ORDENAÇÃO

1.1 BUBBLE SORT

Por ser simples e fácil de entender e implementar, o Bubble Sort está entre os mais conhecidos algoritmos de ordenação. Porém, devido a sua baixa eficiência, devemos tratá-lo como uma solução mais para desenvolvimento de raciocínio que de uso recorrente (embora não seja um problema usá-lo em casos onde não exige muita performance, como quando desejamos ordenar um conjunto com poucos elementos).

Seu princípio é a comparação e troca de valores entre posições consecutivas, fazendo com que os valores mais altos (ou mais baixos) migrem (“borbulhem”)para o final do vetor a ser ordenado.

1.2 INSERTION SORT

O insertion sort faz o que propõe, ordena uma sequência inserindo os registros onde for conveniente para manter a ordenação. Um exemplo clássico disso é a ordenação de uma sequência de cartas nas mãos de um jogador. Funciona assim: temos uma pilha de cartas de onde vamos tirando carta por carta, cada vez que uma carta é tirada ela é comparada às outras cartas que já estão na mão do jogador, e é inserida em seu devido lugar. Desta forma é possível obtermos uma sequência ordenada de cartas na mão.

1.3 MERGE SORT

Este método baseia-se na estratégia do dividir para conquistar. A sua ideia é dividir o vetor em duas partes iguais, até que resultem dois vetores com apenas um único elemento.

1.4 HEARPSORT

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção.

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espetacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grande, o termo lg n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

1.5 QUICK SORT

O quick sort é um dos algoritmos de ordenação mais simples e eficientes que existem. O seu principio é muito semelhante ao merge sort. Primeiro a lista a ordenar é partida em duas partes, de maneira a que os elementos primeira parte sejam menores ou iguais a todos os elementos da segunda. Recursivamente, as duas partes são ordenadas pelo mesmo algoritmo e são então combinadas para dar a lista final. O primeiro passo é escolher um elemento x e depois dividir. A ideia usada neste algoritmo também é a dividir para conquistar.

2 RESUMO DE ÁRVORES BINÁRIAS E AVL

Árvores são Estruturas de Dados que combinam as vantagens de duas outras estruturas: Uma Lista Encadeada e um Array Ordenado. A Árvore pode fazer inserções e deleções tão rápido quanto uma Lista Encadeada, e também pode fazer buscas tão rápidas quanto um Array Ordenado.

Inserção e Deleção em Arrays Ordenados. A inserção e deleção em Arrays Ordenados são lentas porque é necessário que todos os elementos que são maiores que o elemento a ser inserido seja movido adiante, até que exista um espaço para ser inserido o elemento em sua posição correta. De modo análogo para a operação de deleção, onde todos os elementos maiores que o elemento eliminado tem que ser movidos para trás em uma posição.

Buscas em Listas Encadeadas as buscas em Listas Encadeadas tem que ser feitas do inicio da lista, e então, visitar todos os elementos a procura do elemento desejado.

Esse processo é lento, pois são necessárias, em média, de N/2 comparações (considerando N o número o de elementos da lista).

Definições: Nó: Entes da árvore que contém além dos dados que se quer armazenar ponteiros pra outros entes;

Raiz: É o primeiro Nó da Árvore, que se encontra sempre no topo da mesma;

Folha: É o Nó que não possui filhos;

Pai: É o Nó imediatamente superior. Todos os elementos, exceto a Raiz, possuem um Pai;

Filho: São os Nós imediatamente inferiores;

Sub-árvore: Qualquer Nó pode ser Raiz. Uma Subárvore é qualquer árvore cuja

Raiz é um Nó de uma árvore maior ou igual a ela;

Níveis: É a referência a quantidade de gerações do nó comparados a Raiz da árvore;

Árvore Binária: São árvores que possuem apenas dois filhos, um a esquerda e outro a direita.

Construção da Árvore Binária: Primeiramente, um Array é considerado afim de armazenar a freqüência com que os caracteres aparecem no texto do arquivo. Ao percorrer todo o arquivo, estas informações são armazenadas no Array supracitado e é a partir daí que a construção da árvore binária ocorre de fato.

O próximo passo é verificar as duas menores freqüências dentro do Array. Elas serão consideradas folhas da árvore (bem como o próprio caracter que possui tal frequência) e a soma de suas frequências serão consideradas seus pais. Essa soma é armazenada em posições finais do Array em questão. É interessante salientar que o algoritmo passa a desprezar as folhas criadas, o que é um fator positivo no ponto de vista da eficiência do mesmo.

O passo acima é repetido considerando os outros elementos do Array bem como a soma de frequências criada anteriormente. As árvores AVL, cujo nome foi obtido a partir das iniciais de seus criadores russos – Adel’son-Vel’skii e Landis, são uma implementação de um algoritmo para a criação de árvores binárias balanceadas.

Uma vez que foi detectado o desbalanceamento da árvore após uma inserção, e que foi determinado o nodo pivô (onde o valor absoluto de FB é maior que 1), passamos para a realização do procedimento de balanceamento da árvore. Este procedimento consiste primeiramente de determinar em qual dos seguintes tipos de casos nos enquadramos:

Tipo I: Se a sub-árvore esquerda é maior que a sub-árvore direita (FB > 1)

E a sub-árvore esquerda desta sub-árvore esquerda é maior que a sub-árvore direita dela

Então realizar uma rotação simples para a direita;

Tipo II: Se a sub-árvore esquerda é maior que a sub-árvore direita (FB > 1)

E a sub-árvore esquerda desta sub-árvore esq. é menor ou igual que a sub-árvore direita

Então realizar uma rotação dupla para a direita;

Tipo III: Se a sub-árvore esquerda é menor que a sub-árvore direita (FB < -1)

3 RESUMO DE ÁNALISE DE COMPLEXIDADE DE ALGORITMO

Muitas vezes lemos e ouvimos que muitos profissionais da área de computação devem estar em constante atualização para, cada vez mais, oferecem ao mundo inovações devido as rápidas mudanças. Isso é uma grande verdade! No entanto, aos olhos da engenharia da computação, é imprescindível que esses profissionais também não se esqueçam de um dos pilares que dão sustentação à sua formação: a matemática. É ela que torna possível a criação e a avaliação de novos modelos, ponto inicial do processo de desenvolvimento de todas as inovações tecnológicas.

Nesse plano de fundo, não basta apresentarmos a solução para um determinado problema, na análise de algoritmos o importante é apresentar a melhor solução para ele, ou, em muitos casos, a solução mais viável para o momento e com os recursos disponíveis, analisando sempre os pontos positivos e negativos.

Para criar ou utilizar um algoritmo é importante determinar o seu desempenho. Todo algoritmo é projetado para executar uma determinada função e, para isso, ele utiliza uma quantidade de memória e gasta um determinado tempo, e essa execução pode requerer diferentes algoritmos, por isso é necessário analisar qual deles é mais eficiente em diversos aspectos.

O que é a Análise de Algoritmos: O projeto de um algoritmo deve considerar o desempenho que este terá após sua implementação. Quando um problema é estudado e um projeto de algoritmo de algoritmo deve ser feito, várias soluções devem surgir, e aspectos de tempo de execução e espaço ocupado são pontos muito relevantes na escolha. Analisar um algoritmo significa prever os recursos de que ele necessitará. Em geral, memória, largura de banda ou hardware são a preocupação primordial, mas frequentemente é o tempo de computação que se deseja medir. Esse tempo de execução ou custo de utilização pode ser medido por meio de sua execução de um computador real, anotando-se o tempo levando em conta que depende do compilador, do hardware e quantidade de memória principal e secundária.

Outro detalhe importante é o tamanho da entrada de dados no algoritmo. Para valores pequenos, para qualquer algoritmo, mesmo ineficiente, gastará pouco tempo. O que faz o programador escolher um algoritmo não é o seu desempenho sobre tamanhos de entrada pequenos, mas sim sobre tamanhos de entrada grandes. Logo, sua análise é feita sobre tamanhos de entrada grandes. Analisa-se então o comportamento assintótico da função de complexidade de tempo dos algoritmos, sua eficiência assintótica.

Elementos de análise assintótica: Para isso, existem os tipos de notação assintótica ou os elementos de análise assintótica. São utilizados para representar o comportamento assintótico das funções de complexidade de tempo de algoritmos.

Cito algumas delas:

Notação O: utilizada para dar um limite superior.

Notação Ômega: utilizada para dar um limite inferior.

Notação Teta: utilizada para dar um limite firme.

Dentre outras.

Porque algoritmos recursivos são mais rápidos: Um método de uma classe que chama a si mesma é dita recursiva, e a análise do tempo de execução de um algoritmo recursivo é um pouco diferente dos algoritmos que não possuem recursividade.

O cálculo do fatorial de um número n, por exemplo, pode ser elaborado por recursividade, e como a solução do problema de tamanho n depende da solução de problemas menores, o tempo de execução também é representado através do tempo de execução do problema para tamanhos menores. Portanto, desenvolver uma solução não basta, mas sim a melhor solução utilizando a ferramenta de análise de algoritmos.

4 RESUMO DE RECURSIVIDADE

Em ciência da computação, a recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma. Um exemplo de aplicação da recursividade pode ser encontrado nos analisadores sintáticos recursivos para linguagens de programação. A grande vantagem da recursão está na possibilidade de usar um programa de computador finito para definir, analisar ou produzir um estoque potencialmente infinito de sentenças, designs ou outros dados.

Um método comum de simplificação consiste em dividir um problema em subproblemas do mesmo tipo. Como técnica de programação, isto se denomina divisão e conquista, e constitui a chave para o desenvolvimento de muitos algoritmos importantes, bem como um elemento fundamental do paradigma de programação dinâmica.

Praticamente todas as linguagens de programação usadas hoje em dia permitem a especificação direta de funções e procedimentos recursivos. Quando uma função é invocada, o computador (na maioria das linguagens sobre a maior parte das arquiteturas baseadas em pilhas) ou a implementação da linguagem registra as várias instâncias de uma função (em muitas arquiteturas, usa-se uma pilha de chamada, embora outros métodos possam ser usados). Reciprocamente, toda função recursiva pode ser transformada em uma função iterativa usando uma pilha.

Toda função que puder ser produzida por um computador pode ser escrita como função recursiva sem o uso de iteração; reciprocamente, qualquer função recursiva pode ser descrita através de iterações sucessivas.

Um exemplo simples poderia ser o seguinte: se uma palavra desconhecida é vista em um livro, o leitor pode tomar nota do número da página e colocar em uma pilha (que até então está vazia). O leitor pode consultar esta nova palavra e, enquanto lê o texto, pode achar mais palavras desconhecidas e acrescentar no topo da pilha. O número da página em que estas palavras ocorrem também é colocado no topo da pilha. Em algum momento do texto, o leitor vai achar uma frase ou um parágrafo onde está a última palavra anotada e pelo contexto da frase vai descobrir o seu significado. Então o leitor volta para a página anterior e continua lendo dali. Paulatinamente, remove-se sequencialmente cada anotação que está no topo da pilha. Finalmente, o leitor volta para a sua leitura já sabendo o significado da(s) palavra(s) desconhecida(s). Isto é uma forma de recursão.

Algumas linguagens desenvolvidas para programação lógica e programação funcional permitem recursões como única estrutura de repetição, ou seja, não podem usar laços tais como os produzidos por comandos como for, while ou repeat. Tais linguagens geralmente fazem uma recursão em cauda tão eficiente quanto a iteração, deixando os programadores exprimirem outras estruturas de repetição (tais como o map e o for do Scheme) em termos de recursão.

A recursão está profundamente entranhada na Teoria da computação, uma vez que a equivalência teórica entre as funções -recursivas e as máquinas de Turing está na base das ideias sobre a universalidade do computador moderno.

REFERÊNCIAS

1 INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE PERNAMBUCO, B.F. I. Anne. Disponível em:< http://pt.scribd.com/doc/15096143/Metodos-de-Ordenacao>. Acesso em: 16 novembro 2012.

2 CAFOFODOPROGRAMADOR, bubble-sort-em-linguagem. Disponível em:< http://cafofodoprogramador.blogspot.com.br/2009/02/bubble-sort-em-linguagem-c.html>. Acesso em: 18 novembro 2012.

3 WIKIPÉDIA, Hearpsort. Disponível em:< http://pt.wikipedia.org/wiki/Heapsort>. Acesso em: 19 novembro 2012.

4 WIKIPÉDIA, Algoritimo de Ordenação. Disponível em:< http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o>. Acesso em: 19 novembro 2012.

5 Universidade Federal de Alagoas - UFAL Departamento de Tecnologia da Informação - TCI Ciência da Computação, Árvores Binárias e AVL. Disponível em:< http://www.geocities.com/grupotrees/AVL/avl.htm >. Acesso em: 19 de novembro de 2012 .

6 Universidade Federal de Alagoas - UFAL Departamento de Tecnologia da Informação - TCI Ciência da Computação, Árvores Binárias e AVL. Disponível em:< http://www.ppgia.pucpr.br/~laplima/aulas/materia/arvbin_m.html >. Acesso em: 19 de novembro de 2012

7 Ascencio, Ana Fernanda Gomes. Estrutura de dados. Pearson Prentice Hall, 2010.

8 WIKIPÉDIA, Recursividade. Disponível em:< http://pt.wikipedia.org/wiki/Recursividade_%28ci%C3%AAncia_da_computa%C3%A7%C3%A3o%29>. Acesso em: 19 novembro 2012.

...