Guia de Algoritmos, Estruturas de Dados e Complexidade

Conceitos Fundamentais

Algoritmo: Sequência de ações executáveis para obtenção de uma solução para um determinado tipo de problema. Segundo Dijkstra, é uma descrição de um padrão de comportamento expresso em termos de um conjunto finito de ações.

Bubblesort: É um algoritmo de ordenação popular; ele funciona permutando repetidamente elementos adjacentes que estão fora de ordem.

Dados: Sucessões de fatos brutos que não foram organizados, processados, relacionados, avaliados ou interpretados, representando partes isoladas de eventos, situações ou ocorrências.

Filas: Estruturas onde todas as inserções são realizadas em um extremo da estrutura, e todas as retiradas e, geralmente, os acessos são realizados no outro extremo da estrutura; elas têm características FIFO (First In, First Out).

Heapsort: Método de ordenação que seleciona o menor item do vetor e, a seguir, troca-o com o item que está na primeira posição do vetor; repita esta operação com os n-1 itens restantes, depois com os n-2 itens, e assim sucessivamente.

Informação: Tem-se no momento em que os dados passam por algum tipo de relacionamento, avaliação, interpretação ou organização, permitindo que decisões possam ser tomadas; a qualidade dessas decisões dependerá da quantidade e qualidade dos dados disponíveis e do relacionamento efetuado.

Listas Lineares: Uma das formas mais simples de interligar os elementos de um conjunto; estrutura em que as operações inserir, retirar e localizar são definidas. São estruturas muito flexíveis porque podem crescer ou diminuir de tamanho durante a execução de um programa de acordo com a demanda, adequadas para aplicações nas quais não é possível prever a demanda por memória, permitindo manipulação de quantidades imprevisíveis de dados.

Ordenação por Inserção: Neste método de ordenação, em cada passo, a partir de i=2, o i-ésimo item da sequência fonte é acompanhado e transferido para a sequência destino, sendo inserido no seu lugar apropriado.

Pilhas: Estrutura em que todas as inserções, retiradas e, geralmente, todos os acessos são feitos em apenas um extremo da estrutura; o último item a ser inserido é o primeiro item que pode ser retirado da lista; tem característica LIFO (Last In, First Out).

Processo de Ordenação: Corresponde ao processo de rearranjar um conjunto de objetivos em uma ordem ascendente ou descendente; seu objetivo principal é facilitar a recuperação posterior de itens do conjunto ordenado. A atividade de colocar as coisas em ordem está presente na maioria das aplicações em que os objetivos armazenados têm de ser pesquisados e recuperados.

Quicksort: Algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações, e o mais utilizado; a ideia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores.

Shellsort: O método da inserção troca itens adjacentes quando está procurando o ponto de inserção na sequência destino; se o menor item estiver na posição mais à direita no vetor, então o número de comparações e movimentações é igual a n-1 para encontrar o seu ponto de inserção; este método contorna o problema permitindo trocas de registros que estão distantes um do outro.

Tipo Abstrato de Dados (TAD): Modelo matemático acompanhado de operações definidas sobre o modelo.

Análise de Complexidade e Desempenho

Tipo de Dados: Conjunto de valores a que uma constante pertence, ou que podem ser assumidos por uma variável ou expressão, ou que podem ser gerados por uma função.

Medidas de Custo:

• Análise Experimental: Execução do programa em um computador real.
• Análise Assintótica: Conjunto de operações a serem executadas.

Função de Custo ou de Complexidade F:

• Complexidade de Tempo: Medida da quantidade de tempo necessário para executar um algoritmo de tamanho n.
• Complexidade de Espaço: Medida da quantidade de memória para executar um algoritmo de tamanho n.

Análise de Complexidade Tempo-Assintótica:

1. Realizada para valores grandes de n; estuda o comportamento de suas funções de custo para valores grandes de n, isto é, estuda o comportamento assintótico das funções de custo.
2. A Análise Big Oh mede o desempenho de um programa olhando para o próprio programa (código).
3. Se f é uma função de complexidade para um algoritmo f, então O(f) é considerada a complexidade assintótica ou comportamento assintótico do algoritmo f.

Análise de Complexidade Assintótica (Três Cenários):

1. Melhor Caso: Menor tempo de execução sobre todas as possíveis entradas de tamanho n. f(n) = 1.
2. Pior Caso: Maior tempo de execução sobre todas as entradas de tamanho n. f(n) = n.
3. Caso Médio: Média dos tempos de execução de todas as entradas de tamanho n. f(n+1) = /2.

Algoritmos e seus Tempos de Execução usando Big Oh:

• 1. Constante: Complexidade f(n) = O(1).
• 2. Linear: Complexidade f(n) = O(n).
• 3. Logaritmo: Complexidade f(n) = O(log n).
• 4. Tempo de Execução: f(n) = O(n log n).
• 5. Tempo de Execução Quadrática: Complexidade f(n) = O(n²).
• 6. Tempo de Execução Cúbica: Complexidade f(n) = O(n³).
• 7. Exponencial: Complexidade f(n) = O(2ⁿ).
• 8. Fatorial: Complexidade f(n) = O(n!).

Técnicas e Problemas Clássicos

Técnicas de Análise de Algoritmos (Tempo de Execução para): 1. Um comando de atribuição, de leitura ou escrita; 2. Uma sequência de comandos; 3. Um comando de decisão; 4. Executar uma estrutura de repetição; 5. Procedimentos não recursivos; 6. Procedimentos recursivos.

Recursividade: É a ideia de uma função chamar a si mesma; pode ser utilizada se o cenário é puramente recursivo e de baixo custo, caso contrário, utiliza-se iteração.

Técnica de Força Bruta: Avalia todos os possíveis candidatos para obter uma solução.

Técnica de Tentativa e Erro (Backtracking): Constrói os candidatos à solução passo a passo e, a cada passo, os avalia.

Problema das Rainhas: Dado um tabuleiro de xadrez, distribuir 8 rainhas sobre ele de modo que nenhuma delas fique em posição de ser atacada por outra.

Passeio do Cavalo: Dado um tabuleiro de xadrez com n x n posições, o problema consiste em encontrar, se existir, um passeio do cavalo tal que todos os pontos do tabuleiro sejam visitados uma vez.

Grafos: Um grafo G = (V, E) é um conjunto de V vértices e um conjunto de E arestas; cada aresta é um par de vértices. É representado graficamente usando bolinhas para vértices e retas ou curvas para arestas.

Exemplos de Exercícios

• Ex 1: Implemente uma pesquisa sequencial
  V = {1, 2, 3, 4, 5, 10, 9} | número = 5
  for(i = 0; i < 6; i++) { if (vetor[i] == numero) encontrou = true; }
• Ex 2: Fatorial
  5! = 5 x 4 x 3 x 2 x 1 = 120
• Ex 3: Potência
  3² = 3 x 3 = 9