Ir al contenido principal

Inside the trash can

Buscar este blog

Toda tu vida multiplicaste en forma ineficiente: El algoritmo de Karatsuba

Publicadas por Víctor Podberezski complejidad computacional matemática programación

Obtener vínculo
Facebook
Twitter
Pinterest
Correo electrónico
Otras apps

Complejidad algorítmica

Publicadas por Víctor Podberezski

Obtener vínculo
Facebook
Twitter
Pinterest
Correo electrónico
Otras apps

Obtener vínculo
Facebook
Twitter
Pinterest
Correo electrónico
Otras apps

Comentarios

Publicar un comentario

Presentaciones

Redes de flujo
Grafos
División y conquista
Complejidad algorítmica
Algoritmos randomizados
Algoritmos de aproximación

Entradas populares

Por qué las computadoras usan lenguaje binario?

El código binario es el idioma de las computadoras. Construimos abstracciones, lenguajes de alto nivel, pero todo se compila y termina "hablando" en binario. Ceros y unos, unos y ceros. Es así hace años. Parece lógico, parece indiscutible. pero lo es? Para los ajenos al mundo informático el concepto de los números binarios no resulta cómodo. Por qué no almacenar o trabajar con números decimales? Si es lo más común y sencillo? Tenemos 10 dedos en las manos por lo que este sistema con 10 símbolos nos parece intuitivo y natural... entonces por que no usar este sistema?

La historia del número PI y sus infinitos dígitos

Existen infinitos números irracionales. Estos son aquellos que no podemos representar como cociente entre 2 números enteros. Si los queremos expresar como un numero decimal, no podremos dado que tienen infinitas cifras luego de la coma sin un patrón periódico en ellos. Existe no obstante un puñado de ellos que por su utilidad en diversos campos de la ciencia o por cuestiones históricas han salido del anonimato, incluso recibiendo nombre propio. Entre ellos podemos nombrar al número áureo, el número de Euler y por supuesto el número PI. El numero PI - también conocido como "constante de Arquímedes" es un concepto conocido hace miles de años. Representa la relación entre la circunferencia de un circulo y su diámetro. Cualquier empresa constructiva se toparía con él en algún momento. No solo en geometría se utiliza, también para cualquier movimiento periódico o pendular, en señales electrónicas, órbitas de satélites, modelos financieros... entre otros.

Por qué un Byte son 8 bits?

KiloBytes, Megabytes, GigaBytes, TeraBytes... Medidas de capacidad de almacenamiento y procesamiento de información que hemos escuchado durante años. Todas ellas diferentes unidades del Byte. Sabemos que un bit es la unidad mínima de información: si/no, 0/1. Sabemos que 1 Byte son 8bits... pero por qué no son 6bits? 9bits? 12 o cualquier otro número?

Toda tu vida multiplicaste en forma ineficiente: El algoritmo de Karatsuba

Multiplicar dos números enteros es un procedimiento que realizamos habitualmente. Con valores pequeños es un proceso mental automático. Si el requerimiento es con cantidades más grandes, nos podemos ayudar con lapiz y papel.... o le confiamos el resultado a una calculadora digital. Aprendemos a multiplicar en la escuela primaria (elemental). El concepto es sumar "P" veces el número "Q" (suma reiterada) y lo expresamos mediante notación matemática como P x Q. Cada vez que nos encontramos con la necesidad de este cálculo, utilizamos un procedimiento o algoritmo de multiplicación al que llamaremos "tradicional". Tablas de multiplicar. En el método tradicional, utilizando la numeración posicional arábiga con base 10 (existen diez símbolos y el número se compone de unidades, decenas, centenas.... etc de aquellos) debemos como prerequisito memorizar las tablas de multiplicar del 0 al 9. El procedimiento involucra emparejar los dos números y realizar

El juego de Kevin Bacon - Las conexiones en una red social

Existe un juego y desafío donde una persona indica un actor y el contrincante debe ir encadenando actores que fueron compañeros en alguna película hasta llegar a Kevin Bacon. Por ejemplo, Al pacino trabajó en 1974 con Robert Duval en "The Godfather: Part II". Duvall trabajó en 2012 con Kevin Bacon en el film "Jayne Mansfield's Car". Los actores conforman una red vinculados por su filmografía. El reto no es solo encontrar el camino sino que debe intentarse que sea en menos de 6 pasos. Las características de ciertas redes pueden explicar como circula información (noticias, chismes o de otro tipo) así como enfermedades o influencias. Su estudio es un campo fértil de investigación empujado por el auge de las redes sociales.

La neurona artificial de McCulloch-Pitts: El puntapie a los exitos actuales de las redes neuronales

Componer música pop o clásica, pintar un cuadro expresionista o cubista, manejar un auto, jugar al ajedrez o al GO... ¿Qué tienen en común todas estas actividades? Podríamos conjeturar que son actividades que una misma persona podría practicar. Tal vez algunas con apenas rudimento y otras con gran maestría. La mayoría concordará que son habilidades humanas. Pero eso a dejado de ser así. Las inteligencias artificiales comienzan a realizar estas tareas - y otras tantas - con maestría. La imagen que encabeza esta nota fue generada por Deep Dream una inteligencia artificial construida por Google. Ingresando a su sitio nos permite ver diferentes co-creaciones entre usuarios y la IA. También nos permite explorar y crear las propias. Investigaciones de universidades como la Universidad de Tübingen, Alemania trabajan sobre el mismo principio. Empresas como Uber, Google, Volvo, Audi entre otras empresas persiguen la creación de autos autónomos. Tema del que ya hablamos en " El su

Un código criptográfico en la biblia

Dentro de la hermenéutica y la exégesis bíblica es común la búsqueda de un significado de los versículos intentando buscar una interpretación diferente de las palabras que contiene. Algunas prácticas incluyen calcular el valor numérico de cada palabra. En el hebreo cada letra tiene un valor asociado y por lo tanto una palabra puede calcularse como la suma de sus letras. También se suelen aplicar interpretaciones de porque ciertas palabras son utilizadas en cierto contexto. Otra práctica, popularizada con el advenimiento del poder computacional, es buscar códigos secretos en el texto bíblico con predicciones sobre hechos del pasado reciente o del futuro. Este método se hizo conocido con el libro, best sellers "El código secreto de la biblia" publicado en 1997. El autor cuenta el proceso realizado por un matemático de formar palabras utilizando la biblia buscando letras a cierta distancia regular de otras (más detalles acá ). En este caso nos interesa otro tipo de c

La neurona: Su descubrimiento y el polémico Nobel de 1906

El Premio Nobel 1906 en Fisiología o Medicina , en reconocimiento a su trabajo sobre la estructura del sistema nervioso, fue compartido entre dos cientificos. Santiago Ramón y Cajal , nacido en España y Camillo Golgi , italiano, fueron laureados ese año. Lo sorprendente es que ambos sostenían una teoría opuesta sobre el mismo principio. La doctrina reticular defendida por Golgi era incompatible con la doctrina neuronal propuesta por Ramón y Cajal. En su discurso de aceptación del premio, Golgi, no hizo más que intentar desacreditar la teoría de su acérrimo rival español. ¿Cómo es que fueron seleccionados ambos por el comité para compartir el premio? ¿De qué hablaba cada doctrina?

Con tecnología de Blogger