Monitoria de Algoritmos
iudex.io
PbZFU51
[email protected]
[email protected]
1 Ponteiros em Java
Ponteiros em Java
◇ Todas as variáveis de objetos são ponteiros.
◇ Apenas variáveis de tipos primitivos não são ponteiros.
◇ Os arrays, incluindo os de tipo primitivo, são ponteiros.
◇ Quando se atribui um objeto a uma variável em Java, você não está clonando o
objeto, e sim fazendo com que a variável aponte para o endereço de memória do
objeto. Podendo assim um único objeto ser acessado por múltiplas variáveis.
◇ Quando um objeto é passado para a chamada de um método, ele é passado por
referência. Ou seja, qualquer tipo de modificação feita dentro do método irá alterar
o objeto original. Isso também é válido para arrays.
◇ Atribuir ao parâmetro de um método um outro objeto, não irá sobrescrever o
objeto original. Essa regra só não é válida se você estiver recebendo um array
como parâmetro, e atribuindo esse objeto a um elemento do array.
2 Debug using IntelliJ IDEA
https://www.jetbrains.com/student/
1. Antes de
começarmos a
debugar o código,
2
precisamos indicar
a partir de onde
1
iremos iniciar este
processo. Fazemos
isso setando um
breakpoint na linha
desejada.
2. Logo em seguida
rodamos o
programa em
modo de debug,
fazemos isso
utilizando este
botão.
3. Observe que a
execução do
programa parou
no primeiro
breakpoint, e que
foi aberta uma aba
Debugger. Nesta
área iremos poder
debugar o código,
controlando sua
execução e até
observando seu
contexto.
3
4. Por padrão são
listadas todas as
4
variáveis do
escopo atual.
Pode-se adicionar
mais variáveis
utilizando este
botão.
5. Ao utilizar este
botão, a linha em
destaque no
código é
executada, e o
destaque move
para a próxima
linha.
6. Com este botão é
possível entrar no
escopo do método
da linha
destacada.
5
7. Já este botão tem
6
a finalidade
oposta, indo para
a linha onde o
método, que
contém a linha
atual, foi invocado.
3 ED Estáticas
Array
◇ Estrutura de Dados
◇ Unidimensional
◇ Homogênea
◇ Estática
◇ Alocada Linearmente na Memória
◇ Ponteiro para Primeiro Elemento
◇ Acesso em Tempo Constante
Array
Matriz
◇ Estrutura de Dados
◇ Multidimensional
◇ Homogênea
◇ Estática
◇ Alocada Linearmente na Memória
◇ Ponteiro para Primeiro Elemento (Array)
◇ Acesso em Tempo Constante
Matriz
4 ED Dinâmicas
Lista Encadeada
◇ Estrutura de Dados
◇ Unidimensional
◇ Homogênea
◇ Dinâmica
◇ Alocada Randomicamente na Memória
◇ Ponteiro para Primeiro Elemento
◇ Acesso em Tempo Linear
Lista Encadeada
◇ Simplesmente Encadeada
￭ Ponteiro para Próximo Elemento
◇ Duplamente Encadeada
￭ Ponteiro para Próximo Elemento
￭ Ponteiro para Elemento Anterior
Lista Encadeada
Array Dinâmico
◇ Estrutura de Dados
◇ Unidimensional
◇ Homogênea
◇ Dinâmica
◇ Alocada Linearmente na Memória
◇ Ponteiro para Primeiro Elemento
◇ Acesso em Tempo Constante Amortizado
Array Dinâmico
Fila
◇ Estrutura de Dados
◇ Unidimensional
◇ Homogênea
◇ Dinâmica
◇ Ponteiro para Primeiro Elemento (Começo da Fila)
◇ Ponteiro para Último Elemento (Fim da Fila)
◇ Operações em Tempo Constante
Fila
Pilha
◇ Estrutura de Dados
◇ Unidimensional
◇ Homogênea
◇ Dinâmica
◇ Ponteiro para Primeiro Elemento (Topo da Pilha)
◇ Operações em Tempo Constante
Pilha
5 Complexidade Assintótica
A ideia principal da análise assintótica é
ter uma medida de eficiência de um
algoritmo que não dependa de
constantes específicas de uma máquina
e não exija que o algoritmo seja
“
implementado e executado por um
programa, a fim ser comparado. As
notações assintóticas são ferramentas
matemáticas que permitem representar
a complexidade do tempo de algoritmos,
relativos a sua entrada.
Ω
◇ Lower Bound
◇ Melhor caso
◇ Tempo em relação ao
tamanho da entrada
◇ Suprime constantes
multiplicativas
◇ Suprime termos de
menor ordem
Θ
◇ Define comportamento
assintótico exato de um
algoritmo
◇ Tempo em relação ao
tamanho da entrada
◇ Suprime constantes
multiplicativas
◇ Suprime termos de
menor ordem
Big O
◇ Upper Bound
◇ Pior caso
◇ Tempo em relação ao
tamanho da entrada
◇ Suprime constantes
multiplicativas
◇ Suprime termos de
menor ordem
Tempo Relativo à Entrada
Tempo Relativo à Entrada
Tempo Relativo à Entrada
6 Hash Table
Hash Table
◇ Hash Table é uma estrutura de dados especial, que
associa chaves de pesquisa a valores
◇ Seu objetivo é, a partir de uma chave simples, fazer
uma busca rápida e obter o valor desejado
◇ São tipicamente usadas para indexação de grandes
volumes de informação (como bases de dados)
Hash Table
◇ A implementação típica busca uma função de
dispersão que seja de complexidade O(1), não
importando o número de registros na tabela
(desconsiderando colisões)
◇ O ganho com relação a outras estruturas
associativas (como um vetor simples) passa a ser
maior conforme a quantidade de dados aumenta
Hash Table
Fator de Carga
◇ À medida que o fator de carga aumenta, a hash
table torna-se mais lenta e pode até não funcionar
(dependendo do método usado). A propriedade de
tempo constante, esperada de uma hash table,
pressupõe que o fator de carga é mantido abaixo de
algum limite. Para um número fixo de buckets, o
tempo de busca cresce com o número de entradas e,
portanto, o tempo constante desejado não é
alcançado.
Fator de Carga
◇ Em segundo lugar, pode-se examinar a variância do
número de entradas por bucket. Por exemplo, duas
tabelas possuem 1000 entradas e 1000 buckets; um
tem exatamente uma entrada em cada balde, o
outro tem todas as entradas no mesmo balde.
Claramente, o hash não está funcionando no
segundo.
Fator de Carga
◇ Um fator de carga baixo não é especialmente
benéfico. À medida que o fator de carga se
aproxima de 0, a proporção de áreas não utilizadas
na hash tabela aumenta, mas não há
necessariamente qualquer redução no custo de
busca. Isso resulta em memória desperdiçada.
Fator de Carga
Open Hashing
Closed Hashing
7 Busca em ED Lineares
Busca Linear
Busca Binária
8 Ordenação em ED Lineares
Mergesort
◇ Dividir para Conquistar
◇ Necessita de Memória Auxiliar
◇ Pior Caso O(n * log(n))
◇ Melhor Caso O(n * log(n))
Mergesort
Mergesort
https://youtu.be/4VqmGXwpLqc
Mergesort
https://youtu.be/EeQ8pwjQxTM
Quicksort
◇ Dividir para Conquistar
◇ Algoritmo In-Place
◇ Pior Caso O(n^2)
◇ Melhor Caso O(n * log(n))
Quicksort
Quicksort
https://youtu.be/Hoixgm4-P4M
Quicksort
https://youtu.be/aQiWF4E8flQ
9 ED Multidimensionais 1
Binary Tree
◇ Uma árvore binária é uma estrutura de dados em
que cada nó tem no máximo dois filhos, que são
referidas como o filho à esquerda e o filho à direita.
Binary Tree
Binary Tree
Binary Search Tree
◇ São árvores binárias, que permitem pesquisa,
adição, e remoção rápida de itens.
◇ Pior Caso O(n)
◇ Melhor Caso O(log(n))
Binary Search Tree
Binary Search Tree
Pré-Ordem
F, B, A, D, C, E, G, I, H
Binary Search Tree
Em-Ordem
A, B, C, D, E, F, G, H, I
Binary Search Tree
Pós-Ordem
A, C, E, D, B, H, I, G, F
10 ED Multidimensionais 2
AVL
◇ É uma árvore de busca binária balanceada, ou seja,
são as árvores que minimizam o número de
comparações efetuadas no pior caso para uma
busca com chaves de probabilidades de ocorrências
idênticas. Contudo, para garantir essa propriedade
em aplicações dinâmicas, é preciso reconstruir a
árvore para seu estado ideal a cada operação sobre
seus nós (inclusão ou exclusão).
◇ Pior Caso O(log(n))
◇ Melhor Caso O(log(n))
AVL
AVL
AVL
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Heap
◇ É uma estrutura de dados organizada como uma
árvore binária balanceada, seguindo algumas
regras. Existem dois tipos de heaps: max-heap, em
que o valor de todos os nós são menores que os de
seus respectivos pais; e min-heap, em que o valor de
todos os nós são maiores que os de seus
respectivos pais.
Heap
◇ Assim, em uma max-heap, o maior valor do
conjunto está na raiz da árvore, enquanto na
min-heap a raiz armazena o menor valor existente.
De maneira geral, um heap é uma forma eficiente de
implementação de uma fila de prioridade, uma vez
que o elemento de maior ou menor valor sempre
está armazenado na primeira posição e que a
remoção sempre é feita nesse mesmo elemento.
Heap
Heap
Heap
https://www.cs.usfca.edu/~galles/visualization/Heap.html
Heapify
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/DemoHeapify.pdf
Heapsort
◇ Algoritmo de ordenação baseado em inserção e
extração de elementos em uma heap.
◇ Pior Caso O(log(n))
◇ Melhor Caso O(log(n))
Heapsort
Disjoint-Set
◇ Uma estrutura de dados que mantém o controle de
um conjunto de elementos particionados em
subconjuntos disjuntos. Ela fornece operações com
tempo quase constante para adicionar novos
conjuntos, para mesclar conjuntos existentes, e para
determinar se os elementos estão no mesmo
conjunto. Além de muitos outros usos, os
disjoint-sets desempenham um papel fundamental
no algoritmo de Kruskal para encontrar a árvore de
extensão mínima em um grafo.
Disjoint-Set
11 Grafos
Grafo
◇ Um grafo consiste de um conjunto finito de vértices,
com um conjunto de pares que são conhecidos
como arestas. Os vértices podem ser parte do grafo,
ou podem ser entidades externas representadas por
índices inteiros ou referências.
Grafo
Grafo
◇ Simples
◇ Dirigido
◇ Conexo
◇ Desconexo
◇ Matriz de Adjacências
◇ Lista de Adjacências
◇ Espaço Matriz O(V ^ 2)
◇ Espaço Lista O(V + E)
Depth-First Search
https://www.cs.usfca.edu/~galles/visualization/DFS.html
Toposort
◇ A aplicação canônica da ordenação topológica está na programação de uma
sequência de trabalhos ou tarefas; tem uso potencial todas as vezes em que o
problema abordado envolve uma ordem parcial; algoritmos de ordenação
topológica começaram a ser estudados no início dos anos 1960 no contexto da
técnica PERT para a agendamento de tarefas em gerenciamento de projetos. Os
trabalhos são representados por vértices, e existe uma aresta de x para y se o
trabalho x deve estar concluído antes do trabalho y poder ser iniciado (por
exemplo, ao lavar roupas, a máquina de lavar deve terminar antes de se poder
colocar as roupas para secar). Em seguida, uma ordenação topológica dá uma
ordem na qual se possa realizar os trabalhos.
◇ É possível se obter uma ordem topológica através de uma DFS
◇ Ordem Topológica não é única
Toposort
◇ 5, 7, 3, 11, 8, 2, 9, 10
◇ 3, 5, 7, 8, 11, 2, 9, 10
◇ 5, 7, 3, 8, 11, 10, 9, 2
◇ 7, 5, 11, 3, 10, 8, 9, 2
◇ 5, 7, 11, 2, 3, 8, 9, 10
◇ 3, 7, 8, 5, 11, 10, 2, 9
Breadth-First Search
https://www.cs.usfca.edu/~galles/visualization/BFS.html
Shortest Path
https://youtu.be/0XgVhsMOcQM
12 Algoritmo de Dijkstra
Algoritmo de Dijkstra
◇ O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger
Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais
curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em
tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número
de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo
com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de
execução que o Dijkstra.
◇ Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra
é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de
várias estradas, que passam por diversas cidades. Qual delas oferece uma
trajetória de menor caminho?
Algoritmo de Dijkstra
https://youtu.be/_lHSawdgXpI
13 Algoritmo de Prim
Algoritmo de Prim
◇ O algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para
encontrar uma árvore geradora mínima (minimal spanning tree) num grafo simples
conexo ponderado. Isso significa que o algoritmo encontra um subgrafo do grafo
original no qual a soma total das arestas é minimizada e todos os vértices estão
interligados.
◇ Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o
algoritmo de Kruskal e algoritmo de Boruvka. No entanto estes algoritmos podem
ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de
um grafo conexo.
Algoritmo de Prim
https://youtu.be/cplfcGZmX7I
Algoritmo de Kruskal
https://youtu.be/71UQH7Pr9kU
14 Algoritmo de Bellman-Ford
Algoritmo de Bellman-Ford
◇ O Algoritmo de Bellman-Ford é um algoritmo de
busca de caminho mínimo em um grafo ponderado,
ou seja, cujas arestas têm peso, inclusive negativo.
O Algoritmo de Dijkstra resolve o mesmo problema,
num tempo menor, porém exige que todas as
arestas tenham pesos positivos. Portanto, o
algoritmo de Bellman-Ford é normalmente usado
apenas quando existem arestas de peso negativo.
Algoritmo de Bellman-Ford
https://youtu.be/9PHkk0UavIM
Algoritmo de Bellman-Ford
https://youtu.be/obWXjtg0L64
Algoritmo de
15 Floyd–Warshall
Algoritmo de Floyd–Warshall
◇ O algoritmo de Floyd-Warshall é um algoritmo que
resolve o problema de calcular o caminho mais curto
entre todos os pares de vértices em um grafo
dirigido ponderado.
Algoritmo de Floyd–Warshall
https://youtu.be/4OQeCuLYj-4
