insertion sort <- sorting!

7 agosto 2009

Algo apasionante para algunos, divertido para otros, y completamente tonto para la mayoria es diseñar, inventar y estudiar algoritmos de ordenamiento. En mi caso, es algo que me interesa. No porque sea apasionante pasar tardes y tardes leyendo sobre esto, sino porque a la hora de probarlo es divertido ver como se ordena, y el hecho de buscar formas de superar el orden del tiempo de ejecución en cada algoritmo obtenido es un desafio bastante intersante.

A continuación presento una de las formas mas básicas, triviales e intuitivas de ordenamiento de una estructura. Es aplicable tambien a listas enlazadas, con ciertas modificaciones.

El algoritmo en cuestión se denomina Insertion-Sort, denominado así por la forma en que se toma cada elemento y se lo inserta en su nueva posición definitiva. Se ejecuta no-recursivamente sobre la estructura misma, y tiene un tiempo de ejecución del orden de N^2, siendo N el número de elementos en la estructura (ya hablaremos de esto al final).

Veamos:

procedimiento InsertionSort(Arreglo[] estructura){

N<- estructura.size() //retorna el número de elementos de la estructura

desde i=0 hasta N-1{

int index=i;

desde j=i hasta 0 {

if (estructura[index]<estructura[j]){

intercambiar(index,j,estructura)

index=j;

}

else break;//salimos porque encontramos la ubicacion final del elemento

}

}//fin procedimiento

Lo que hace, si no se entiende, es tomar cada uno de los elementos y compararlo con sus predecesores en la estructura. Si el elemento actual es menor, se intercambian. Así, una vez ubicado, no es necesario tocarlo nuevamente. Si se piensa a los elementos como burbujas, es como si los mas pesados fueran siendo desplazados hacia arriba por los mas livianos en cada iteración. El método intercambiar simplemente hace eso, intercambia los elementos ubicados en los indices pasados por parametro en la estructura señalada.

El método, implementado en Java luce así:

public static void insertionSort(int[]a){

int n=a.length;

for (int i=1;i<n;i++){

char cursor=a[i];

int j=i-1;

while((j>=0)&&(a[j]>cursor))

a[j+1]=a[j–];

a[j+1]=cursor;

}

}

A simple vista parece un algoritmo ideal: sencillo de pensar e implementar. Pero si nos ponemos a pensar, imaginemos que tenemos que ordenar algo asi como 5000 entradas (alumnos de una universidad), o peor aún, 36.000.000(votantes en un país). El algoritmo evalua cada elemento un0 a uno contra todos los otros (en realidad, contra sus predecesores). En el peor de los casos, el arreglo estará en orden decreciente y, como queremos ordenarlo de menor a mayor, cada elemento deberá moverse hacia su izquierda j-1 (j=posición del elemento en el arreglo) lugares (cabe aclarar, que el mejor escenario es un arreglo ya ordenado, donde se realizan solo N comparaciones). Esto da lugar a la siguiente ecuación:

T(N)=  N. (1 + 2 + 3 + 4 + … + (N-1))

Luego, T(N) es del orden de N^2. Algo que, si bien no es el peor de los escenarios, podría ser mucho mejor.

Para la proxima analizaremos otros métodos mas lindos e interesantes, y prometo hablar algo acerca del orden de ejecución de algoritmos, para los que no entiendan a que se refiere que insertionSort sea O(N^2).

Anuncios

observaciones y el pensamiento no-lineal

4 agosto 2009

Una vez leí un libro de textos de Estructuras de Datos, en Inglés, escrito por Goodrich y Tamassia, que como introducción al capítulo de árboles decía:

Productivity experts say that breakthroughs come by thinking “nonlinearly”

Lo que en español se traduce (horrorosamente) a: Expertos afirman que los grandes avances/progresos se logran pensando no-linealmente.

Es una frase que me quedó por siempre grabada. En realidad, creo que siempre fuí de ese tipo de personas, y en ese momento me di cuenta (tanto es así que mi heladera lleva esa marca). El pensamiento no-lineal (nonlinearly) es aquel que te lleva a obtener soluciones distintas a las que cualquier persona consideraría normal, y en algunos casos, correcta, o a actuar de manera impredecible en ciertas ocasiones.

En realidad se me ocurren millones de ejemplos: la persona que sale a correr siempre a la misma hora los mismos días, es una persona de pensamiento lineal. Una persona que cocina hamburguesas y siempre le pone media cucharadita de sal porque así fue como lo leyó, es una persona de pensamiento lineal. Así lo es también el profesor de matemáticas que da clases aferrado a un libro de texto, o aquel que cultiva sus plantas en linea recta, pero que nunca probó si el agua no corre mejor de otra forma..

Aplicado a lo que nos interesa más, el pensamiento lineal tiene gran importancia en el desarrollo de los algoritmos. En realidad, el pensamiento no-lineal tiene trascendencia en el desarrollo; el lineal, en el no-desarrollo. Una persona con ideas libres y auténticas dibujaría un arbol de la siguiente forma:

up9

En cambio, una persona con pensamiento lineal, atada a lo que ha leído en algún lado o alguien le ha dicho, simplemente haría esto:

up8Si bien parece una observación inútil y tosca, creo que la mayor parte de la gente actua así sin darse cuenta. Es decir, a veces por no detenernos a generar una idea nosotros mismos, terminamos comportandonos como pequeños procesadores que a la hora de querer dibujar un árbol de enteros, lo mejor que podemos hacer es uno con los números en orden creciente.

Imaginense si en vez de un árbol queremos, no se, elegir uno entre varios candidatos a presidente, o dar solución al problema de ordenar una lista no recursivamente, o peor aún, tomar decisiones cruciales en nuestra propia vida, y simplemente podemos hacerlo linealmente..


¿Páginas web mentirosas?

4 agosto 2009

Hoy navegando un toque por internet me encontré con dos ejemplos de cosas bastante pelo***** y sin sentido que forman parte de sitios web que parecen ser serios. Bueno, uno no tanto.

La primera es algo gracioso. Se trata del sitio photography-now.net, al cual llego en busca de fotografías de calidad luego de buscar en google. Si se fijan bien, la portada del sitio es un logo con letras rojas que debajo muestra un contador de visitas: según este aparato, tienen mas de 80.000.000 de visitantes. Algo sorprendente. Me puso un poco triste porque yo solo recibo algo así como 30 por día nada mas. Sin embargo, al intentar entrar el sitio descubro que no funciona, y nos retorna al sitio donde se ve el logo nuevamente y el contador de visitas, ¡Incrementado!. Mi atenta (mas bien casual) observación me permitió darme cuenta que los desarrolladores del sitio decidieron contar las visitas en general, y no las únicas;  pero no se quedaron ahí. También incluyeron un generador aleatorio de números aparentemente entre 1 y 3 para que las visitas NO-ÚNICAS no solo se incrementen, sino que lo hagan de a 2 o incluso de a 3. Hagan la prueba ustedes mismos en este link.

up5

El segundo sitio me precoupa un tanto más. No quiero acusar a nadie pero, por qué debo descargarme un Wallpaper en formato .exe? Por mas que no fuera nada extraño, ¿no es realmente poco serio y misterioso? El sitio al que me refiero es wallpapers.com,  accesible sencillamente buscando “wallpapers” en google, entre los primeros resultados.

wallpaper.com jaja

Pueden comprobarlo ustedes mismos en el siguiente LINK (no recomiendo que corran nada de esto..). Pero como soy curioso, le mandé a Virus Total el supuesto wallpaper del gato tan bonito ese (que encima pesaba 4,1 mb ahahha), obteniendo como respuesta:

up7

Creo que visto esto no hace falta ni mostrar lo que dice google acerca de esta infección (trojan horse, lalal blabla). O si? VER


yo pregunto: es realmente necesario..

31 julio 2009

..que suceda esto en internet?

copy-paster's

Es sano que la información se propague y llegue a mas personas. Pero, ¿es realmente necesario copiar información de todos los lados en nuestros sitios web sin siquiera, en muchos casos, mencionar las fuentes ni dejar un breve comentario personal al respecto? ¿Qué sentido tiene, en términos de evolución, hacer esto cuando se puede dejar el enlace al otro sitio? En fin, basta googlear “tomar agua con el estomago vacio” y ver que 90% de los resultados tienen la misma información:

Debería ser también un llamado de atención a los bloggers: ¿qué necesidad hay de copiar tal cual aparecen noticias de periódicos online y revistas y publicarlas en nuestro blogs, orientando a visitantes a nuestro sitio, pero también a información que posiblemente ya hayan encontrado en sus respectivos centros de información? Es decir, el usuario siempre busca en un blog información comentada, explicada, desarrollada. Nunca algo científico. La razón? En casi todos los casos es imposible determinar el nivel académico del que expone. ¿Cómo sabe el usuario que yo soy Ingeniero en Lencería? Claro, lo leyo en “About..”


ser un genio (caleb carr)

30 julio 2009

A juzgar por la manera en que seguía hablando y deambulando como un rayo por nuestras diversas habitaciones, en busca de parafernalia tan exótica como unas cucharillas, cualquiera se hubiera planteado con toda la razón si prepararse su propio té no le suponía a Sherlock Holmes un reto de mas envergadura que la mayoría de sus empresas científicas e investigaciones. Pero tan intrigado estaba yo con el mensaje que tenía en la mano, que a estas alturas apenas le prestaba atención. Cuando Holmes ladró algo así como <<¡Tabaco, Watson!>>, me las arreglé para sacar la petaca del bolsillo, pero luego me hundí en un sillón cercano, más ajeno que nunca a los incesantes comentarios de mi amigo.


ajajaj redimensionar imágenes resulto ser fácil

30 julio 2009

Hoy a la tarde recibí un llamado de mi viejo a 300 km de distancia. Estaba desesperado porque había terminado un trabajo en MS WORD(una vez le instalé OpenOffice y me lo revoleó por la cabeza, cada uno con sus gustos..) en el que había incluido imágenes y, al momento de enviarlo por mail, descubrió que Outlook (si, también eso..) no funcionaba. Bah, si funcionaba, pero el archivo tenía un peso aproximado de 30.000 kb (así habla él). En fin, me llamó porque quería saber de alguna manera de redimensionar las imágenes para que pesen menos de lo que pesan apenas las sacamos de una cámara de mas de 5 megapixeles (de 500kb para arriba!).

En futuras entregas explicaré por qué una imagen puede pesar 2 mb y verse igual que una de 20 kb. Básicamente es porque la de 2mb tiene cientos de miles de millones de pixeles, lo cual le da una calidad asombrosa. Sin embargo, solo es apreciable a escalas muy grandes; por ejemplo, si nos sacamos una foto y hacemos un mural con ella.

En fin, lo cierto es que el gran Windows XP incluye un redimensionador que se activa cuando intentamos enviar nuestras imágenes por mail. Y no es el paint. Aunque tampoco se que proceso es exactamente, y cuando lo encuentre lo publicaré, es una gran forma de hacer las cosas sin necesidad de tener nada instalado en la pc. Por ejemplo, si somos de esos que nunca hacemos nada con fotos y JUSTO un día nos hace falta (como mi papa).

El método!

  • Seleccionamos todas las imágenes que queremos achicar y abriendo el menu contextual (click derecho sobre alguna foto seleccionada), elegimos Enviar a -> Destinatario de Correo.
  • Windows, que es muy inteligente, se dará cuenta que estamos por enviar muchos mb’s en un mail y nos ofrecerá gentilmente achicar el tamaño de las fotos. Aceptamos.
  • Lo siguiente es una barra de progreso y luego la pantalla de redactar mail. Donde dice adjuntos veremos todas nuestras fotos, pero ¡redimensionadas!.
  • Hice un par de pruebas y llegué a la conclusión, totalmente inútil, pero conclusión al fin: el tamaño final es de aproximadamente el 7% del original. Nada mal.
  • Para terminar, seleccionamos las fotos desde la casilla de adjuntos y las arrastramos/copiamos a una carpeta en nuestro disco.

Obviamente que existen miles de utilidades ultra sencillas para redimensionar, incluso en modo batch (de a muchas). Algunas de ellas son: VSO Image Resizer (DESCARGAR!) , Media Resizer (DESCARGA!), etc. Creo que no vale la pena explicar ahora como usar cada uno de ellos: es muy sencillo, existen los manuales en sus páginas web, y sino pueden mirar ACA.


yo pregunto: ¿por qué…

28 julio 2009

habiendo tantas formas de explicar graficamente lo que es una función continua, Anton Howard de la Universidad de Drexel, en su libro Cálculo y Geometría Analítica, hizo esto (leer donde dice “Es posible imaginar…”):

howardy

Creo que tomé mas tiempo en imaginar como rasgaría el yeso para crear una función que en comprender la definición matemática de función continua.


Servicio técnico, driver instalation y ¡Everest Portable!

28 julio 2009

Primero que nada, no sé bien por qué razón se me mezclan oraciones en Inglés y Español; supongo que será que me gusta tanto como suenan ciertas palabras. Por ejemplo, driver e instalation.

Ahora bien, anoche tuve que dar una especie de servicio técnico a un amigo al cual le habían reinstalado Windows XP en su computadora, pero le faltaban los drivers del sonido, cierta placa PCI y el chipset. Se me ocurrió que la única manera de conseguir los programas correctos era instalando el Everest y generando un reporte, que el luego me lo enviaría asi yo buscaba.

El reporte bien puede ser hecho con el Everest tradicional; sin embargo, existe algo mejor que eso y es algo que cualquier computómano como yo que de vez en cuando repara ordenadores debería llevar en el maletín de cd`s. Se trata del Everest 2008 en versión Portable, creada por alguien que dice llamarse Kastillo (quise googlear algo sobre él pero no encontré nada).

Se trata de tan solo un ejecutable libre de serial que pesa tan solo 5.887 kb y funciona excelente. Lo pueden descargar desde el siguiente enlace.

¿Cómo generar reportes con Everest?

Ahora bien, para no tener que andar guiando a mi amigo a través de las opciones y recibiendo datos de dudosa calidad (para una persona normal puede ser lo mismo Intel A-400 que Intel A-400-Pro) le indiqué que podía generar un reporte muy fácilmente de la siguiente manera:

  • En el Everest, seleccionamos lo que queremos reportar (o informar) en la columna de la izquierda, o bien seleccionamos todo eligiendo la opción que está por encima de todas que dice algo así como EVEREST -version-.
  • En el menú superior hacemos Informe -> Informe Rápido -opción seleccionada-
  • Elegimos el formato, que yo recomiendo sea .txt si estamos apurados o en una máquina antigua (estimen que un informe en txt de tamaño medio lleva casi 1 mb y tarda en procesar todo). Sin embargo, en HTML o MHTML sale muy bonito.
  • Esperamos que termine, y se lo enviamos a nuestro técnico de confianza para que nos encuentre los drivers.

Otra forma de hacerlo es utilizando el asistente: sin embargo, solo recomiendo esta opción si tenemos mas tiempo (por algo el otro es Informe Rápido, creanme) o necesitamos algo mas específico (por ejemplo, generar un informe solo de la categoría Monitor y Seguridad).

Repito el link de descarga por las dudas:

EVEREST ULTIMATE EDITION 4.20.817 (portable)


yo pregunto: ¿Es esto una joda?

26 julio 2009
Click en imagen para ver en tamaño completo:

facekaka

Esta aplicación de Facebook ofrece Fluck Points en paquetes y ofrece varios métodos de pago. La intención? Impresionar a tus amigos mostrandoles un determinado status, mucho mas avanzado que el que se podría obtener normalmente usando la aplicación. Y si existe, es porque hay gente que de verdad lo compra.


acerca de: cambios de ip, cambios de mac, usuarios múltiples en bux.to

25 julio 2009

Esta tarde estuve propagando la onda Bux.to a un compañero de la facultad. No se si lo encontró muy interesante, pero igual hicimos una cuenta a su nombre. El tema es que la página no acepta, como era de suponer, varias cuentas desde la misma pc. Sin embargo, nuestro objetivo no era hacer trampa. Simplemente estabamos en mi casa, en mi computadora, y queríamos hacer una cuenta para él. Como todo esto no esta contemplado por la gente del sitio, decidimos utilizar el ingenio y lo aprendido en tantas horas de universidad. Este es el resultado:

Primero que nada, verificamos lo que dice el faq. En español, dice mas o menos que, en el caso de una familia, todos pueden usar la misma pc sin que eso se considere “cheat”, pero que deben usar distintas direcciones de correo y de alertpay. Esto es raro, porque contreadice con el mensaje recibido al intentar registrarnos:

“There is already an account registered from that computer. You CANT have more than one account per computer” (O algo así).

Contradictorio? Bastante.

Para solucionar el tema, tomamos un Mac Changer, un IP Changer (en realidad, la consola de Windows y el programa ipconfig) y el Mozilla Firefox.

EL PROCESO

  • Probando, descubrimos inmediatamente que basta ingresar a Herramientas – > Limpiar Datos Privados – > Tildar Cookies, Sesiones Activas, Historial de Navegación y Contraseñas Guardadas -> Limpiar. Hecho esto ya podremos crear nuestra cuenta.
  • Sin embargo, estaremos enviando al servidor los mismos datos de IP y de MAC que nuestra cuenta verdadera. No vaya a ser que cuando estemos por cobrar 100 dolares nos digan que recibimos 15 de un referido con la misma MAC y que por ello… realmente no queremos eso. Siguiente paso.
  • Para cambiar la Mac, lo más efectivo es utilizar Macshift (que no es mas que un script en batch o en algún lenguaje de scripting similar que hace automatico lo que deberiamos hacer llendo a conexiones de red, etc etc). Desde aquí se puede descargar el programa y este es el sitio del autor, donde explica ademas como utilizarlo. Brevemente se los muestro en español: iniciamos una consola (Inicio -> Ejecutar -> “cmd.exe”), buscamos la carpeta donde desempaquetamos el Macshift y escribimos lo siguiente: “macshift -r -i ejemplo“.

machisft (nombre del programa que estamos ejecutado =o )

-r indica que se genera una Mac aleatoria.

-i ejemplo indica el nombre del dispositivo cuya mac queremos modificar. (en ejemplo ponen el nombre de su dispositivo, que se consulta en Inicio ->Panel de Control -> Conexiones de Red.)

  • Cambiada la Mac, esperamos que el modem se reinicie. En mi caso, tuve que desconectarlo y volverlo a conectar (me refiero al cable de energía) para que arranque de vuelta. Para cambiar la ip, debemos crear un fichero de texto, copiar lo siguiente en su interior:

@echo off
ipconfig /release
cls
color 4a
echo Desconecta el modem.
pause
cls
ipconfig /renew
cls
color a4
echo Conectalo de nuevo.
pause
ipconfig
cls
color 4a
echo ­Ya ten‚s una nueva IP!
echo Si lo publicas, menciona la fuente.
echo Saludos de ilpapa…
pause

y renombrarlo como fichero.BAT. Lo ejecutamos dandole o enter o corriendolo desde la consola de comandos (no quiero explicar como, es igual que el macshift que explique recién pero sin argumentos porque no tiene!). El programa nos guiará durante el proceso en lo que debemos hacer.

Comentarios finales: puede consultar su Mac ejecutando desde la consola de comandos “ipconfig /all”. Puede consultar su ip con el comando anterior, o simplemente con “ipconfig” así no se marea con tanta información.

  • Hecho todo lo anterior, tenemos nueva ip, nueva Mac y nada de cookies. Ya estamos listos para registrar una nueva cuenta en Bux.to de forma segura. Eso sí, no recomiendo a nadie que haga trampa: los creadores y la gente grosa de verdad esta mas allá de un macshift o un fichero bat para cambiar ip y serán descubiertos si ellos lo desean. Así que, nada de trampas: sea honesto y será feliz.
  • cmd is useful!