Lista de algoritmos - List of algorithms

La siguiente es una lista de algoritmos junto con descripciones de una línea para cada uno.

Planificación automatizada

Algoritmos combinatorios

Algoritmos combinatorios generales

• Algoritmo de Brent : encuentra un ciclo en las iteraciones del valor de la función usando solo dos iteradores
• Algoritmo de búsqueda de ciclo de Floyd : encuentra un ciclo en iteraciones de valor de función
• Algoritmo de Gale-Shapley : resuelve el problema del matrimonio estable
• Generadores de números pseudoaleatorios (distribuidos uniformemente; consulte también la Lista de generadores de números pseudoaleatorios para otros PRNG con diversos grados de convergencia y calidad estadística variable):
  • Generador de BELLOTA
  • Blum Blum Shub
  • Generador de Fibonacci retrasado
  • Generador de congruencia lineal
  • Mersenne Twister

Algoritmos de grafos

• Algoritmo de coloración: algoritmo de coloración de gráficos.
• Algoritmo Hopcroft-Karp : convierta un gráfico bipartito en una coincidencia máxima de cardinalidad
• Algoritmo húngaro : algoritmo para encontrar una coincidencia perfecta
• Codificación Prüfer : conversión entre un árbol etiquetado y su secuencia Prüfer
• Algoritmo de ancestros comunes más bajos fuera de línea de Tarjan : calcula los ancestros comunes más bajos para pares de nodos en un árbol
• Clasificación topológica : busca el orden lineal de los nodos (por ejemplo, trabajos) en función de sus dependencias.

Dibujo gráfico

• Algoritmos basados en fuerza (también conocidos como algoritmos dirigidos por fuerza o algoritmo basado en resortes)
• Disposición espectral

Teoría de redes

• Análisis de red
  • Análisis de enlaces
    • Algoritmo Girvan-Newman : detecta comunidades en sistemas complejos
    • Análisis de enlaces web
      • Búsqueda de temas inducida por hipervínculos (HITS) (también conocida como Hubs y autoridades )
      • Rango de página
      • TrustRank
• Redes de flujo
  • Algoritmo de Dinic : es un algoritmo fuertemente polinomial para calcular el flujo máximo en una red de flujo .
  • Algoritmo de Edmonds-Karp : implementación de Ford-Fulkerson
  • Algoritmo de Ford-Fulkerson : calcula el flujo máximo en un gráfico
  • Algoritmo de Karger : un método de Monte Carlo para calcular el corte mínimo de un gráfico conectado
  • Algoritmo push-reetiquetado : calcula un flujo máximo en un gráfico

Enrutamiento para gráficos

• Algoritmo de Edmonds (también conocido como algoritmo de Chu – Liu / Edmonds): encuentre ramificaciones máximas o mínimas
• Árbol de expansión mínimo euclidiano : algoritmos para calcular el árbol de expansión mínimo de un conjunto de puntos en el plano
• Problema del camino más corto euclidiano : encuentre el camino más corto entre dos puntos que no cruce ningún obstáculo
• Problema de ruta más larga : encuentre una ruta simple de longitud máxima en un gráfico dado
• Árbol de expansión mínimo
  • Algoritmo de Borůvka
  • Algoritmo de Kruskal
  • Algoritmo de Prim
  • Algoritmo de eliminación inversa
• Interruptor de expansión mínima sin bloqueo , digamos, para una central telefónica
• Problema del camino más corto
  • Algoritmo de Bellman-Ford : calcula las rutas más cortas en un gráfico ponderado (donde algunos de los pesos de los bordes pueden ser negativos)
  • Algoritmo de Dijkstra : calcula las rutas más cortas en un gráfico con pesos de borde no negativos
  • Algoritmo de Floyd-Warshall : resuelve el problema de la ruta más corta de todos los pares en un gráfico dirigido ponderado
  • Algoritmo de Johnson : algoritmo de ruta más corta de todos los pares en un gráfico dirigido ponderado disperso
• Problema de cierre transitivo : encuentre el cierre transitivo de una relación binaria dada
• Problema del vendedor ambulante
  • Algoritmo de Christofides
  • Algoritmo del vecino más cercano
• Regla de Warnsdorff : un método heurístico para resolver el problema de la gira del Caballero .

Búsqueda gráfica

• A * : caso especial de búsqueda del mejor primero que utiliza heurística para mejorar la velocidad
• B * : un algoritmo de búsqueda de gráfico del mejor primero que encuentra la ruta de menor costo desde un nodo inicial dado a cualquier nodo de objetivo (de uno o más objetivos posibles)
• Retroceso : abandona las soluciones parciales cuando se descubre que no satisfacen una solución completa
• Beam search : es un algoritmo de búsqueda heurístico que es una optimización de la mejor búsqueda que reduce su requerimiento de memoria.
• Búsqueda de pila de haces : integra el retroceso con la búsqueda de haces
• Mejor búsqueda primero : atraviesa un gráfico en el orden de importancia probable utilizando una cola de prioridad
• Búsqueda bidireccional : encuentre el camino más corto desde un vértice inicial hasta un vértice de meta en un gráfico dirigido
• Búsqueda primero en amplitud : atraviesa un gráfico nivel por nivel
• Búsqueda de fuerza bruta : un método de búsqueda exhaustivo y confiable, pero computacionalmente ineficiente en muchas aplicaciones.
• D * : un algoritmo de búsqueda heurística incremental
• Búsqueda en profundidad : atraviesa un gráfico rama por rama
• Algoritmo de Dijkstra : un caso especial de A * para el que no se utiliza una función heurística
• Solucionador de problemas generales : un algoritmo de demostración de teoremas seminal destinado a funcionar como una máquina universal de resolución de problemas.
• Búsqueda iterativa de profundización primero en profundidad (IDDFS): una estrategia de búsqueda de espacio de estado
• Búsqueda de punto de salto : una optimización a A * que puede reducir el tiempo de cálculo en un orden de magnitud utilizando heurísticas adicionales.
• Búsqueda lexicográfica primero en amplitud (también conocida como Lex-BFS): un algoritmo de tiempo lineal para ordenar los vértices de un gráfico
• Búsqueda de costo uniforme : una búsqueda de árbol que encuentra la ruta de menor costo donde los costos varían
• SSS * : búsqueda de espacio de estado que atraviesa un árbol del juego de una manera mejor primero similar a la del algoritmo de búsqueda A *
• F * : algoritmo especial para fusionar las dos matrices

Subgrafos

• Camarillas
  • Algoritmo de Bron – Kerbosch : una técnica para encontrar camarillas máximas en un gráfico no dirigido
  • Algoritmo de camarilla máxima MaxCliqueDyn : encuentre una camarilla máxima en un gráfico no dirigido
• Componentes fuertemente conectados
  • Algoritmo de componente fuerte basado en ruta
  • Algoritmo de Kosaraju
  • Algoritmo de componentes fuertemente conectados de Tarjan
• Problema de isomorfismo de subgrafo

Algoritmos de secuencia

Coincidencia de secuencia aproximada

• Algoritmo Bitap : algoritmo difuso que determina si las cadenas son aproximadamente iguales.
• Algoritmos fonéticos
  • Daitch – Mokotoff Soundex : un refinamiento de Soundex que permite la coincidencia de apellidos eslavos y germánicos
  • Double Metaphone : una mejora en Metaphone
  • Enfoque de clasificación de coincidencia : un algoritmo fonético desarrollado por Western Airlines
  • Metaphone : un algoritmo para indexar palabras por su sonido, cuando se pronuncia en inglés
  • NYSIIS : algoritmo fonético , mejora en Soundex
  • Soundex : un algoritmo fonético para indexar nombres por sonido, como se pronuncia en inglés
• Métricas de cadenas : calcula una puntuación de similitud o disimilitud (distancia) entre dos pares de cadenas de texto
  • Distancia de Damerau-Levenshtein : calcula una medida de distancia entre dos cuerdas, mejora la distancia de Levenshtein
  • Coeficiente de dados (también conocido como coeficiente de dados): una medida de similitud relacionada con el índice de Jaccard
  • Distancia de Hamming : suma del número de posiciones que son diferentes
  • Distancia Jaro-Winkler : es una medida de similitud entre dos cadenas
  • Distancia de edición de Levenshtein : calcula una métrica para la cantidad de diferencia entre dos secuencias
• Trigram search : busca texto cuando no se conoce con precisión la sintaxis o la ortografía exacta del objeto de destino

Algoritmos de selección

• Selección rápida
• Introselect

Búsqueda de secuencia

• Búsqueda lineal : localiza un elemento en una secuencia sin clasificar.
• Algoritmo de selección : encuentra el k- ésimo elemento más grande en una secuencia
• Búsqueda ternaria : una técnica para encontrar el mínimo o máximo de una función que es estrictamente creciente y luego estrictamente decreciente o viceversa.
• Listas ordenadas
  • Algoritmo de búsqueda binaria : ubica un elemento en una secuencia ordenada
  • Técnica de búsqueda de Fibonacci : busque una secuencia ordenada utilizando un algoritmo de dividir y conquistar que reduce las posibles ubicaciones con la ayuda de los números de Fibonacci
  • Búsqueda de salto (o búsqueda de bloque): búsqueda lineal en un subconjunto más pequeño de la secuencia
  • Búsqueda predictiva : búsqueda de tipo binario que tiene en cuenta la magnitud del término de búsqueda frente a los valores altos y bajos de la búsqueda. A veces se denomina búsqueda de diccionario o búsqueda interpolada.
  • Búsqueda binaria uniforme : una optimización del algoritmo de búsqueda binaria clásico

Secuencia de fusión

• Algoritmo de fusión simple
• algoritmo de fusión de k-way
• Unión (fusionar, con elementos en la salida no repetidos)

Permutaciones de secuencia

• Mezcla de Fisher-Yates (también conocida como reproducción aleatoria de Knuth): mezcla aleatoriamente un conjunto finito
• Algoritmo de Schensted : construye un par de cuadros de Young a partir de una permutación
• Algoritmo Steinhaus-Johnson-Trotter (también conocido como algoritmo Johnson-Trotter): genera permutaciones mediante la transposición de elementos
• Algoritmo de generación de permutación de heap : intercambiar elementos para generar la siguiente permutación

Combinaciones de secuencia

Alineación de secuencia

• Deformación de tiempo dinámica : mide la similitud entre dos secuencias que pueden variar en el tiempo o la velocidad
• Algoritmo de Hirschberg : encuentra la alineación de secuencia de menor costo entre dos secuencias, medida por su distancia de Levenshtein
• Algoritmo de Needleman-Wunsch : encuentre la alineación global entre dos secuencias
• Algoritmo de Smith-Waterman : encuentre la alineación de secuencia local

Orden de secuencia

• Tipos de intercambio
  • Clasificación de burbujas : para cada par de índices, intercambie los elementos si están fuera de orden
  • Clasificación de coctelera o clasificación de burbujas bidireccionales, una clasificación de burbujas que recorre la lista alternativamente de adelante hacia atrás y de atrás hacia adelante
  • Tipo de peine
  • Tipo de gnomo
  • Tipo impar-par
  • Clasificación rápida : divida la lista en dos, con todos los elementos de la primera lista antes de todos los elementos de la segunda lista .; luego ordene las dos listas. A menudo, el método de elección
• Humorístico o ineficaz
  • Bogosort
  • Tipo chiflado
• Híbrido
  • Flashsort
  • Introsort : comience con quicksort y cambie a heapsort cuando la profundidad de recursividad exceda un cierto nivel
  • Timsort : algoritmo adaptativo derivado de la ordenación por fusión y la ordenación por inserción. Usado en Python 2.3 y versiones posteriores, y Java SE 7.
• Clases de inserción
  • Orden de inserción : determine dónde pertenece el elemento actual en la lista de ordenados e insértelo allí
  • Orden de biblioteca
  • Clasificación de paciencia
  • Ordenación de shell : un intento de mejorar la ordenación por inserción
  • Clasificación de árbol ( clasificación de árbol binario): construya un árbol binario, luego recorralo para crear una lista ordenada
  • Orden de ciclo : en el lugar con un número teóricamente óptimo de escrituras
• Fusionar clases
  • Combinar ordenación : ordena la primera y la segunda mitad de la lista por separado, luego combina las listas ordenadas
  • Clasificación lenta
  • Tipo de hebra
• Clases sin comparación
  • Tipo de cuentas
  • Tipo de cubo
  • Burstsort : cree un trie de ráfagas compacto y eficiente en caché y luego recorralo para crear una salida ordenada
  • Contando ordenar
  • Tipo de casillero
  • Tipo de cartero : variante del tipo de cubo que aprovecha la estructura jerárquica
  • Ordenación por radix : ordena las cadenas letra por letra
• Clases de selección
  • Heapsort : convierta la lista en un montón, siga eliminando el elemento más grande del montón y agregándolo al final de la lista
  • Orden de selección: elija el más pequeño de los elementos restantes, agréguelo al final de la lista ordenada
  • Smoothsort
• Otro
  • Clasificador bitónico
  • Clasificación de panqueques
  • Tipo de espagueti
  • Orden topológico
• Clase desconocida
  • Ordenación de muestras

Subsecuencias

• Algoritmo de Kadane : encuentra la submatriz máxima de cualquier tamaño
• Problema de subsecuencia común más larga : encuentre la subsecuencia más larga común a todas las secuencias en un conjunto de secuencias
• Problema de subsecuencia creciente más larga : encuentre la subsecuencia creciente más larga de una secuencia dada
• Problema de supersecuencia común más corta: encuentre la supersecuencia más corta que contenga dos o más secuencias como subsecuencias

Subcadenas

• Problema de subcadena común más largo : encuentre la cadena (o cadenas) más larga que sea una subcadena (o son subcadenas) de dos o más cadenas
• Búsqueda de subcadenas
  • Algoritmo de coincidencia de cadenas Aho-Corasick : algoritmo basado en trie para encontrar todas las coincidencias de subcadenas con cualquiera de un conjunto finito de cadenas
  • Algoritmo de búsqueda de cadenas de Boyer-Moore : algoritmo lineal amortizado ( sublineal en la mayoría de los casos) para la búsqueda de subcadenas
  • Algoritmo de Boyer-Moore-Horspool : simplificación de Boyer-Moore
  • Algoritmo de Knuth-Morris-Pratt : búsqueda de subcadenas que omite el reexamen de caracteres coincidentes
  • Algoritmo de búsqueda de cadenas de Rabin-Karp : busca múltiples patrones de manera eficiente
  • Algoritmo de coincidencia de cadenas de Zhu-Takaoka : una variante de Boyer-Moore
• El algoritmo de Ukkonen : un tiempo lineal , algoritmo de línea para la construcción de árboles de sufijos
• Coincidencia de comodines
  • Rich Salz ' wildmat : un ampliamente utilizado de fuente abierta recursivo algoritmo
  • Algoritmo de comodines de coincidencia de Krauss : un algoritmo no recursivo de código abierto

Matemática computacional

Álgebra abstracta

• Búsqueda de Chien : un algoritmo recursivo para determinar las raíces de polinomios definidos sobre un campo finito
• Algoritmo de Schreier-Sims : cálculo de un grupo electrógeno base y fuerte (BSGS) de un grupo de permutación
• Algoritmo de Todd-Coxeter : procedimiento para generar clases laterales .

Álgebra informática

• El algoritmo de Buchberger : encuentra una base de Gröbner
• Algoritmo de Cantor-Zassenhaus : factorizar polinomios sobre campos finitos
• Algoritmo Faugère F4 : encuentra una base de Gröbner (también menciona el algoritmo F5)
• Algoritmo de Gosper : encuentre sumas de términos hipergeométricos que sean en sí mismos términos hipergeométricos
• Algoritmo de finalización de Knuth-Bendix : para reescribir sistemas de reglas
• Algoritmo de división multivariante : para polinomios en varios indeterminados
• Algoritmo canguro de Pollard (también conocido como algoritmo lambda de Pollard): un algoritmo para resolver el problema del logaritmo discreto
• División larga de polinomios : un algoritmo para dividir un polinomio por otro polinomio del mismo o menor grado.
• Algoritmo de Risch : un algoritmo para la operación de cálculo de integración indefinida (es decir, encontrar antiderivadas )

Geometría

• Problema del par más cercano : encuentre el par de puntos (de un conjunto de puntos) con la distancia más pequeña entre ellos
• Algoritmos de detección de colisiones : compruebe la colisión o intersección de dos sólidos dados
• Algoritmo de cono : identificar puntos de superficie
• Algoritmos de casco convexo : determinación del casco convexo de un conjunto de puntos
  • Escaneo de Graham
  • Quickhull
  • Algoritmo de envoltura de regalos o marcha de Jarvis
  • Algoritmo de Chan
  • Algoritmo de Kirkpatrick-Seidel
• Transformada de distancia euclidiana : calcula la distancia entre cada punto de una cuadrícula y una colección discreta de puntos.
• Hash geométrico : un método para encontrar de manera eficiente objetos bidimensionales representados por puntos discretos que han sufrido una transformación afín
• Algoritmo de distancia de Gilbert – Johnson – Keerthi : determinación de la distancia más pequeña entre dos formas convexas .
• Algoritmo Jump-and-Walk : un algoritmo para la ubicación de puntos en triangulaciones
• Suavizado laplaciano : un algoritmo para suavizar una malla poligonal
• Intersección de segmento de línea : encontrar si las líneas se cruzan, generalmente con un algoritmo de línea de barrido
  • Algoritmo de Bentley-Ottmann
  • Algoritmo de Shamos-Hoey
• Algoritmos del cuadro delimitador mínimo : encuentre el cuadro delimitador mínimo orientado que encierra un conjunto de puntos
• Búsqueda de vecino más cercano : busque el punto o puntos más cercanos a un punto de consulta
• Algoritmos de punto en polígono : prueba si un punto dado se encuentra dentro de un polígono dado
• Algoritmos de registro de conjuntos de puntos : encuentra la transformación entre dos conjuntos de puntos para alinearlos de manera óptima.
• Calibradores giratorios : determinan todos los pares antípodas de puntos y vértices en un polígono convexo o casco convexo .
• Algoritmo de cordones : determina el área de un polígono cuyos vértices están descritos por pares ordenados en el plano.
• Triangulación
  • Triangulación de Delaunay
    • Algoritmo de Ruppert (también conocido como refinamiento de Delaunay): cree triangulaciones de Delaunay de calidad
    • El segundo algoritmo de Chew : crear triangulaciones de Delaunay con restricciones de calidad
  • Triángulos en marcha : reconstruya la geometría de la superficie bidimensional a partir de una nube de puntos no estructurada
  • Algoritmos de triangulación de polígonos : descomponga un polígono en un conjunto de triángulos
  • Diagramas de Voronoi , dual geométrico de triangulación de Delaunay
    • Algoritmo de Bowyer-Watson : cree un diagrama de voronoi en cualquier número de dimensiones
    • Algoritmo de Fortune : crear diagrama de voronoi
  • Cuasitriangulación

Algoritmos teóricos de números

• Algoritmo binario GCD : forma eficiente de calcular GCD.
• Algoritmo de multiplicación de Booth
• Método de Chakravala : un algoritmo cíclico para resolver ecuaciones cuadráticas indeterminadas, incluida la ecuación de Pell
• Logaritmo discreto :
  • Paso de bebé paso gigante
  • Algoritmo de cálculo de índices
  • Algoritmo rho de Pollard para logaritmos
  • Algoritmo de Pohlig-Hellman
• Algoritmo euclidiano : calcula el máximo común divisor
• Algoritmo euclidiano extendido : también resuelve la ecuación ax  +  by  =  c .
• Factorización de enteros : dividir un entero en sus factores primos
  • Congruencia de cuadrados
  • El algoritmo de Dixon
  • Método de factorización de Fermat
  • Tamiz de campo de número general
  • Factorización de la curva elíptica de Lenstra
  • De Pollard p  - 1 algoritmo
  • Algoritmo rho de Pollard
  • algoritmo de factorización prima
  • Tamiz cuadrático
  • Algoritmo de Shor
  • Tamiz de campo de número especial
  • División de prueba
• Algoritmos de multiplicación : multiplicación rápida de dos números
  • Algoritmo de Karatsuba
  • Algoritmo de Schönhage-Strassen
  • Multiplicación de Toom-Cook
• Raíz cuadrada modular : calcular raíces cuadradas módulo un número primo
  • Algoritmo de Tonelli-Shanks
  • Algoritmo de Cipolla
  • Algoritmo de búsqueda de raíces de Berlekamp
• Algoritmo de Odlyzko-Schönhage : calcula ceros no triviales de la función zeta de Riemann
• Algoritmo Lenstra – Lenstra – Lovász (también conocido como algoritmo LLL): encuentre una base de celosía corta, casi ortogonal en tiempo polinomial
• Pruebas de primordialidad : determinar si un número dado es primo
  • Prueba de primalidad de AKS
  • Prueba de primalidad de Baillie-PSW
  • Prueba de primalidad de Fermat
  • Prueba de primalidad de Lucas
  • Prueba de primalidad de Miller-Rabin
  • Tamiz de Atkin
  • Tamiz de Eratóstenes
  • Tamiz de Sundaram

Algoritmos numéricos

Resolución de ecuaciones diferenciales

• Método Euler
• Método de Euler hacia atrás
• Regla trapezoidal (ecuaciones diferenciales)
• Métodos lineales de varios pasos
• Métodos de Runge-Kutta
  • Integración de Euler
• Métodos de cuadrícula múltiple ( métodos MG), un grupo de algoritmos para resolver ecuaciones diferenciales utilizando una jerarquía de discretizaciones.
• Ecuación diferencial parcial :
  • Método de diferencias finitas
  • Método de Crank-Nicolson para ecuaciones de difusión
  • Lax-Wendroff para ecuaciones de onda
• La integración de Verlet ( pronunciación francesa: [vɛʁlɛ] ): integrar las ecuaciones del movimiento de Newton

Funciones elementales y especiales

• Cálculo de π :
  • Algoritmo de Borwein : un algoritmo para calcular el valor de 1 / π
  • Algoritmo de Gauss-Legendre : calcula los dígitos de pi
  • Algoritmo de Chudnovsky : un método rápido para calcular los dígitos de π
  • Fórmula de Bailey-Borwein-Plouffe : (fórmula BBP) un algoritmo de espiga para el cálculo del enésimo dígito binario de π
• Algoritmos de división : para calcular el cociente y / o el resto de dos números
  • División larga
  • Restaurando la división
  • División no restauradora
  • División SRT
  • División de Newton-Raphson : usa el método de Newton para encontrar el recíproco de D y multiplica ese recíproco por N para encontrar el cociente final Q.
  • División Goldschmidt
• Funciones hiperbólicas y trigonométricas:
  • Algoritmo BKM : calcula funciones elementales usando una tabla de logaritmos
  • CORDIC : calcula funciones hiperbólicas y trigonométricas usando una tabla de arcangentes
• Exponenciación:
  • Exponenciación de cadena de suma : exponenciación por potencias enteras positivas que requiere un número mínimo de multiplicaciones
  • Exponenciación por cuadratura : un algoritmo utilizado para el cálculo rápido de grandes potencias enteras de un número.
• Reducción de Montgomery : un algoritmo que permite realizar la aritmética modular de manera eficiente cuando el módulo es grande
• Algoritmos de multiplicación : multiplicación rápida de dos números
  • Algoritmo de multiplicación de Booth : un algoritmo de multiplicación que multiplica dos números binarios con signo en notación en complemento a dos
  • Algoritmo de Fürer : un algoritmo de multiplicación de enteros para números muy grandes que poseen una complejidad asintótica muy baja
  • Algoritmo de Karatsuba : un procedimiento eficiente para multiplicar números grandes
  • Algoritmo de Schönhage-Strassen : un algoritmo de multiplicación asintóticamente rápido para números enteros grandes
  • Multiplicación de Toom-Cook : (Toom3) un algoritmo de multiplicación para números enteros grandes
• Algoritmos inversos multiplicativos : para calcular el inverso multiplicativo (recíproco) de un número.
  • Método de Newton
• Funciones de redondeo : las formas clásicas de redondear números
• Algoritmo de espiga : una forma de calcular el valor de una constante matemática sin conocer los dígitos anteriores
• Raíz cuadrada y enésima de un número:
  • Algoritmo alpha max plus beta min : una aproximación de la raíz cuadrada de la suma de dos cuadrados
  • Métodos para calcular raíces cuadradas
  • n- ésimo algoritmo raíz
  • Cambio de algoritmo de raíz n : extracción de raíz dígito a dígito
• Suma:
  • División binaria : una técnica de divide y vencerás que acelera la evaluación numérica de muchos tipos de series con términos racionales.
  • Algoritmo de suma de Kahan : un método más preciso para sumar números de punto flotante
• Algoritmo sin restricciones

Geométrico

• Retroproyección filtrada : calcula de manera eficiente la transformada de radón bidimensional inversa .
• Método de conjunto de niveles (LSM): una técnica numérica para rastrear interfaces y formas

Interpolación y extrapolación

• Interpolación de Birkhoff : una extensión de la interpolación polinomial
• Interpolación cúbica
• Interpolación de Hermite
• Interpolación de Lagrange : interpolación utilizando polinomios de Lagrange
• Interpolación lineal : un método de ajuste de curvas que utiliza polinomios lineales.
• Interpolación cúbica monótona: una variante de interpolación cúbica que conserva la monotonicidad del conjunto de datos que se interpola.
• Interpolación multivariante
  • Interpolación bicúbica , una generalización de la interpolación cúbica a dos dimensiones
  • Interpolación bilineal : una extensión de la interpolación lineal para interpolar funciones de dos variables en una cuadrícula regular
  • Remuestreo de Lanczos ("Lanzosh"): un método de interpolación multivariante utilizado para calcular nuevos valores para cualquier dato muestreado digitalmente
  • Interpolación del vecino más cercano
  • Interpolación tricúbica , una generalización de la interpolación cúbica a tres dimensiones
• Interpolación de Pareto : método para estimar la mediana y otras propiedades de una población que sigue una distribución de Pareto .
• Interpolación polinomial
  • El algoritmo de Neville
• Interpolación de splines : reduce el error con el fenómeno de Runge .
  • Algoritmo de De Boor : B-splines
  • Algoritmo de De Casteljau : curvas de Bézier
• Interpolación trigonométrica

Álgebra lineal

• Algoritmos de valores propios
  • Iteración de Arnoldi
  • Iteración inversa
  • Método Jacobi
  • Iteración de Lanczos
  • Iteración de poder
  • Algoritmo QR
  • Iteración del cociente de Rayleigh
• Proceso de Gram-Schmidt : ortogonaliza un conjunto de vectores
• Algoritmos de multiplicación de matrices
  • Algoritmo de Cannon : un algoritmo distribuido para la multiplicación de matrices especialmente adecuado para computadoras dispuestas en una malla N × N
  • Algoritmo de calderero-Winograd : multiplicación de matrices cuadradas
  • Algoritmo de Freivalds : un algoritmo aleatorio utilizado para verificar la multiplicación de matrices
  • Algoritmo de Strassen : multiplicación de matrices más rápida

• Resolver sistemas de ecuaciones lineales
  • Método de gradiente biconjugado : resuelve sistemas de ecuaciones lineales
  • Gradiente conjugado : un algoritmo para la solución numérica de sistemas particulares de ecuaciones lineales.
  • eliminación gaussiana
  • Eliminación de Gauss-Jordan : resuelve sistemas de ecuaciones lineales
  • Método de Gauss-Seidel : resuelve sistemas de ecuaciones lineales de forma iterativa
  • Recursividad de Levinson : resuelve una ecuación que involucra una matriz de Toeplitz
  • Método de Stone : también conocido como procedimiento fuertemente implícito o SIP, es un algoritmo para resolver un sistema lineal disperso de ecuaciones.
  • Sobre-relajación sucesiva (SOR): método utilizado para acelerar la convergencia del método Gauss-Seidel
  • Algoritmo de matriz tridiagonal ( algoritmo de Thomas): resuelve sistemas de ecuaciones tridiagonales
• Algoritmos de matriz dispersa
  • Algoritmo de Cuthill-McKee : reduzca el ancho de banda de una matriz dispersa simétrica
  • Algoritmo de grado mínimo : permutar las filas y columnas de una matriz dispersa simétrica antes de aplicar la descomposición de Cholesky
  • Descomposición simbólica de Cholesky : forma eficiente de almacenar matriz dispersa

Monte Carlo

• Muestreo de Gibbs : genera una secuencia de muestras a partir de la distribución de probabilidad conjunta de dos o más variables aleatorias.
• Monte Carlo híbrido : genera una secuencia de muestras utilizando la cadena de Markov ponderada hamiltoniana Monte Carlo , a partir de una distribución de probabilidad que es difícil de muestrear directamente.
• Algoritmo de Metropolis-Hastings : se utiliza para generar una secuencia de muestras a partir de la distribución de probabilidad de una o más variables.
• Algoritmo de Wang y Landau : una extensión del muestreo del algoritmo de Metropolis-Hastings

Integracion numerica

• Algoritmo MISER : simulación Monte Carlo, integración numérica

Hallazgo de raíz

• Método de bisección
• Método de posición falsa : aproxima las raíces de una función
• Método ITP : convergencia mínima máxima óptima y superlinar simultáneamente
• Método de Newton : encuentra ceros de funciones con cálculo
• Método de Halley : utiliza derivadas primera y segunda
• Método secante : 2 puntos, 1 cara
• Método de posición falsa y método de Illinois: 2 puntos, entre corchetes
• Método de Ridder : escala exponencial de 3 puntos
• Método de Muller : interpolación cuadrática de 3 puntos

Algoritmos de optimización

• Poda alfa-beta : búsqueda para reducir el número de nodos en el algoritmo minimax
• Ramificar y enlazar
• Algoritmo de Bruss : ver algoritmo de probabilidades
• Multiplicación de matrices en cadena
• Optimización combinatoria : problemas de optimización donde el conjunto de soluciones factibles es discreto
  • Procedimiento de búsqueda adaptativa aleatoria codiciosa (GRASP): construcciones sucesivas de una solución aleatoria codiciosa y posteriores mejoras iterativas de la misma a través de una búsqueda local
  • Método húngaro : un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinomial.
• Satisfacción de restricciones
  • Algoritmos generales para la satisfacción de restricciones
    • Algoritmo AC-3
    • Algoritmo de mapa de diferencias
    • Algoritmo de conflictos mínimos
  • Algoritmo de paja : un algoritmo para resolver instancias del problema de satisfacibilidad booleano
  • Algoritmo de Davis-Putnam : comprobar la validez de una fórmula lógica de primer orden
  • Algoritmo de Davis-Putnam-Logemann-Loveland (DPLL): un algoritmo para decidir el satisfacibilidad de fórmula lógica de proposiciones en forma normal conjuntiva , es decir para resolver el CNF-SAT problema
  • Problema de cobertura exacto
    • Algoritmo X : un algoritmo no determinista
    • Dancing Links : una implementación eficiente del algoritmo X
• Método de entropía cruzada : un enfoque general de Monte Carlo para la optimización combinatoria y continua multi-extremal y el muestreo de importancia
• Evolución diferencial
• Programación dinámica : problemas que presentan las propiedades de subproblemas superpuestos y subestructura óptima
• Método elipsoide : es un algoritmo para resolver problemas de optimización convexa.
• Computación evolutiva : optimización inspirada en los mecanismos biológicos de la evolución
  • Estrategia de evolución
  • Programación de expresión genética
  • Algoritmos genéticos
    • Selección proporcional de fitness , también conocida como selección de rueda de ruleta
    • Muestreo universal estocástico
    • Selección de truncamiento
    • Selección de torneo
  • Algoritmo memético
  • Inteligencia de enjambre
    • Optimización de colonias de hormigas
    • Algoritmo de abejas : un algoritmo de búsqueda que imita el comportamiento de búsqueda de alimentos de enjambres de abejas melíferas.
    • Enjambre de particulas
• Algoritmo de Frank-Wolfe : un algoritmo de optimización iterativo de primer orden para la optimización convexa restringida
• Búsqueda de la sección áurea : un algoritmo para encontrar el máximo de una función real
• Descenso de gradiente
• Búsqueda de cuadrícula
• Búsqueda de armonía (HS): un algoritmo metaheurístico que imita el proceso de improvisación de los músicos
• Método de punto interior
• Programación lineal
  • Algoritmo de Benson : un algoritmo para resolver problemas de optimización de vectores lineales
  • Descomposición de Dantzig-Wolfe : un algoritmo para resolver problemas de programación lineal con estructura especial
  • Generación de columna retrasada
  • Programación lineal de enteros : resuelva problemas de programación lineal donde algunas o todas las incógnitas están restringidas a valores enteros
    • Ramificar y cortar
    • Método de plano de corte
  • Algoritmo de Karmarkar : el primer algoritmo razonablemente eficiente que resuelve el problema de programación lineal en tiempo polinomial .
  • Algoritmo simplex : un algoritmo para resolver problemas de programación lineal
• Búsqueda de línea
• Búsqueda local : una metaheurística para resolver problemas de optimización computacionalmente difíciles
  • Escalada de colinas con reinicio aleatorio
  • Búsqueda tabú
• Minimax utilizado en la programación de juegos
• Búsqueda de vecino más cercano (NNS): encuentra los puntos más cercanos en un espacio métrico
  • Best Bin First : encuentre una solución aproximada al problema de búsqueda del vecino más cercano en espacios de muy alta dimensión
• El método de Newton en optimización
• Optimización no lineal
  • Método BFGS : un algoritmo de optimización no lineal
  • Algoritmo de Gauss-Newton : un algoritmo para resolver problemas de mínimos cuadrados no lineales .
  • Algoritmo de Levenberg-Marquardt : un algoritmo para resolver problemas de mínimos cuadrados no lineales .
  • Método de Nelder-Mead ( método simplex cuesta abajo): un algoritmo de optimización no lineal
• Algoritmo de probabilidades ( algoritmo de Bruss): encuentra la estrategia óptima para predecir un último evento específico en un evento de secuencia aleatoria
• Búsqueda aleatoria
• Recocido simulado
• Túneles estocásticos
• Algoritmo de suma de subconjuntos

Ciencia computacional

Astronomía

• Algoritmo del fin del mundo : día de la semana
• La congruencia de Zeller es un algoritmo para calcular el día de la semana para cualquier fecha del calendario juliano o gregoriano
• Se utilizan varios algoritmos de Pascua para calcular el día de Pascua.

Bioinformática

• Herramienta básica de búsqueda de alineación local también conocida como BLAST: un algoritmo para comparar información de secuencia biológica primaria
• Algoritmo de Kabsch : calcule la alineación óptima de dos conjuntos de puntos para calcular la desviación cuadrática media de la raíz entre dos estructuras de proteínas.
• Velvet : un conjunto de algoritmos que manipulan los gráficos de Bruijn para el ensamblaje de secuencias genómicas
• Clasificación por reversiones firmadas : un algoritmo para comprender la evolución genómica.
• Máxima parsimonia (filogenética) : un algoritmo para encontrar el árbol filogenético más simple para explicar una matriz de caracteres determinada.
• UPGMA : un algoritmo de construcción de árboles filogenéticos basado en la distancia.

Geociencia

• Fórmulas de Vincenty : un algoritmo rápido para calcular la distancia entre dos puntos de latitud / longitud en un elipsoide
• Geohash : un algoritmo de dominio público que codifica un par decimal de latitud / longitud como una cadena hash

Lingüística

• Algoritmo de Lesk : desambiguación del sentido de las palabras
• Algoritmo de raíz: un método para reducir las palabras a su forma de raíz, base o raíz
• Algoritmo de Sukhotin : un algoritmo de clasificación estadística para clasificar caracteres en un texto como vocales o consonantes

Medicamento

• Algoritmo ESC para el diagnóstico de insuficiencia cardíaca
• Criterios de Manning para el síndrome del intestino irritable
• Algoritmos de diagnóstico de embolia pulmonar
• Proyecto de algoritmo de medicación de Texas

Física

• Algoritmo de restricción : una clase de algoritmos para satisfacer restricciones para cuerpos que obedecen las ecuaciones de movimiento de Newton.
• Algoritmo de demonio : un método de Monte Carlo para muestrear de manera eficiente miembros de un conjunto microcanónico con una energía determinada
• Algoritmo de Featherstone : calcula los efectos de las fuerzas aplicadas a una estructura de articulaciones y enlaces
• Aproximación del estado fundamental
  • Método variacional
    • Método Ritz
• problemas de n -body
  • Simulación de Barnes-Hut : resuelve el problema de n cuerpos de una manera aproximada que tiene el orden O ( n log n ) en lugar de O ( n ² ) como en una simulación de suma directa.
  • Método rápido multipolar (FMM): acelera el cálculo de fuerzas de largo alcance
• Algoritmo de recuento de flujo de lluvia : reduce un historial de estrés complejo a un recuento de inversiones de estrés elementales para su uso en análisis de fatiga
• Barrido y poda : un algoritmo de fase amplio que se utiliza durante la detección de colisiones para limitar el número de pares de sólidos que deben comprobarse en busca de colisiones.
• Algoritmo VEGAS : un método para reducir el error en las simulaciones de Monte Carlo
• Dinámica de Glauber : un método para simular el modelo de Ising en una computadora

Estadísticas

• Algoritmos para calcular la varianza : evitar la inestabilidad y el desbordamiento numérico
• Algoritmo de recuento aproximado : permite contar una gran cantidad de eventos en un registro pequeño
• Estadísticas bayesianas
  • Algoritmo de muestreo anidado : un enfoque computacional al problema de comparar modelos en estadísticas bayesianas
• Algoritmos de agrupación
  • Agrupación de enlaces promedio : un algoritmo de agrupación de aglomeraciones simple
  • Algoritmo de agrupación en clústeres de dosel : un algoritmo de agrupación previa no supervisado relacionado con el algoritmo K-means
  • Agrupación de agrupamiento de enlace completo : un algoritmo de agrupación de aglomeración simple
  • DBSCAN : un algoritmo de agrupamiento basado en densidad
  • Algoritmo de maximización de expectativas
  • Agrupación difusa : una clase de algoritmos de agrupación en la que cada punto tiene un grado de pertenencia a agrupaciones.
    • C-significa difuso
    • Agrupación de FLAME ( agrupación difusa por aproximación local de membresías): defina agrupaciones en las partes densas de un conjunto de datos y realice la asignación de agrupaciones basándose únicamente en las relaciones de vecindad entre objetos
  • Algoritmo de agrupación en clústeres KHOPCA : un algoritmo de agrupación en clústeres local, que produce agrupaciones jerárquicas de varios saltos en entornos estáticos y móviles.
  • Clustering de k-means : agrupar objetos basados ​​en atributos en particiones
  • k-means ++ : una variación de esto, usando semillas aleatorias modificadas
  • k-medoids : similares a k-medias, pero elige puntos de datos o medoids como centros
  • Algoritmo Linde-Buzo-Gray : un algoritmo de cuantificación vectorial para derivar un buen libro de códigos
  • Algoritmo de Lloyd (iteración o relajación de Voronoi): agrupe los puntos de datos en un número determinado de categorías, un algoritmo popular para la agrupación en clústeres de k-medias
  • ÓPTICA : un algoritmo de agrupamiento basado en densidad con un método de evaluación visual
  • Agrupación de un solo enlace : un algoritmo de agrupación de aglomeración simple
  • SUBCLU : un algoritmo de agrupamiento subespacial
  • Método de Ward : un algoritmo de agrupamiento aglomerativo, extendido a algoritmos más generales de Lance-Williams
  • Algoritmo de agrupación en clústeres WACA : un algoritmo de agrupación en clústeres local con estructuras potencialmente de varios saltos; para redes dinámicas
• Teoría de la estimación
  • Algoritmo de maximización de expectativas Una clase de algoritmos relacionados para encontrar estimaciones de máxima verosimilitud de parámetros en modelos probabilísticos.
    • Maximización Ordenadas subconjunto expectativa (OSEM): se utiliza en imágenes médicas para la tomografía por emisión de positrones , tomografía computarizada por emisión de fotón único y de rayos X de tomografía computarizada.
  • Algoritmo de probabilidades ( algoritmo de Bruss) Búsqueda en línea óptima de valor distinguido en entrada aleatoria secuencial
  • Filtro de Kalman : estima el estado de un sistema dinámico lineal a partir de una serie de mediciones ruidosas
• El algoritmo de vecino más cercano falso (FNN) estima la dimensión fractal
• Modelo de Markov oculto
  • Algoritmo de Baum-Welch : calcula estimaciones de máxima verosimilitud y estimaciones de modo posterior para los parámetros de un modelo de Markov oculto
  • Algoritmo hacia adelante y hacia atrás : un algoritmo de programación dinámica para calcular la probabilidad de una secuencia de observación particular
  • Algoritmo de Viterbi : encuentre la secuencia más probable de estados ocultos en un modelo de Markov oculto
• Regresión de mínimos cuadrados parciales : encuentra un modelo lineal que describe algunas variables predichas en términos de otras variables observables
• Teoría de colas
  • Algoritmo de Buzen : un algoritmo para calcular la constante de normalización G (K) en el teorema de Gordon-Newell
• RANSAC (abreviatura de "RANdom SAmple Consensus"): un método iterativo para estimar los parámetros de un modelo matemático a partir de un conjunto de datos observados que contiene valores atípicos
• Algoritmo de puntuación : es una forma del método de Newton que se utiliza para resolver numéricamente ecuaciones de máxima verosimilitud.
• Método de Yamartino : calcule una aproximación a la desviación estándar σθ de la dirección del viento θ durante una sola pasada a través de los datos entrantes
• Algoritmo Zigurat : genera números aleatorios a partir de una distribución no uniforme.

Ciencias de la Computación

Arquitectura de Computadores

• Algoritmo de Tomasulo : permite que las instrucciones secuenciales que normalmente estarían estancadas debido a ciertas dependencias se ejecuten de forma no secuencial

Gráficos de computadora

• Recorte
  • Recorte de línea
    • Cohen – Sutherland
    • Cyrus – Beck
    • Recorte rápido
    • Liang – Barsky
    • Nicholl – Lee – Nicholl
  • Recorte de polígono
    • Sutherland – Hodgman
    • Vatti
    • Weiler – Atherton
• Líneas de contorno e isosuperficies
  • Cubos de marcha : extrae una malla poligonal de una isosuperficie de un campo escalar tridimensional (a veces llamado vóxeles)
  • Cuadrados de marcha : genera líneas de contorno para un campo escalar bidimensional
  • Tetraedros en marcha : una alternativa a los cubos en marcha
• Teorema de Green discreto : es un algoritmo para calcular la integral doble sobre un dominio rectangular generalizado en tiempo constante. Es una extensión natural del algoritmo de tabla de áreas sumadas.
• Relleno de inundación : llena una región conectada de una matriz multidimensional con un símbolo específico
• Algoritmos de iluminación global : Considera la iluminación directa y la reflexión de otros objetos.
  • Oclusión ambiental
  • Seguimiento de haz
  • Rastreo de cono
  • Iluminación basada en imágenes
  • Transporte ligero Metropolis
  • Seguimiento de ruta
  • Mapeo de fotones
  • Radiosidad
  • trazado de rayos
• Eliminación de superficies ocultas o determinación visual de superficies
  • Algoritmo de Newell : elimine los ciclos de polígonos en la clasificación de profundidad requerida en la eliminación de superficies ocultas
  • Algoritmo del pintor : detecta partes visibles de un escenario tridimensional
  • Renderizado de línea de exploración : construye una imagen moviendo una línea imaginaria sobre la imagen
  • Algoritmo Warnock
• Dibujo lineal : algoritmo gráfico para aproximar un segmento de línea en medios gráficos discretos.
  • Algoritmo de línea de Bresenham : traza puntos de una matriz bidimensional para formar una línea recta entre 2 puntos especificados (usa variables de decisión)
  • Algoritmo de línea DDA : traza puntos de una matriz bidimensional para formar una línea recta entre 2 puntos especificados (usa matemáticas de punto flotante)
  • Algoritmo de línea de Xiaolin Wu : algoritmo para antialiasing de línea.
• Algoritmo de círculo de punto medio : un algoritmo utilizado para determinar los puntos necesarios para dibujar un círculo
• Algoritmo de Ramer-Douglas-Peucker : dada una 'curva' compuesta de segmentos de línea para encontrar una curva no muy diferente pero que tenga menos puntos
• Sombreado
  • Sombreado de Gouraud : un algoritmo para simular los diferentes efectos de la luz y el color en la superficie de un objeto en gráficos por computadora en 3D
  • Sombreado Phong : un algoritmo para interpolar vectores normales de superficie para sombreado de superficie en gráficos por computadora en 3D
• Slerp (interpolación lineal esférica): interpolación de cuaterniones con el fin de animar la rotación 3D
• Tabla de área sumada (también conocida como imagen integral): un algoritmo para calcular la suma de valores en un subconjunto rectangular de una cuadrícula en tiempo constante

Criptografía

• Cifrado asimétrico (clave pública) :
  • ElGamal
  • Criptografía de curva elíptica
  • MAE1
  • NTRUEncrypt
  • RSA
• Firmas digitales (autenticación asimétrica):
  • DSA y sus variantes:
    • ECDSA y ECDSA determinista
    • EdDSA (Ed25519)
  • RSA
• Funciones hash criptográficas (consulte también la sección sobre códigos de autenticación de mensajes):
  • BLAKE
  • MD5 : tenga en cuenta que ahora existe un método para generar colisiones para MD5
  • RIPEMD-160
  • SHA-1 : tenga en cuenta que ahora existe un método para generar colisiones para SHA-1
  • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
  • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
  • Tigre (TTH), generalmente utilizado en hashes de árboles de tigre
  • TORBELLINO
• Generadores de números pseudoaleatorios criptográficamente seguros
  • Blum Blum Shub : basado en la dureza de la factorización
  • Fortuna , pensado como una mejora en el algoritmo de Milenrama
  • Registro de desplazamiento de retroalimentación lineal (nota: muchos algoritmos basados ​​en LFSR son débiles o se han roto)
  • Algoritmo de milenrama
• Intercambio de llaves
  • Intercambio de claves Diffie-Hellman
  • Curva elíptica Diffie-Hellman (ECDH)
• Funciones de derivación de claves , a menudo utilizadas para el hash de contraseñas y el estiramiento de claves
  • bcrypt
  • PBKDF2
  • scrypt
  • Argón2
• Códigos de autenticación de mensajes (algoritmos de autenticación simétrica, que toman una clave como parámetro):
  • HMAC : autenticación de mensajes con clave hash
  • Poli1305
  • SipHash
• Uso compartido de secretos , división de secretos, división de claves, algoritmos M de N
  • El plan de Blakey
  • El plan de Shamir
• Cifrado simétrico (clave secreta) :
  • Estándar de cifrado avanzado (AES), ganador del concurso NIST , también conocido como Rijndael
  • Pez globo
  • Dos peces
  • Tres peces
  • Estándar de cifrado de datos (DES), a veces algoritmo DE, ganador del concurso de selección de NBS, reemplazado por AES para la mayoría de los propósitos
  • IDEA
  • RC4 (cifrado)
  • Pequeño algoritmo de cifrado (TEA)
  • Salsa20 y su variante actualizada ChaCha20
• Criptografía poscuántica
• Algoritmos de prueba de trabajo

Lógica digital

• Minimización booleana
  • Algoritmo de Quine-McCluskey : también llamado algoritmo QM, método programable para simplificar las ecuaciones booleanas.
  • Método de Petrick : otro algoritmo de simplificación booleana.
  • Minimizador lógico heurístico de Espresso : algoritmo rápido para la minimización de funciones booleanas.

Aprendizaje automático y clasificación estadística

• ALOPEX : un algoritmo de aprendizaje automático basado en correlación
• Aprendizaje de reglas de asociación : descubra relaciones interesantes entre variables, utilizadas en la minería de datos
  • Algoritmo a priori
  • Algoritmo Eclat
  • Algoritmo de crecimiento FP
  • Regla de un atributo
  • Regla de atributo cero
• Impulso (meta-algoritmo) : use muchos estudiantes débiles para aumentar la efectividad
  • AdaBoost : refuerzo adaptativo
  • BrownBoost : un algoritmo de impulso que puede ser robusto para conjuntos de datos ruidosos
  • LogitBoost : aumento de la regresión logística
  • LPBoost : programación lineal impulsar
• Bootstrap aggregating (ensacado): técnica para mejorar la estabilidad y precisión de clasificación
• Visión por computador
  • Grabcut basado en cortes de Graph
• Árboles de decisión
  • Algoritmo C4.5 : una extensión de ID3
  • Algoritmo ID3 (dicotomizador iterativo 3): use heurística para generar pequeños árboles de decisión
• Agrupación : una clase de algoritmos de aprendizaje no supervisados para agrupar y agrupar vectores de entrada relacionados.
  • k vecinos más cercanos (k-NN): un método para clasificar objetos basado en ejemplos de entrenamiento más cercanos en el espacio de características
• Algoritmo de Linde-Buzo-Gray : un algoritmo de cuantificación de vectores utilizado para derivar un buen libro de códigos
• Hash sensible a la localidad (LSH): un método para realizar una reducción de dimensión probabilística de datos de alta dimensión
• Red neuronal
  • Retropropagación : un método de aprendizaje supervisado que requiere un maestro que sepa, o pueda calcular, el resultado deseado para cualquier entrada dada.
  • Hopfield net : una red neuronal recurrente en la que todas las conexiones son simétricas
  • Perceptron : el tipo más simple de red neuronal feedforward: un clasificador lineal .
  • Redes neuronales acopladas por pulsos (PCNN): modelos neuronales propuestos mediante el modelado de la corteza visual de un gato y desarrollados para el procesamiento de imágenes biomiméticas de alto rendimiento .
  • Red de función de base radial : una red neuronal artificial que utiliza funciones de base radial como funciones de activación.
  • Mapa autoorganizado : una red no supervisada que produce una representación de baja dimensión del espacio de entrada de las muestras de entrenamiento.
• Bosque aleatorio : clasifique utilizando muchos árboles de decisión
• Aprendizaje por refuerzo :
  • Q-learning : aprende una función de valor de acción que brinda la utilidad esperada de tomar una acción determinada en un estado dado y seguir una política fija a partir de entonces.
  • Estado-Acción-Recompensa-Estado-Acción (SARSA): aprenda una política de proceso de decisión de Markov
  • Aprendizaje de la diferencia temporal
• Máquina de vectores de relevancia (RVM): similar a SVM, pero proporciona una clasificación probabilística
• Aprendizaje supervisado : aprendizaje mediante ejemplos (conjunto de datos etiquetado dividido en conjunto de entrenamiento y conjunto de prueba)
• Máquina de vectores de soporte (SVM): un conjunto de métodos que dividen datos multidimensionales al encontrar un hiperplano de división con el margen máximo entre los dos conjuntos
  • SVM estructurado : permite el entrenamiento de un clasificador para etiquetas de salida estructuradas generales.
• Algoritmo de aventar : relacionado con el perceptrón, pero utiliza un esquema de actualización de peso multiplicativo

Teoría del lenguaje de programación

• Linealización C3 : un algoritmo utilizado principalmente para obtener una linealización consistente de una jerarquía de herencia múltiple en la programación orientada a objetos.
• Algoritmo de Chaitin : un algoritmo de asignación de registros de coloración de gráficos de abajo hacia arriba que utiliza costo / grado como métrica de derrame
• Algoritmo de inferencia de tipo Hindley-Milner
• Algoritmo Rete : un algoritmo de coincidencia de patrones eficiente para implementar sistemas de reglas de producción
• Algoritmo Sethi-Ullman : genera código óptimo para expresiones aritméticas

Analizando

• Algoritmo CYK : un algoritmo O (n ³ ) para analizar gramáticas libres de contexto en la forma normal de Chomsky
• Analizador de Earley : otro algoritmo O (n ³ ) para analizar cualquier gramática libre de contexto
• Analizador GLR : un algoritmo para analizar cualquier gramática libre de contexto de Masaru Tomita . Está afinado para gramáticas deterministas, en las que realiza un tiempo casi lineal y O (n ³ ) en el peor de los casos.
• Algoritmo de adentro hacia afuera : un algoritmo O (n ³ ) para volver a estimar las probabilidades de producción en gramáticas probabilísticas libres de contexto
• Analizador de LL : un algoritmo de análisis de tiempo lineal relativamente simple para una clase limitada de gramáticas libres de contexto
• Analizador LR : un algoritmo de análisis de tiempo lineal más complejo para una clase más grande de gramáticas libres de contexto . Variantes:
  • Analizador LR canónico
  • Analizador LALR (LR anticipado)
  • Analizador de precedencia de operadores
  • Analizador SLR (Simple LR)
  • Analizador de precedencia simple
• Analizador de Packrat : un algoritmo de análisis de tiempo lineal que admite algunas gramáticas libres de contexto y gramáticas de expresión de análisis
• Analizador sintáctico de descenso recursivo : un analizador de arriba hacia abajo adecuado para las gramáticas LL ( k )
• Algoritmo del patio de maniobras : convierta una expresión matemática de notación infija en sufijo
• Analizador de Pratt
• Análisis léxico

Algoritmos cuánticos

• Algoritmo Deutsch – Jozsa : criterio de equilibrio para la función booleana
• Algoritmo de Grover : proporciona aceleración cuadrática para muchos problemas de búsqueda
• Algoritmo de Shor : proporciona una aceleración exponencial (en relación con los algoritmos no cuánticos conocidos actualmente) para factorizar un número
• Algoritmo de Simon : proporciona una aceleración exponencial demostrable (en relación con cualquier algoritmo no cuántico) para un problema de caja negra

Teoría de la computación y los autómatas

• El algoritmo de Hopcroft , el algoritmo de Moore , y el algoritmo de Brzozowski : algoritmos para reducir al mínimo el número de estados en un autómata finito determinista
• Construcción Powerset : Algoritmo para convertir un autómata no determinista en un autómata determinista .
• Algoritmo de Tarski-Kuratowski : un algoritmo no determinista que proporciona un límite superior para la complejidad de las fórmulas en la jerarquía aritmética y la jerarquía analítica

Teoría de la información y procesamiento de señales

Teoría de la codificación

Detección y corrección de errores

• Códigos BCH
  • Algoritmo de Berlekamp-Massey
  • Algoritmo Peterson-Gorenstein-Zierler
  • Corrección de errores de Reed-Solomon
• Algoritmo BCJR : decodificación de códigos de corrección de errores definidos en rejillas (principalmente códigos convolucionales)
• Corrección de errores hacia adelante
• Código gris
• Códigos de Hamming
  • Hamming (7,4) : un código Hamming que codifica 4 bits de datos en 7 bits agregando 3 bits de paridad
  • Distancia de Hamming : suma del número de posiciones que son diferentes
  • Peso de Hamming (recuento de población): encuentre el número de 1 bits en una palabra binaria
• Verificaciones de redundancia
  • Adler-32
  • Verificación de redundancia cíclica
  • Algoritmo Damm
  • Suma de comprobación de Fletcher
  • Comprobación de redundancia longitudinal (LRC)
  • Algoritmo de Luhn : un método para validar números de identificación
  • Algoritmo Luhn mod N : extensión de Luhn a caracteres no numéricos
  • Paridad : técnica de detección de errores simple / rápida
  • Algoritmo de Verhoeff

Algoritmos de compresión sin pérdidas

• Transformada de Burrows-Wheeler : preprocesamiento útil para mejorar la compresión sin pérdidas
• Ponderación del árbol de contexto
• Codificación delta : ayuda a la compresión de datos en los que los datos secuenciales ocurren con frecuencia
• Compresión dinámica de Markov : compresión mediante codificación aritmética predictiva
• Codificadores de diccionario
  • Codificación de pares de bytes (BPE)
  • Desinflar
  • Lempel – Ziv
    • LZ77 y LZ78
    • Lempel – Ziv Jeff Bonwick (LZJB)
    • Algoritmo de cadena Lempel – Ziv – Markov (LZMA)
    • Lempel – Ziv – Oberhumer (LZO): orientado a la velocidad
    • Lempel – Ziv – Stac (LZS)
    • Lempel – Ziv – Storer – Szymanski (LZSS)
    • Lempel – Ziv – Welch (LZW)
    • LZWL : variante basada en sílabas
    • LZX
    • Lempel – Ziv Ross Williams (LZRW)
• Codificación de entropía : esquema de codificación que asigna códigos a los símbolos para hacer coincidir las longitudes de los códigos con las probabilidades de los símbolos.
  • Codificación aritmética : codificación de entropía avanzada
    • Codificación de rango : igual que la codificación aritmética , pero vista de una manera ligeramente diferente
  • Codificación Huffman : compresión simple sin pérdidas que aprovecha las frecuencias relativas de caracteres
    • Codificación adaptativa de Huffman : técnica de codificación adaptativa basada en la codificación de Huffman
    • Algoritmo de combinación de paquetes : optimiza la codificación de Huffman sujeta a una restricción de longitud en las cadenas de código
  • Codificación Shannon-Fano
  • Codificación Shannon-Fano-Elias : precursora de la codificación aritmética
• Codificación de entropía con características de entropía conocidas
  • Codificación de Golomb : forma de codificación de entropía que es óptima para alfabetos que siguen distribuciones geométricas
  • Codificación de arroz : forma de codificación de entropía que es óptima para alfabetos que siguen distribuciones geométricas
  • Codificación binaria truncada
  • Codificación unaria : código que representa un número n con n unos seguidos de un cero
  • Códigos universales : codifica números enteros positivos en palabras de código binario
    • Codificación delta , gamma y omega de Elias
    • Codificación exponencial de Golomb
    • Codificación de Fibonacci
    • Codificación de Levenshtein
• Sistema de compresión de imágenes rápido, eficiente y sin pérdidas (FELICS): un algoritmo de compresión de imágenes sin pérdidas
• Codificación incremental : codificación delta aplicada a secuencias de cadenas
• Predicción por coincidencia parcial (PPM): una técnica de compresión de datos estadísticos adaptativos basada en el modelado y la predicción del contexto
• Codificación de longitud de ejecución : compresión de datos sin pérdida que aprovecha las cadenas de caracteres repetidos
• Algoritmo SEQUITUR : compresión sin pérdidas por inferencia gramatical incremental en una cadena

Algoritmos de compresión con pérdida

• 3Dc : un algoritmo de compresión de datos con pérdida para mapas normales
• Compresión de audio y voz
  • Algoritmo de ley A : algoritmo de compresión estándar
  • Predicción lineal excitada por código (CELP): compresión de voz de baja tasa de bits
  • Codificación predictiva lineal (LPC): compresión con pérdida al representar la envolvente espectral de una señal digital de voz en forma comprimida
  • Algoritmo mu-law : compresión de señal analógica estándar o algoritmo de companding
  • Codificación predictiva lineal deformada (WLPC)
• Compresión de imagen
  • Codificación de truncamiento de bloques (BTC): un tipo de técnica de compresión de imágenes con pérdida para imágenes en escala de grises
  • Wavelet Zerotree integrado (EZW)
  • Algoritmos de transformación rápida de coseno ( algoritmos FCT): calcula la transformación de coseno discreta (DCT) de manera eficiente
  • Compresión fractal : método utilizado para comprimir imágenes mediante fractales.
  • Establecer particiones en árboles jerárquicos (SPIHT)
  • Compresión wavelet : forma de compresión de datos muy adecuada para la compresión de imágenes (a veces también compresión de video y compresión de audio)
• Transformar codificación : tipo de compresión de datos para datos "naturales" como señales de audio o imágenes fotográficas
• Compresión de video
• Cuantización vectorial : técnica de uso frecuente en la compresión de datos con pérdida

Procesamiento de señales digitales

• Algoritmo adaptativo-aditivo ( algoritmo AA): encuentre la fase de frecuencia espacial de una fuente de onda observada
• Transformada discreta de Fourier : determina las frecuencias contenidas en una señal (segmento de a)
  • Algoritmo FFT de Bluestein
  • Algoritmo FFT de Bruun
  • Algoritmo Cooley-Tukey FFT
  • Transformada rápida de Fourier
  • Algoritmo FFT de factor primo
  • Algoritmo FFT de Rader
• Algoritmo de plegado rápido : un algoritmo eficiente para la detección de eventos aproximadamente periódicos dentro de los datos de series de tiempo
• Algoritmo de Gerchberg-Saxton : algoritmo de recuperación de fase para planos ópticos
• Algoritmo de Goertzel : identifica un componente de frecuencia particular en una señal. Se puede utilizar para la decodificación de dígitos DTMF .
• Síntesis de cuerdas Karplus-Strong : síntesis de modelado físico para simular el sonido de una cuerda martillada o pulsada o algunos tipos de percusión

Procesamiento de imágenes

• Mejora de contraste
  • Ecualización de histograma : use histograma para mejorar el contraste de la imagen
  • Ecualización adaptativa de histograma : ecualización de histograma que se adapta a los cambios locales de contraste
• Etiquetado de componentes conectados : busque y etiquete regiones disjuntas
• Dithering y half-toning
  • Difusión de errores
  • Dithering de Floyd-Steinberg
  • Dithering ordenado
  • Riemersma titubeando
• Algoritmo de mapa de diferencias de Elser : un algoritmo de búsqueda para problemas generales de satisfacción de restricciones. Utilizado originalmente para microscopía de difracción de rayos X
• Detección de características
  • Detector de bordes astuto : detecta una amplia gama de bordes en imágenes
  • Transformada de Hough generalizada
  • Hough transformar
  • Algoritmo de Marr-Hildreth : un algoritmo de detección temprana de bordes
  • SIFT (transformación de características invariantes de escala): es un algoritmo para detectar y describir características locales en imágenes.
  • SURF ( Funciones robustas aceleradas ) : es un detector de características locales robusto, presentado por primera vez por Herbert Bay et al. en 2006, que se puede utilizar en tareas de visión por computadora como el reconocimiento de objetos o la reconstrucción 3D. Está inspirado en parte por el descriptor SIFT. La versión estándar de SURF es varias veces más rápida que SIFT y sus autores afirman que es más robusta frente a diferentes transformaciones de imágenes que SIFT.
• Deconvolución de Richardson-Lucy : algoritmo de desenfoque de imágenes
• Deconvolución ciega : algoritmo de desenfoque de la imagen cuando se desconoce la función de dispersión de puntos .
• Filtrado de la mediana
• Tallado de costuras : algoritmo de cambio de tamaño de imagen basado en el contenido
• Segmentación : dividir una imagen digital en dos o más regiones.
  • Algoritmo GrowCut : un algoritmo de segmentación interactivo
  • Algoritmo de caminante aleatorio
  • Región en crecimiento
  • Transformación de cuencas hidrográficas : una clase de algoritmos basados ​​en la analogía de cuencas hidrográficas

Ingeniería de software

• Algoritmos de caché
• Conversión CHS : conversión entre sistemas de direccionamiento de disco
• Doble incursión : convierte números binarios a BCD
• Función hash : convierte una gran cantidad de datos, posiblemente de tamaño variable, en un dato pequeño, generalmente un único entero que puede servir como índice en una matriz.
  • Función hash Fowler – Noll – Vo : rápida con baja tasa de colisión
  • Hash de Pearson : calcula solo el valor de 8 bits, optimizado para computadoras de 8 bits
  • Hash de Zobrist : utilizado en la implementación de tablas de transposición
• Algoritmo de clasificación Unicode
• Algoritmo de intercambio Xor : intercambia los valores de dos variables sin usar un búfer

Algoritmos de base de datos

• Algoritmos para la recuperación y el aislamiento aprovechando la semántica (ARIES): recuperación de transacciones
• Unir algoritmos
  • Bloquear bucle anidado
  • Hash join
  • Unión de bucle anidado
  • Unión de clasificación y fusión

Algoritmos de sistemas distribuidos

• Sincronización de reloj
  • Algoritmo de Berkeley
  • El algoritmo de Cristian
  • Algoritmo de intersección
  • El algoritmo de Marzullo
• Consenso (ciencias de la computación) : ponerse de acuerdo sobre un valor único o historial entre procesadores no confiables
  • Algoritmo de consenso Chandra-Toueg
  • Algoritmo de Paxos
  • Balsa (informática)
• Detección de terminación de proceso
  • Algoritmo de Dijkstra-Scholten
  • Algoritmo de Huang
• Lamport pedido : una ordenación parcial de eventos basado en el pasado, antes de relación
• Elección de líder : un método para seleccionar dinámicamente a un coordinador
  • Algoritmo Bully
• Exclusión mutua
  • Algoritmo de exclusión mutua distribuida de Lamport
  • Algoritmo log (n) de Naimi-Trehel
  • Algoritmo de Maekawa
  • Algoritmo de Raymond
  • Algoritmo Ricart – Agrawala
• Algoritmo de instantánea : registre un estado global consistente para un sistema asincrónico
  • Algoritmo de Chandy-Lamport
• Relojes vectoriales : genera una ordenación parcial de eventos en un sistema distribuido y detecta violaciones de causalidad.

Algoritmos de asignación y desasignación de memoria

• Asignación de memoria de amigos : algoritmo para asignar memoria de manera que la fragmentación sea menor.
• Recolectores de basura
  • Algoritmo de Cheney : una mejora en el colector semiespacio
  • Recolector de basura generacional : recolectores de basura rápidos que segregan la memoria por edad
  • Algoritmo Mark-Compact : una combinación del algoritmo Mark-Sweep y el algoritmo de copia de Cheney
  • Marcar y barrer
  • Coleccionista de semiespacio : uno de los primeros coleccionistas de copias
• Recuento de referencias

Redes

• Algoritmo de Karn : aborda el problema de obtener estimaciones precisas del tiempo de ida y vuelta de los mensajes cuando se usa TCP
• Algoritmo de Luleå : una técnica para almacenar y buscar tablas de enrutamiento de Internet de manera eficiente
• Congestión en la red
  • Retroceso exponencial
  • Algoritmo de Nagle : mejore la eficiencia de las redes TCP / IP mediante la fusión de paquetes
  • Retroceso exponencial binario truncado

Algoritmos de sistemas operativos

• Algoritmo de banquero : algoritmo utilizado para evitar interbloqueos.
• Algoritmos de reemplazo de página : selección de la página víctima en condiciones de poca memoria.
  • Caché de reemplazo adaptable : mejor rendimiento que LRU
  • Reloj con reemplazo adaptable (CAR): es un algoritmo de reemplazo de página que tiene un rendimiento comparable al caché de reemplazo adaptable

Sincronización de procesos

• Algoritmo de Dekker
• Algoritmo de panadería de Lamport
• Algoritmo de Peterson

Planificación

• Fecha límite más temprana primera programación
• Programación equitativa
• Programación del menor tiempo de inactividad
• Programación de listas
• Cola de retroalimentación de varios niveles
• Programación de tarifas monótona
• Programación por turnos
• Siguiente trabajo más corto
• El tiempo restante más corto
• Algoritmo de nodos superiores : gestión del calendario de recursos

Programación de E / S

Programación de disco

• Algoritmo de elevador : algoritmo de programación de disco que funciona como un elevador.
• La búsqueda más corta primero : algoritmo de programación de disco para reducir el tiempo de búsqueda .

Ver también

• Lista de estructuras de datos
• Lista de algoritmos de aprendizaje automático
• Lista de algoritmos de búsqueda de rutas
• Lista de temas generales de algoritmos
• Lista de términos relacionados con algoritmos y estructuras de datos
• Heurístico

Referencias