Please enable JavaScript.

Coggle requires JavaScript to display documents.

00 e 01 - Fundamentos (métodos de ordenação (métodos instáveis (QuickSort,…

- - - - desempenho significativamente melhor que o BubbleSort, em termos absolutos. Além disso, ele é extremamente eficiente para listas que já estejam substancialmente ordenadas e listas com pequeno número de elementos.
        Realiza a ordenação de um vetor por meio da inserção de cada
        elemento em sua posição correta dentro de um subvetor classificado
      - se a lista possui n elementos, após (n-1) inserções, ela estará ordenada
    - - Esse algoritmo é baseado na estratégia de resolução de problemas conhecida como divisão-e-conquista. Essa técnica consiste basicamente em decompor a instância a ser resolvida em instâncias menores do mesmo tipo de problema, resolver tais instâncias (em geral, recursivamente) e por fim utilizar as soluções parciais para obter uma solução da instância original.
    - - Em cada iteração do método, percorremos a lista a partir de seu início comparando cada elemento com seu sucessor, trocando-se de posição se houver necessidade
      - É possível mostrar que, se a lista tiver n elementos, após no máximo (n-1) iterações, a lista estará em ordem (crescente ou decrescente)
  - - - Trata-se, portanto, de um algoritmo do tipo Divisão-e-Conquista i.e., repartindo os dados em subgrupos, dependendo de um elemento chamado pivô.
        Quicksort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independe, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.
    - - Esse algoritmo utiliza uma estrutura de dados chamada heap, para ordenar os elementos à medida que os insere na estrutura.
        Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.
        Essa estrutura pode ser representada como uma árvore ou como um vetor
    - - Esse algoritmo consiste em selecionar o menor elemento de um
        vetor e trocá-lo (swap) pelo item que estiver na primeira posição, i.e., inseri-lo no início do vetor. Essas duas operações são repetidas com os itens restantes até o último elemento
    - - extensão ou refinamento do algoritmo do InsertionSort. Em vez de considerar o vetor a ser ordenado como um único segmento, ele considera vários segmentos e aplica o InsertionSort em cada um deles
- - - - vetores
        
        possui alocação estática, com dados armazenados em posições contíguas de memória e permite o acesso direto ou aleatório a seus elementos
      - matriz
        
        arranjo bidimensional ou multidimensional de alocação estática e sequencial. Ela necessita de um índice para referenciar a linha e outro para referenciar a coluna para que seus elementos sejam endereçados
    - - lista
        
        lista encadeada
        
        campo de informação
        
        campo de endereço (ponteiro)
        
        endereço do próximo nó
        
        é acessada a partir de um ponteiro externo que aponta
        para o primeiro nó na lista. O último elemento da lista aponta para NULL.
        
        lista circular
        
        igual a encadeada, porém o último nó aponta para o primeiro ao invés de NULL
        
        lista duplamente encadeada
        
        Cada nó numa lista desse tipo contém dois ponteiros, um para seu predecessor e outro para seu sucessor
        
        podem ser lineares ou circulares
        
        Lista é uma estrutura de acesso sequencial, i.e., é
        preciso percorrer por nó para acessar um dado específico. quanto mais ao fim, maior o tempo para acessar.
    - - Lista LIFO (Last In First Out) / UEPS (Último a Entrar, Primeiro a Sair)
      - operações
        
        push (insere elemento no topo)
        
        pop (remove um elemento do topo)
        
        top (ou check - acessa e consulta o elemento do topo da pilha)
      - podem ser implementadas por meio de Vetores (Pilha Sequencial - Alocação Estática de Memória) ou Listas (Pilha Encadeada - Alocação Dinâmica de Memória)
    - - Lista FIFO - First In First Out / PEPS (Primeiro a Entrar, Primeiro a Sair)
      - operações
        
        enqueue (enfileirar)
        
        dequeue (desenfileirar)
      - elementos
        
        início (head / cabeça)
        
        fim (tail / cauda)
      - Deque (Double Ended Queue)
        
        Filas Duplamente Encadeadas e permite a eliminação e
        inserção de itens em ambas as extremidades
    - - elementos
        
        pais
        
        folhas (último elemento - toda folha tem Grau 0)
        
        raiz
      - conceitos
        
        grau (quantidade de filhos de um determinado nó)
        
        nível (Raiz = 0 e cada nível aumenta 1)
        
        altura (equivale ao nível máximo de seus nós)
      - tipos
        
        árvore estritamente binária
        
        todos os nós têm grau 0 ou 2
        
        árvore binária completa
        
        todas as folhas estão no mesmo nível
        
        Uma Árvore Binária Completa com x folhas conterá sempre (2x – 1) nós
        
        árvore binária
        
        estrutura de dados hierárquica em que todos os nós têm grau 0 (Folha), 1 (Único filho) ou 2 (Dois filhos)
      - Uma árvore é uma estrutura de dados hierárquica (não-linear) composta por um conjunto finito de elementos com um único elemento raiz, com zero ou mais sub-árvores ligadas a esse elemento raiz
      - modo de percorrimento
        
        in-fixado (esquerda, raiz, direita)
        
        pós-fixada (esquerda, direita, raiz)
        
        pré-fixado (raiz, esquerda, direita)
- - - - duas chaves x e y colidem se h(x) = h(y)
      - técnicas para lidar com colisão
        
        hashing fechado
        
        hashing aberto