-
Introdução à Análise de Algoritmos
A análise de desempenho é uma etapa fundamental na concepção de um algoritmo. Diante de um problema computacional, diversas soluções podem ser propostas. Por exemplo, para ordenar um sequência de números, o desenvolvedor pode utilizar algoritmos como o BubbleSort, MergeSort, QuickSort entre outros.
Leia mais… -
Análise Assintótica
No material introdutório de análise de algoritmos aprendemos a definir a função que descreve o custo de execução de algoritmos. Vimos exemplos simples cujas funções são também simples. Contudo, vamos supor que a função que descreve o tempo de execução de um algoritmo é dada por:
Leia mais… -
Análise de Algoritmos Recursivos
Até aqui vimos como analisar algoritmos iterativos, lembra? Esse processo pode ser resumido pelos seguintes passos: identificar operações primitivas; identificar a quantidade de vezes que cada uma dessas primitivas é executada; Somar essas execuções.
Leia mais… -
Ordenação por Comparação: Selection Sort
Direto ao ponto Se você pedir para alguém que não é familiarizado com algoritmos para que ordene uma sequência de números, há uma probabilidade alta dessa pessoa aplicar o Selection Sort.
Leia mais… -
Ordenação por Comparação: Insertion Sort
Direto ao ponto O Insertion Sort tem como rotina base a inserção ordenada. A ideia é executar várias vezes essa rotina para ordenar um array. Para ser exato, se executarmos $N - 1$ vezes a rotina de inserção ordenada em um array o resultado é a ordenação completa do mesmo.
Leia mais… -
Ordenação por Comparação: Merge Sort
Merge Sort é um algoritmo eficiente de ordenação por divisão e conquista. Se nossa missão é ordenar um array comparando seus elementos, do ponto de vista assintótico, $n * \log n$ é o nosso limite inferior.
Leia mais… -
Ordenação por Comparação: Quick Sort
Quick Sort é um algoritmo eficiente de ordenação por divisão e conquista. Apesar de ser da mesma classe de complexidade do Merge Sort e do Heap Sort, o Quick Sort é na prática o mais veloz deles, pois suas constantes são menores.
Leia mais… -
Particionamento Hoare para o Quick Sort
No material sobre o QuickSort nós vimos o particionamento de Lomuto – um algoritmo simples para posicionar o pivot tal que todos os elementos à esquerda são menores ou iguais e todos os elementos à direita são maiores.
Leia mais… -
Ordenação Linear: Counting sort
Os algoritmos de ordenação que vimos até então utilizam comparação para estabelecer a ordem entre os elementos de uma sequência. Primeiro vimos três algoritmos $\Theta(n^2)$: Selection Sort, Insertion Sort e Bubble Sort.
Leia mais… -
Listas Baseadas em Arrays (ArrayList)
Array é a primeira estrutura de dados que abordamos na disciplina. Há razões para essa escolha. Em primeiro lugar, arrays estão presentes na biblioteca padrão de grande parte das linguagens de programação.
Leia mais… -
Filas (FIFO) baseadas em Arrays
Neste material nós vamos estudar uma forma de implementar uma FILA utilizando arrays. Disclaimer. Este material tem muita interseção com o material de ArrayList, que eu sugiro que seja lido antes.
Leia mais… -
Listas Ligadas (LinkedList)
Problemas No material sobre ArrayLists discutimos algumas preocupações oriundas do uso de arrays e que estão todas conceitualmente relacionadas ao fato de que o array é uma estrutura de tamanho fixo.
Leia mais… -
Pilhas (LIFO) baseadas em Arrays
Neste material nós vamos estudar uma forma de implementar uma Pilha utilizando arrays. O que define uma pilha é a sua política de acesso. Toda adição (push/addLast) é feita no topo da pilha e toda remoção é feita também no topo da pilha (pop/removeLast).
Leia mais… -
Tabelas Hash
Quando tratamos de estrutura de dados estamos sempre interessados na eficiência de operações fundamentais de coleções, como busca, inserção e remoção. Nesse sentido, o array, embora seja uma estrutura elementar, é um excelente escolha para diversos cenários, pois nos fornece acesso, inserção e remoção em tempo $O(1)$.
Leia mais… -
Uma aula só com perguntas: Endereçamento Aberto
Neste artigo vou descrever um experimento que fiz em sala de aula. Tentei lecionar Resolução de Colisões em Tabelas Hash utilizando apenas perguntas para a turma. Eu estou no meu segundo ano como professor da UFCG e já me cansei de usar slides em sala de aula.
Leia mais… -
Árvores Binárias de Pesquisa
Definições e Propriedades Árvores binárias são estruturas de dados fundamentais no contexto de Ciência da Computação. Em particular, Árvores Binárias de Pesquisa são aplicadas na solução de diversos problemas que demandam eficiência em operações básicas, como busca, inserção e remoção.
Leia mais… -
Heap
Nem toda fila segue a política de acesso First In First Out (FIFO). Na verdade, em vários cenários do dia a dia, as filas que entramos possuem uma política diferente: são filas de prioridade.
Leia mais… -
Árvores Balanceadas (AVL)
Contextualização Árvores binárias são estruturas de dados fundamentais no contexto de Ciência da Computação. Em particular, Árvores Binárias de Pesquisa são aplicadas na solução de diversos problemas que demandam eficiência em operações básicas, como busca.
Leia mais… -
Estruturas de Dados Básicas e Cache
Este não é o material para você aprender cache. Há excelentes livros para isso. Este material é usado na disciplina de estruturas de dados e serve para discutir como usar as estruturas básicas (arrays, linkedlists e tabelas hash) para implementar algumas políticas de cache eviction.
Leia mais…