Portada
mis comunidades
otras secciones
![Los verdaderos 10 algoritmos que dominan nuestro mundo [EN]](https://cdn.mnmstatic.net/cache/21/67/media_thumb_2x-link-2189298.jpeg?1417833704)
#14:
El algoritmo del Karma de Menéame
#1:
Ojo, no tiene nada que ver con esta: Los 10 algoritmos que dominan el mundo
Comentarios
El algoritmo del Karma de Menéame
#14 LOLLLLLL!
Ojo, no tiene nada que ver con esta: Los 10 algoritmos que dominan el mundo
Los 10 algoritmos que dominan el mundo
omicrono.comAquí tenéis explicado el algoritmo de ordenación:
#5 Prefiero:
Lo he leído y he visto los vídeos de #5 y #8 y me voy a pegar un tiro.
#5 Es genial! luego se lo enseño q un compañero de curro que creo que es un adorador de realizar ordenaciones en burbuja en PHP de contenidos no ordenados sacados directamente de una base de datos MySQL ("Yo soy más eficiente ordenando que MySQL" me dice)
#17
#18 Para que te rías más, me ha soltado un par de "Yo soy más eficiencte haciendo XXXXXXX que MySQL". Algun día le responderé que quizás haciendo el café o las tostadas, hasta que MySQL saque un módulo para ello
#17 Curiosamente, sí hay escenarios en los que un algoritmo de burbuja (o cualquier otro n^2) puede ser más rápido que un quick-merge-heap sort. Si el conjunto de datos es pequeño, es más rápido usar un algoritmo de inserción directa o similar, ya que hay menos llamadas a función. También, si los datos están ya ordenados (o casi), un algoritmo de burbuja acaba casi instantáneamente.
Que no quiere decir que una base de datos o librería no tenga esos factores ya en cuenta, y de hecho ya se cuidan de no especificar qué algoritmo usan porque hacen trucos de ese tipo (cualquier algoritmo quick sort medio bueno usa inserción directa cuando el nº de datos es inferior a un umbral). Pero puede haber casos en los que el tipo y/o tamaño de los datos hagan preferible ordenarlos nosotros.
Sólo echo en falta el del simplex
#2 La mayoría de los problemas de optimización no son lineales, el simplex solo lo usan los alumnos de empresariales o de organización industrial en las asignaturas correspondientes.
Vamos a ver, #2 y #4, se trata de una lista de 10 algoritmos, no de 12, de 10. Sin duda alguna, faltarán muchos más que son "importantes", pero el autor remarca cuáles son los 10 más importantes (supongo que por su uso) y lo razona bastante bien.
Es lo que tiene hacer listas acotadas, que siempre te dejas alguno.
Falta la eliminación gaussiana.
Y algoritmos para cálculo de autovalores.
La lista no está mal, pero un regulador PID no es realmente un "algoritmo". Y, desde luego, me parecería razonable añadir, aunque fueran varios algoritmos en un mismo apartado:
1) Algo de álgebra lineal numérica: la reducción gaussiana / factorización LU (como apunta #4), la factorización QR y algo de autovalores / SVD / Krylov, algoritmos muy importantes en computación científica. Incluso aceptaría Page Rank, que está estrechamente relacionado con los problemas de autovalores
2) Algo de algoritmos de optimización (tanto lineal como no-lineal)
Minimax, el padre de los algoritmos de decisión
el mejor algoritmo recursivo es #20
#25 Sí, yo no dije lo contrario.
Dije que en imágenes se usa la DCT y que es una DCT bidimensional porque las imágenes tienen 2D ¡pero no dije que se use la DCT porque no exista una FFT bidimensional!.
¿Y por qué no se usa una FFT / DFT bidimensional en imágenes y recurren a otra, la DCT?
Pues no lo se, aunque intuyo algo... En sonido si introduces un retardo, para el oyente el resultado es casi idéntico... Es muy parecido oir "DO RE MI" y oir "[Silencio] DO RE MI" y su FFT es muy similar: multiplicar por un número complejo (mismas componentes de frecuencias: la nota DO, la nota RE, y la nota MI")... Pero si en una imagen introduces un "retardo" lo que se hace es desplazar la imagen y ya es muy diferente. Entiendo que por esto y por otras razones la DCT representa mejor una información de imágenes.
#26, simplemente era una aclaración por si alguien entendía mal la frase donde la definías. La DCT es más apropiada para imágenes por una cuestión de condiciones de contorno (la DFT está asociada a condiciones periódicas -el caso de un sonido, como bien apuntas-, la DCT no)
La transformada de Fourier no se usa el la compresión MP3 o JPEG ?
#12, en general, la transformada de Fourier y sus variantes y primas (transformada coseno) se usan masivamente en procesamiento de imagen y sonido. También en otros muchos campos.
#12
La psicoacústica trata de cosas como que ciertas frecuencias son menos perceptibles. El truco es codificar con menos bits (menos precisión) las frecuencias menos perceptibles (no sólo frecuencias muy bajas o muy altas sino algunas intermedias que se haya demostrado que el oído no capta muy bien). Y de esa forma, la señal obtenida de compresión MP3 es apenas indistinguible de la grabación original, a pesar de haber perdido el 90% de la información grabada.
Sí y no.
Primero matizar que cuando se dice "Transformada de Fourier" se refiere a la transformada contínua... es decir, para funciones continuas en una variable (típicamente el tiempo t, y típicamente variable real, aunque puede ser compleja) y en general definida en para todos los reales (de -infinito a +infinito) existe una transformada de Fourier que es una función que da un valor complejo para cada valor de otra variable llamada frecuencia (f, en Hz = ciclos por segundo...) o frecuencia angular, omega, "w", en radianes por segundo). Yo diría que la Transformada de Fourier no es un algoritmo sino un concepto / definición. (Igual que la multiplicación es un concepto... y luego está la forma de obtener el producto que ya sería un algoritmo concreto). Ej: para la función f(t) = cos(4*PI*t) cuyo periodo es 0.5 segundos y su frecuencia 2 Hz existiría una transformada que tendría valor nulo para frecuencias diferentes de f=2 y sería no nulo para f=2.
Luego está la "Transformada de Fourier Discreta" (Discrete Fourier Transform ó DFT), que es otro concepto más práctico, ya que exige que la función de entrada sea una secuencia discreta y además de duración finita. Esto es más práctico porque la función de entrada pueden ser unas medidas (valores, números reales llamados "muestras") obtenidos cada cierto tiempo (llamado periodo de muestreo) y no hay que tomar infinitas sino un número finito (sean 20 ó 100 ó 10000). Pero, a pesar de ser un concepto más aplicable a situaciones reales sigue siendo un concepto... y en parte irrealizable ya que en la definición cada muestra puede tener precisión infinita. Por ejemplo, la primera muestra puede ser PI que tiene infinitos decimales, la segunda puede ser el número e, etc.
El algoritmo eficiente correspondiente es FFT (Fast Fourier Transform) que ya no es concepto sino un algoritmo realizable. Cada muestra tiene una precisión (que es causa de un error de muestreo), aparte de haber un número limitado de muestras (lo cual limita la precisión de las frecuencias) y que cada muestra es tomada cada cierto tiempo (lo cual limita la frecuencia máxima).
Pero hasta aquí no hay nada de compresión, salvo quizá el recorte que se haga en la precisión de cada muestra. Es decir, si tenemos una secuencia de 256 muestras de sonido, cada muestra con una precisión de 16 bits... la FFT será una secuencia de 256 valores de frecuencias, con precisión de 16 bits. De forma que el tamaño de la información a la entrada y a la salida de FFT es prácticamente el mismo (normalmente es algo mayor: la salida son 256 valores complejos, y requieren mayor precisión en general, pero podéis creerme si os digo que es prácticamente igual)... y la señal original puede reconstruirse idéntica (si en los valores de la salida de la FFT no se redondeó perdiendo precisión).
Sin embargo, MP3 es un formato comprimido, y con pérdidas (como la codificación usada en telefonía móvil GSM y muchas otras codificaciones de audio). Esto quiere decir que la salida (el fichero MP3) ocupa mucho menos (típicamente 1/10 pero variable dependiendo de la calidad) y que la señal reconstruida a partir del MP3 puede ser bastante diferente a la original. Eso quiere decir que se ha perdido algo de la señal original (por eso se dice que es "lossy", es decir, con pérdidas). ¿y como es posible que perdiendo como el 90% de la información original suene igual? Pues por obra y gracia de la psicoacústica... no confundir con psicofonías
JPEG también es un formato comprimido y con pérdidas... y usa más o menos el mismo "truco" (eliminar información de forma que sea poco perceptible). Sólo que usa otra transformada, la del Coseno, no la de Fourier... aunque ambas son muy parecidas. En concreto se usa la Transformada del Coseno Discreta (DCT), para la cual existe también un algoritmo eficiente (similar a FFT)... eso sí, extendido para señales bidimensionales. Pero el matiz es ese: compresión y pérdidas. Y para comprimir y saber qué se puede perder y qué no hace falta bastante más que una mera transformada, la cual como dije no comprime nada por sí misma.
cc #22
Como he explicado, por mucho que JPEG / MPEG estén basados en algo similar a FFT son algo más. Y la cantidad de datos a los que afecta dicha compresión (fotos y vídeos hechos con móviles o cámaras digitales, todo lo que se ve en la TDT, vídeos de Internet, la mayoría de imágenes de la web, DVD, Blu-Ray...) creo que es de mucha mayor importancia que LZH, el cual de modo perceptible por la mayoría de la gente sólo está en las imágenes GIF. Huffman sí lo acepto como importante ya que se usa en MP3, JPEG, etc... pero teniendo en cuenta que está incluido en ellos y que fuera de ellos creo que se usa poco pues me parece que la falta de mención explícita no es muy grave.
#24, comentario muy informativo, pero la transformada de Fourier también está definida para varias variables: http://en.wikipedia.org/wiki/Fourier_transform#Fourier_transform_on_Euclidean_space
Yo me quedo con este:
Un poco denso si no has estudiado el tema.
Incluso si lo has hecho la complejidad temporal de algoritmos es bastante difícil (el O(n^2) que menciona en el primer algoritmo)
Por si alguien se aburre: http://latecladeescape.com/t/Qu%C3%A9+es+la+complejidad+de+un+algoritmo
Muy interesante
Yo hubiera puesto la FFT en primer lugar. En cuanto al 9, "algoritmos de compresión", son sumamente importantes, pero no lo explica muy bien. Menciona JPEG y MPEG, que están basados en un derivado de la FFT, pero no nombra la codificación de Huffman, la codificación aritmética, o la familia LZW.