TECNOLOGIA EN REDES Y TELECOMUNICACIONES

ALEXANDER JACOME RIVERA

20 ALGORITMOS MÁS IMPORTANTES

15 DE AGOSTO 2010

TRC260-40

Los 20 Algoritmos más importantes

1) Algoritmo de Metrópolis-Hastings

Este algoritmo construye una cadena de Markov apropiada definiendo las probabilidades de transición

2) Método Simplex

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

3) Métodos del subespacio de Krylov

Los métodos del subespacio de Krylov forman una base ortogonal de la secuencia de potencias de la matriz por el residuo inicial (la secuencia de Krylov). Las aproximaciones a la solución se forman minimizando el residuo en el subespacio formado. El método prototípico de esta clase es el método de gradiente conjugado. Otros métodos son el método del residuo mínimo generalizado y el método del gradiente biconjugado.

4) La descomposición de la matriz Householder.

Transformación de Householder

En matemáticas, una transformación de Householder es una transformación lineal del espacio que consiste en una reflexión pura con respecto a un plano. Viene definida por una matriz de dimensión (N x N) tal que para cualquier vector de dimensión N se

cumple que es la reflexión de respecto a un plano .

5) El compilador fortran.

El Fortran (previamente FORTRAN)[1] (del inglés Formula Translating System) es un lenguaje de programación alto nivel de propósito general,[2] procedurimental[3] e imperativo, que está especialmente adaptado al cálculo numérico y a la computación científica. Desarrollado originalmente por IBM en 1957 para el equipo IBM 704, y usado para aplicaciones científicas y de ingeniería, el FORTRAN vino a dominar esta área de la programación desde el principio y ha estado en uso continuo por más de medio siglo en áreas de cómputo intensivo tales como la predicción numérica del tiempo, análisis de elementos finitos, dinámica de fluidos computacional (CFD), física computacional, y química computacional. Es una de los lenguajes más populares en el

área de la computación de alto rendimiento y es el lenguaje usado para programas que evalúan el desempeño (benchmark) y el ranking de los supercomputadores más rápidos del mundo.[4]

El FORTRAN (una palabra compuesta, derivada de The IBM Mathematical Formula Translating System) abarca un linaje de versiones, cada una de las cuales evolucionó para añadir extensiones al lenguaje mientras que usualmente retenía compatibilidad con las versiones previas. Versiones sucesivas han añadido soporte para procesamiento de datos basados en caracteres (FORTRAN 77), programación de arreglos, programación modular y programación orientada a objetos (Fortran 90/95), y programación genérica (Fortran 2003).

6) El algoritmo de descomposición para la obtención de autovalores QR.

En álgebra lineal, la descomposición o factorización QR de una matriz es una descomposición de la misma como producto de una matriz ortogonal por una triangular superior. La descomposición QR es la base del algoritmo QR utilizado para el cálculo de los vectores y valores propios de una matriz.

7) El algoritmo de quicksort.

Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

8) La transformada rápida de Fourier.

Para otros usos de este término, véase Transformación (desambiguación).

FFT es la abreviatura usual (del inglés Fast Fourier Transform) de un eficiente algoritmo que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones diferenciales parciales o los algoritmos de multiplicación rápida de grandes enteros. El algoritmo pone algunas limitaciones en la señal y en el espectro resultante. Por ejemplo: la señal de la que se tomaron muestras y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores TRF permiten la transformación de 512, 1024, 2048 o 4096 muestras. El rango de frecuencias cubierto por el análisis TRF depende de la cantidad de muestras recogidas y de la proporción de muestreo.

9) Algoritmo de detección de relación entre enteros.

En matemáticas, computación y teoría de la información, la detección y corrección de errores es una importante práctica para el mantenimiento e integridad de los datos a través de canales ruidosos y medios de almacenamiento poco confiables.

10) Método del multipolo rápido.

11) Algoritmos voraces (greedy)

Seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.

12) Algoritmos paralelos

Permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.

13) Algoritmos probabilísticos

Algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios.

14) Algoritmos determinísticos

El comportamiento del algoritmo es lineal: cada paso del algoritmo tiene únicamente un paso sucesor y otro antecesor.

15) Algoritmos no determinísticos

El comportamiento del algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.

16) Divide y vencerás

Dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.

17) Metaheurísticas

Encuentran soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.

17)Programación dinámica

Intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.

18)Ramificación y acotación

Se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.

19) Vuelta atrás (backtracking)

Se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas.