Notes - MIECT
Métodos Probabilísticos p/ Engenharia Informática
Notes - MIECT
Métodos Probabilísticos p/ Engenharia Informática
  • Métodos Probabilísticos para Engenharia Informática
  • Probabilidades Condicionais Independentes
    • Conceitos Básicos
    • Teoria Clássica
    • Abordagem Frequencista
    • Teoria Axiomática de Probabilidade
    • Probabilidades Condicionais
    • Independência
    • Experiências de Bernoulli
  • Variáveis Aleatórias
    • Conceito de variável aleatória
    • Caracterização - Parte 1
    • Variáveis aleatórias contínuas
    • Caracterização - Parte 2
  • Distribuições
    • Distribuições
    • Bernoulli
    • Binomial
    • Geométrica
    • Poisson
    • Uniforme
    • Normal
    • Exponencial
  • Variáveis Aleatórias
    • Variáveis aleatórias multidimensionais
    • Vector aleatório
    • Caracterização
  • Esperança matemática
    • Extensão das definições
    • Correlação
    • Independência
    • Covariância
    • Coeficiente de correlação
  • Soma e Combinação Linear de Variáveis Aleatórias
    • Média
    • Variância
    • Função de distribuição
    • Combinações lineares
  • Funções de variáveis aleatórias
    • Funções de v.a. múltiplas
    • Expectância funções de v.a.
    • Momentos de funções
    • Média
  • Situações Limite
    • Situações Limite
    • Markov e Chebyshev
    • Lei dos Grandes Números
    • Teorema do Limite Central
  • Cadeias de Markov
    • Processos estocásticos
    • Estados
    • Matriz de transição
    • Representação gráfica da cadeia
    • Vetor estado
    • Equação de Chapman-Kolmogorov
  • Terminologia
    • Tipos de estados
      • Estados comunicantes
      • Estado recorrente
      • Estado transiente
      • Estado periódico
      • Estado absorvente
    • Equilíbrio
    • Matriz/ Processo regular
    • Cadeia ergódica
  • Cadeias com estados absorventes
    • Cadeias com estados absorventes
  • Forma canónica da matriz de transição
    • Forma canónica da matriz de transição
    • Forma canónica
  • Situação Limite
    • Situação limite
    • Matriz fundamental
    • Tempo médio até absorção
    • Probabilidade de absorção
  • PageRank
    • Os primeiros motores de procura
    • Random surfers / Passeios aleatórios
    • Definição
    • Calculo
    • Forma matricial
    • Limite
    • Problems reais
    • Problemas do Page Rank
  • Geração de Números Aleatórios
    • Motivação
    • Geradores
    • Algoritmos congruenciais
    • Como escolher os parâmetros ?
    • Outros algoritmos congruenciais
  • Transformações
    • Transformações simples
    • Métodos
    • Método da Transformação (Inversa)
    • Método de procura numa tabela
    • Métodos baseados em Rejeição
  • Algoritmos específicos para distribuição mais comuns (discretas)
    • Técnicas especiais Obter Binomial
  • Funções de dispersão
    • Motivação
    • Função de dispersão
    • Hash Code
    • Funções de dispersão / Hash functions
    • Colisões
    • Propriedades
    • Método da Divisão
    • Método da Multiplicação
    • Função de dispersão de uma sequência de caracteres
    • Problemas
    • Funções de dispersão universais
    • Método de Carter Wegman
    • Método da Matriz
    • Como ter n funções de dispersão ?
    • Funções de dispersão criptográficas
  • Solução Probabilística do Problema da Pertença a um Conjunto
    • Definição do problema
    • Conjuntos de grandes dimensões
    • Generalizando …
    • Ideia base
  • Filtros de Bloom
    • Definição
    • Ausência de falsos negativos
    • Inicialização
    • Utilização
    • Erros
    • Parâmetros
    • Implementação
    • Falsos positivos e falsos negativos
      • Probabilidades para um bit
      • Após aplicar k funções de dispersão
      • Após inserir m elementos
      • Probabilidade de falsos positivos
    • Efeito de k na Pfp
    • Determinação de n
    • Filtros de Bloom
    • Filtros de Contagem
    • Obtenção da multiplicidade
    • Problemas
  • Similaridade
    • Generalizando
    • Definição do Problema
      • Solução ingénua
    • Distância
    • Conjuntos Grandes e Gigantes
    • Abordagem probabilística
      • Conversão dos documentos em conjuntos
      • Cálculo das Assinaturas
      • Determinação de pares candidatos
      • Análise do LSH
Powered by GitBook
On this page
  • Objetivo
  • Problemas
  • Solução
  1. Similaridade

Conjuntos Grandes e Gigantes

Objetivo

Dado um grande número de documentos (N), determinar pares “quase iguais”

Problemas

Demasiados documentos para se compararem todos os pares

Muitas partes de um documento podem aparecer por outra ordem noutro

Documentos são tão grandes ou número elevado que não cabem em memória

Solução

  1. Reduzir a dimensão dos conjuntos

    1. mantendo a informação essencial à determinação de distância entre eles

  2. Reduzir o tempo de cálculo da distância e/ou reduzir os pares a que se tem de aplicar essa distância

PreviousDistânciaNextAbordagem probabilística

Last updated 3 years ago