¿Qué algoritmos aprenden los estudiantes de informática? ¿Qué libros puedo leer? ¿Qué conceptos básicos necesito aprender?

Algoritmo de búsqueda A*

Comúnmente conocido como algoritmo de estrella A. Este es un algoritmo para encontrar el costo transversal más bajo de una ruta con múltiples nodos en el plano del gráfico. A menudo se utiliza para la computación móvil de NPC en juegos o BOT en juegos en línea. Al igual que el algoritmo de Dijkstra, este algoritmo puede encontrar el camino más corto. Al igual que BFS, se realiza una búsqueda heurística.

Búsqueda por haz

El método de búsqueda por haz es un método heurístico para resolver problemas de optimización. Se desarrolla sobre la base del método de rama y encuadernación. Utiliza un método heurístico para estimar k rutas óptimas y solo busca hacia abajo desde estas k rutas, es decir, solo se retienen los nodos satisfactorios en cada capa y otros nodos se descartan permanentemente. En comparación con el método de ramificación y unión. puede ahorrar mucho tiempo de ejecución. La búsqueda por haz se utilizó por primera vez en el campo de la inteligencia artificial a mediados de la década de 1970. En 1976, Lowerre utilizó por primera vez el método de búsqueda por haz en su sistema de reconocimiento de voz llamado HARPY. Su objetivo es buscar varias posibles rutas de decisión óptimas en paralelo para reducir el retroceso y obtener rápidamente una solución.

Algoritmo de búsqueda binaria

Un algoritmo de búsqueda para encontrar elementos específicos en una matriz ordenada. El proceso de búsqueda comienza desde el elemento central de la matriz y finaliza si el elemento central es exactamente el elemento a buscar; si el elemento específico es mayor o menor que el elemento central, la búsqueda se realiza en la mitad de la matriz que se encuentra; más grande o más pequeño que el elemento del medio y comenzar a comparar desde el elemento del medio. Este algoritmo de búsqueda reduce el rango de búsqueda a la mitad con cada comparación.

Bifurcación y límite

El algoritmo de rama y límite es un método para buscar una solución a un problema en el árbol del espacio de soluciones del problema. Sin embargo, a diferencia del algoritmo de retroceso, el algoritmo de ramificación y vinculación utiliza el método de primero en amplitud o de costo mínimo primero para buscar en el árbol del espacio de soluciones. En el algoritmo de ramificación y vinculación, cada nodo activo tiene solo una oportunidad de hacerlo. convertirse en un nodo de expansión.

Compresión de datos

La compresión de datos es una tecnología que aumenta la densidad de los datos y, en última instancia, reduce el espacio de almacenamiento de datos al reducir la redundancia de los datos almacenados en las computadoras o los datos en las comunicaciones. La compresión de datos se utiliza ampliamente en el almacenamiento de archivos y en los sistemas distribuidos. La compresión de datos también representa un aumento en el tamaño de la capacidad de los medios y una expansión del ancho de banda de la red.

Acuerdo de claves Diffie-Hellman

El intercambio de claves Diffie-Hellman (D-H para abreviar) es un protocolo de seguridad. Permite que dos partes establezcan claves a través de un canal inseguro sin requerir información previa sobre la otra parte. Esta clave se puede utilizar como clave simétrica para cifrar las comunicaciones en comunicaciones posteriores.

Algoritmo de Dijkstra

El algoritmo de Dijkstra fue inventado por el informático holandés Edsger Dijkstra. Este algoritmo resuelve el problema del camino más corto desde un único punto fuente a otros vértices en un gráfico dirigido. Por ejemplo, si los vértices del gráfico representan ciudades y los pesos en los bordes representan la distancia de conducción entre ciudades, el algoritmo de Dikoscher se puede utilizar para encontrar el camino más corto entre dos ciudades.

Programación dinámica

La programación dinámica es un método en matemáticas e informática que se utiliza para resolver problemas de optimización con subproblemas superpuestos. La idea básica es descomponer el problema original en subproblemas similares. En el proceso de resolución, la solución al problema original se obtiene resolviendo los subproblemas. Las ideas de programación dinámica son la base de muchos algoritmos y se utilizan ampliamente en informática e ingeniería. Ejemplos de aplicaciones famosas incluyen: resolución del problema del camino más corto, problema de mochila, gestión de proyectos, optimización del tráfico de red, etc. Aquí tenéis un artículo con más detalles.

Algoritmo euclidiano

En matemáticas, la división transitiva, también conocida como algoritmo euclidiano, es un algoritmo para encontrar el máximo común divisor. La división de fases apareció por primera vez en los "Elementos de geometría" de Euclides (Volumen 7, Proposiciones 1 y 2), y en China se remonta a "Nueve capítulos sobre aritmética" y apareció en la dinastía Han del Este.

Algoritmo de expectativa máxima

En informática estadística, el algoritmo de expectativa máxima (EM) es un algoritmo para encontrar estimaciones de máxima verosimilitud de parámetros en un modelo probabilístico que se basa en variables ocultas no observables. La expectativa máxima se utiliza a menudo en el campo de la agrupación de datos en el aprendizaje automático y la visión por computadora. El algoritmo de expectativa máxima se calcula alternativamente en dos pasos.

El primer paso es calcular la expectativa (e), utilizando los valores estimados existentes para calcular la estimación de máxima verosimilitud de la variable oculta. El segundo paso es maximizar (m), para maximizar el valor de máxima verosimilitud obtenido en el paso e; para calcular el valor de los parámetros. Las estimaciones de los parámetros encontrados en el paso m se utilizan en el cálculo del siguiente paso e, y el proceso avanza alternativamente.

Transformada Rápida de Fourier

La Transformada Rápida de Fourier (FFT) es un algoritmo rápido para la transformada de Fourier discreta y también se puede utilizar para calcular la inversa de la transformada de Fourier discreta. La transformada rápida de Fourier tiene una amplia gama de aplicaciones, como el procesamiento de señales digitales, el cálculo de multiplicaciones de enteros grandes, la resolución de ecuaciones diferenciales parciales, etc.

Función Hash

HashFunction es un método para crear una pequeña huella digital a partir de cualquier tipo de datos. Esta función codifica los datos y recrea una huella digital llamada hash. Un valor hash se utiliza normalmente para representar una cadena corta de letras y números aleatorios. Las buenas funciones hash rara vez provocan colisiones hash en el dominio de entrada. En las tablas hash y el procesamiento de datos, no suprimir las colisiones para diferenciar los datos puede hacer que los registros de la base de datos sean más difíciles de encontrar.

Clasificación de montón

Heapsort se refiere a un algoritmo de clasificación diseñado utilizando la estructura de datos del árbol del montón (montón). Un árbol de montón es una estructura de árbol binario completa aproximada que también satisface la propiedad del montón: es decir, el valor clave o índice de un nodo secundario siempre es menor (o mayor) que su nodo principal.

Ordenación por combinación

La ordenación por combinación es un algoritmo de clasificación eficaz basado en operaciones de combinación. Este algoritmo es una aplicación muy típica de divide y vencerás.

Algoritmo RANSAC

RANSAC es la abreviatura de "RANdom SAmpleConsensus". Este algoritmo es un método iterativo propuesto por Fischler y Bolles en 1981 para estimar los parámetros de un modelo matemático a partir de un conjunto de datos de observación. Es un algoritmo no determinista porque sólo puede obtener resultados razonables con una cierta probabilidad, y esta probabilidad aumenta con el número de iteraciones. El supuesto básico de este algoritmo es que hay "puntos internos" (aquellos puntos que respaldan la estimación de los parámetros del modelo) y "puntos atípicos" (puntos que no se ajustan al modelo) en el conjunto de datos de observación, y este conjunto de datos de observación se ve afectado por el ruido. RANSAC supone que dado un conjunto de datos "inliner", se puede obtener el mejor modelo.

Algoritmo de cifrado RSA

Este es un algoritmo de cifrado de clave pública y el primer algoritmo del mundo adecuado para firmas. La patente RSA actual ha caducado y se utiliza ampliamente en el cifrado del comercio electrónico. Todo el mundo cree que mientras la clave sea lo suficientemente larga, el algoritmo será seguro.

Búsqueda de unión

Union es una estructura de datos en forma de árbol que se utiliza para manejar la fusión y consulta de conjuntos disjuntos. Suele estar representado por un bosque.

Algoritmo de Viterbi

Encuentra la secuencia más probable de estados ocultos.