Búscalo aquí:

Revista CompuScientia 2011

La revista CompuScientia es una nueva propuesta de la Sociedad de Estudiantes de Ciencia de la Computación (SECC) que nace con el objetivo de consolidar diferentes ideas y experiencias que tienen los jóvenes estudiantes de pregrado y posgrado, profesionales y entusiastas de la Computación y áreas afines. Esta revista ha sido recientemente publicada el día 15 de Diciembre con una amplia acogida por parte de la comunidad que aún continua difundiendo de diversas maneras esta revista por los diferentes medios, desde su versión descargable disponible en el sistema BECC asi como su versión de lectura disponible en ISSUU.

Cuatro grados de separación en las redes sociales

La teoría de los seis grados de separación intenta probar que cualquiera en la Tierra puede estar conectado a cualquier otra persona del planeta a través de una cadena de conocidos que no tiene más de cinco intermediarios, así, ambas personas están conectadas con sólo seis enlaces. Luego de analizar los datos de las conexiones sociales de 721 millones de usuarios de Facebook (que representan poco más del 10% de la población mundial), que a su vez conforman una red de personas interconectadas por 69 mil millones de relaciones de amistad, la red social en conjunto con la Universidad de Milan, y ayudados por una supercomputadora compuesta de 2250 equipos, han podido constatar que la separación entre las personas es de 4,74 grados. Toda una revelación.

Ray Kurzweil: antes del 2030 los humanos se podrán enamorar de robots

Ray Kurzweil, científico en Computación, inventor y uno de los futuristas más importantes del mundo, ha recibidio 3 condecoraciones presidenciales por su trabajo, acumula 19 doctorados honoríficos, es autor de 6 libros de los cuales 5 son best-sellers, además de tener a su nombre 15 patentes y poseer $30 millones en patrimonio, quiere la inmortalidad: "...no hay nada que diga que debemos envejecer y morir". Ahora lanza una de sus más importantes previsiones, la vida humana se podrá extender de manera casi ilimitada a partir del 2036.

Dennis Ritchie: el lenguaje C

Sé que ya no es noticia, Dennis Ritchie falleció exactamente hacia 1 semana, el domingo 9 de Octubre, pero no quería dejar de escribir en este blog hacerca de él, un grande para el mundo de la Computación. La primera vez que tuve un libro de programación en mis manos y vi el nombre de él (asi como el de Bjarne Stroustrup, padre del C++), sentí una gran admiración, por el simple hecho de haber tenido la genialidad y paciencia para construir un lenguaje de programación tan potente. Ahora Dennis, también se nos adelantó.

Steve Jobs, presente y futuro de Apple

Steve Jobs, simplemente un grande, hablar sobre su persona y trabajo, es hablar simplemente de un visionario y mentor, de un ejemplo de fortaleza, muchos ya conocíamos del terrible cáncer que lo debilitó pero no lo derrotó, una larga lucha, lucha que terminó hoy 5 de octubre, que se nos adelantó y causo, como solo los grandes hacen, un gran silencio para quienes conocemos de su labor. Steve se nos adelanto, nos dejó un legado y nos mostró cómo y con qué superar las adversidades, grande Steve!!

El tiempo que se pasa en Redes sociales


No es un secreto que, desde la aparición de Facebook, las cifras de cantidad de tiempo de navegación en la Internet ha cambiado a favor de esta red social, dejando atrás por gran diferencia a otras redes sociales, incluso a otras tareas, específicamente las relacionadas a las búsquedas. Este "dominio" de las redes sociales en el tiempo de los cibernautas que influencia tiene? son positivas?

Jooble, un metabuscador de empleo

La búsqueda de trabajo siempre es una constante, cualquier iniciativa que ayude a encontrar trabajo es bien recibida, por ese motivo fue creado Jooble – un metabuscador especializado en empleo y trabajo que realiza búsquedas en páginas de más de 40 países. Jooble es muy recomendable especialmente para la búsqueda de empleo porque utiliza en sus resultados de búsqueda ¡hasta 60 sitios web diferentes de ofertas de empleo!


Aplicaciones del Ranking Lexicográfico

La idea de ranking esta presente en nuestras vidas de muchas maneras, por ejemplo, el ranking de equipos de futbol del torneo nacional, el ranking de estudiantes al final de un ciclo de estudios en la Universidad. Al escuchar la palabra "ranking" simplemente se nos viene a la mente la ordenación de elementos teniendo en cuenta algún criterio. En este post se hace una breve introducción al aprendizaje por ranking, se muestran algunas aplicaciones y algoritmos.


Sincronización, Caos y Movimiento Colectivo



La sincronización fue descubierta (o estudiada?) por Christiaan Huygens en 1665, quién como resultado de su investigación inventó el reloj de péndulo. La sincronización es un fenómeno natural que presenta la obtención de una relación fija entre instantes de tiempo correspondientes de dos o más señales. Así, la sincronización actúa en la naturaleza a través del movimiento colectivo y ordenado que permite la realización de varios de sus fenómenos naturales.


Métodos de Krylov para la solución de Sistemas Lineales



El tema del Algebra Lineal siempre tiene algo de trabajoso, en este post quiero compartir un poco de información sobre los métodos de Krylov, una alternativa de solución para sistemas lineales. En el Algebra Lineal, se tiene dos tipos de problemas principales: Ax = b y Ax = λx o Ax = λBx, además de un nuevo problema de funciones de matrices y = f(A)x. Esos problemas ya son atendidos por métodos directos o métodos iterativos del Algebra Lineal, sin embargo, para cuando se procesan volúmenes grandes de datos, soluciones directas o iterativas pueden tornarse no viables, siendo los métodos de Krylov una alternativa.

La Seguridad en Sistemas Críticos Embebidos



Un sistema embebido es un sistema encapsulado en un dispositivo o en un sistema más general que lo controla. La diferencia con un sistema convencional de un computador, es que el sistema embebido se limita a ejecutar una única tarea, de manera continua, y la mayoría de veces, sin complicaciones. En específico, un sistema crítico embebido tiene una tarea de alta importancia cuyo mal funcionamiento tendría pérdidas muy graves, por ejemplo, un sistema crítico embebido que detecta la correcta altura a la que se encuentra una aeronave. La seguridad en estos sistemas, como en cualquiera, tiene vital importancia. Otros sistemas embebidos están destinados a brindar confort y un mejor desarrollo de las actividades humanas, como el uso de un sistema embebido en zapatillas deportivas, las cuales se amoldan al pie del atleta de acuerdo al terreno por donde se encuentre.


Poscomp: Incripciones 2011



Ya están abiertas las inscripciones para el examen Brasilero de ingreso la Pos-graduación en Computación (PosComp) que una vez más se realizará en Perú en las ciudades de Arequipa y Trujillo. En Trujillo, el apoyo del SECC hace posible nuevamente la realización de este examen que abre las puertas para que estudiantes peruanos puedan realizar sus estudios de maestria en cualquier Universidad de Brasil. La noticia para este 2011 es que el examen por primera vez será realizado también en Colombia, una indudable buena noticia.

Revista para estudiantes de carreras de Computación: Compuscientia



Este post es para hacer publico el lanzamiento de una revista dirigida a estudiantes de pre y pos grado, la revista CompuScientia ha sido creada y se está haciendo el llamado de contribuciones de los autores. Una oportunidad de publicación de artículos para alumnos, egresados, profesionales y toda persona que tenga algo que compartir, en una revista indexada, de libre acceso y de contenido no necesariamente técnico/científico sino más informativo.


Ranking Mundial de Universidades 2011



Como es costumbre desde el 2004, por esta época del año es publicado el ranking de las 12 mil Universidades del mundo. Este ranking muestra la posición de diferentes Universidades de diferentes partes del mundo, presentando un ranking mundial y uno por zona geográfica tomando en cuenta la información que estas ponen a disposición en sus web oficiales. Esto es interesante porque permite identificar como esta posicionada nuestra institución con respecto a sus pares en nuestra región y en el mundo. Cómo estarán posicionadas las Universidades de Perú?

Medir Impacto de una Investigación con estadísticas de Publish or Perish


Cuando realizamos una investigación de cualquier dimensión, siempre es bueno (o es obligatorio) mostrar el impacto del trabajo de investigación realizado para la comunidad científica. Una de las maneras más comunes de hacerlo es mostrando estadísticas de cómo ha ido creciendo la cantidad de investigaciones del área investigada en los últimos tiempos...sin embargo, el solo hecho de mostrar esta estadística aparentemente sencilla, puede tomarnos algo de tiempo y esfuerzo extra. Por suerte existe una herramienta que nos brinda soporte para varios tipos de estadísticas y es soportado por Google Académico.

Detector de Bordes de Kirsh en Matlab [código]



Dentro de los detectores de bordes, en la categoria de operadores direccionales, podemos ubicar el detector de bordes de Kirsh, el cual tiene por objetivo no solo mantener la magnitud de los bordes, sino también su dirección. El operador de Kirsh se caracteriza por trabajar en las direcciones de 0º, 45º, 90º y 135º teniendo una máscara de convolución para cada uno de dichos ángulos. En este post mostramos el código fuente para la detección de bordes usando el operador direccional de Kirsh aplicado a imágenes en escala de grises.


Visualización de Estructura de Datos



En Ciencias de la Computación, algo que siempre es útil son gráficos que permitan comprender mejor el funcionamiento de algún método, técnica, algoritmo, o estructura de datos. De manera visual, la explicación teórica tiene más chance de quedar prendida en la memoria del lector o estudiante y poder hacer uso de lo aprendido con mayor facilidad. Jean Bovet, de la Universidad de San Francisco, a desarrollado un completo sistema que permite la interacción y por supuesto, la visualización de Estructuras de Datos que van de simples a complejas.


Detector de Bordes Laplaciano en Matlab [código]



En Procesamiento Digital de Imágenes, uno de los detectores de bordes de imágenes en escala de grises que otorga buenos resultados es el operador Laplaciano, el cual aplica la segunda derivada a un píxel analizado. En este post presentamos el código fuente en Matalb del detector de bordes Laplaciano para imágenes en escala de grises.


Diagramas de Chernoff para la visualización de datos multivariados



Un dato multivariado es aquel que posee más de un atributo que lo define. Un conjunto de datos multivariados contiene muchos de estos elementos, los cuales, normalmente, son usados para diferentes tareas, en Inteligencia Artificial, podría ser por ejemplo, clasificación, agrupación, etc. Estos tipos de datos poseen diferentes formas de representación visual, siendo uno de ellos, los diagramas de Chernoff, que en lo personal me han llamado la atención debido a que, representan los diferentes atributos de los datos a través de características de un rostro.

Detector de Bordes de Sobel en Matlab [código]



Entre los operadores usados en Procesamiento Digital de Imágenes para la detección de bordes en imágenes en escala de grises tenemos el operador de Sobel, el cual, a parte de su tarea de detector de bordes cumple también con el suavizamiento de la imagen al aplicar de manera intrínseca el Suavizamiento Gaussiano. En este post presentamos el código en Matlab del operador de Sobel para la detección de bordes en imágenes en escala de grises.


Perú en la final mundial ACM-ICPC 2011



Este post es algo emotivo, tal vez pocos de los peruanos conozcan que es un concurso de programación, incluso tal vez pocos de los estudiantes de Computación y/o ramas afines en el Perú lo sepan, y este post no tiene por objetivo definirlo, sino hacer de conocimiento que un equipo del Perú, hoy a participado en la final del ACM-ICPC 2011, el más grande, antiguo y prestigioso concurso de programación a nivel mundial. El equipo peruano Hackermath, representante de la Pontificia Universidad Católica del Perú, se convirtió en el primer equipo peruano en llegar a una final mundial de esta competencia, y pese a la dificultad de que uno de sus miembros no pudo viajar, Walter Erquinigo y Daniel Soncco junto al coach Victor Laguna pusieron el nombre del Perú en el score final!!

II Concurso Peruano de Programación CPP 2011

El Concurso Peruano de Programación viene convirtiéndose en uno de los eventos de programación competitiva más importantes del Perú, de la mano del SECC y la SPC este 2011 se viene con fuerza, se tiene preparado 2 categorías en la que participantes de nivel básico o intermedio pueden inscribirse en la categoría A y los participantes expertos en la categoría B, además, para cada categoría, una ronda eliminatoria y una final en la ciudad de Pucallpa sede del X Congreso de la Sociedad Peruana de Computación - CSPC 2011.

El problema de String Matching Completo



El problema de string matching completo consiste em encontrar todas las ocurrencias de um determinado patrón p en um texto t. Este es uno de los problemas más estudiados en Ciencia de la Computación principalmente por tener aplicación directa en diversas áreas como procesamiento de texto, imágenes y señales, análisis y reconocimiento de habla, compresión de datos, recuperación de datos, entre otros. Desde 1970 se han propuesto más de 80 algoritmos de string matching, y de ellos, más del 50% son de la última década. En un trabajo de investigación se han implementado 85 diferentes algoritmos de string matching y se han realizado distintas pruebas sobre su desenvolvimiento.


Jerarquía del Aprendizaje Inductivo: Aprendizaje Supervisado y No Supervisado



Los algoritmos de aprendizaje de máquinas aparecen con la intención de mejorar el desempeño en la realización de alguna tarea, este desempeño es mejorado a través de la experiencia, con la cual van “aprendiendo” hasta ser capaces de inducir una función o hipótesis capaz de resolver un determinado problema. Estos algoritmos son asociados al área de Inteligencia Artificial, sin embargo, otras áreas como Estadística, Teoría de la Computación, Teoría de la Información, Neurociencia, etc., tienen importantes contribuciones. De esta manera, de acuerdo a la tarea que se desea resolver, los algoritmos de aprendizaje pueden ser divididos en predictivos y descriptivos.

AlgoRythmics Intercultural Computer Science Education: Algoritmos de Ordenación a ritmo de folk dance



Cuando se empieza a estudiar algoritmos, especialmente en el tema de análisis de los mismos, es ineludible empezar con los métodos de ordenación, los cuales van poco a poco "subiendo de complejidad" para el entendimiento de un novato y no es recién con la práctica, cuando el concepto del mismo es entendido. Hay muchas maneras didácticas de aprender estos algoritmos de ordenación, sin embargo, también hay maneras rítmicas, como la propuesta por la Sapientia University (Transylvania - Hungria) que utilizando folk dance europeo muestra el funcionamiento de los algoritmos de ordenación más utilizados, como el tradicional bubble sort (método de la burbuja) explicado al ritmo del Csángó Hungaro.


Detector de Bordes de Prewitt en Matlab [código]



En Procesamiento Digital de Imágenes, uno de los operadores usado para la detección de bordes en imágenes es el operador de Prewitt, el cual usa una vecindad de 3 x 3 para la convolución por cada píxel de la imagen analizada. Con este tipo de máscara usada se logra evitar el cálculo de la gradiente en el punto intermedio. En este post presentamos el código fuente en Matlab del operador de Prewitt para la deteción de bordes en imágenes en escala de grises.


Detector de Bordes de Roberts en Matlab [código]



En Procesamiento Digital de Imágenes, los bordes corresponden a cambios locales significativos de intensidad en la imagen analizada, representando así una discontinuidad medida por un valor alto de la gradiente. Para la detección de bordes de una imagen existen dos tipos de detectores: operadores de gradiente y operadores direccionales. En este post presentamos el código fuente en Matlab del detector de bordes de Roberts que se basa en el uso del operador gradiente que aplica la derivada respecto a los ejes x y y de un píxel.


Algoritmos: sobre el análisis y diseño



De manera amplia, los algoritmos son procedimientos para solucionar problemas, es decir, no son simples respuestas, sino que son procedimientos definidos para obtener respuestas y, básicamente, son la piedra angular de la Ciencia de la Computación. Si alguien estudia Computación o algo relacionado a ella, de seguro que en su vida verá más de un algoritmo, y más aún, tendrá que analizarlo, programarlo y si no existe, crearlo.


Sculptris: Modelos 3D realistas


Muchas veces se buscan herramientas para la construcción de modelos tridimensionales eficientes y que generen resultados realistas lo mejor posible. El modelado tridimensional se refiere, en términos generales, a la generación de formas realistas con la ayuda de herramientas computacionales, las cuales tienen como propósito realizar la mejor proyección visual. Sculptris resulta ser una herramienta prometedora.


Filtro de Realce Paso Alto para Imágenes en Matlab [código]



Así como se ha evaluado algunos métodos de filtros de suavizamiento, ahora veremos un filtro de realce que tiene por objetivo intensificar detalles finos de una imagen, acentuando las orillas (bordes). La máscara de convolución de los filtros de realce se caracterizan por tener coeficientes positivos cerca a su centro y negativos en la periferia. En este post presentamos el código fuente en Matlab del filtro de realce de Paso Alto que se encarga de eliminar los componentes de bajas frecuencias y mantener las de altas frecuencias.

Problemas de la Educación en Ciencia de la Computación en Perú


Leyendo por ahí, me cruce con unos artículos del SIGCSE (ACM Special Interest Group on Computer Science Education), en el cual se tratan problemas de educación relacionados a Ciencia de la Computación. en el boletín ACM SIGCSE del 2009, volumen 41, encontré un paper muy interesante en el que se habla de los problemas educacionales que tiene el Perú con respecto a la Ciencia de la Computación, uno de los autores de este trabajo es Juan M. Gutierrez, de la Sociedad Peruana de Computación (SPC), sin duda un documento que vale la pena revisar.


El paper se denomina: "Computer Science Education in Perú: A New Kind of Monster?", y puede encontrarse en la Librería Digital de la ACM: http://portal.acm.org/citation.cfm?id=1595481&dl=GUIDE&coll=GUIDE. Muestra los aspectos en los que las leyes peruanas ven la educación con respecto a la Ciencia de la Computación enfocándose en la preparación de los profesores. El problema de las mallas curriculares no es dejado de lado en este documento.

Saludos

Quieres leer más post como éste???...suscribete aquí!!!

Suavizamiento de Imágenes usando el Filtro de Promedio/Rango en Matlab [código]



Otro método usado en Procesamiento Digital de Imágenes para realizar el suavizamiento de imágenes es usando el filtro de Promedio/Rango, el cual se basa en promediar únicamente los píxeles en la máscara que se encuentren en cierto rango que dependerá del tono de gris del píxeles. En este post presentamos el código fuente en Matlab del suavizamiento de imágenes en escala de grises usando el filtro de Promedio/Rango.


Clasificador de símbolos LaTeX: Detexify


A quién no le ha pasado que al trabajar en el editor LaTeX a tenido alguna complicación por no conocer un símbolo matemático? seguro que a alguno de nosotros y más de una vez, personalmente me ha pasado y me ha quitado algo de tiempo buscar en la documentación LaTeX...y más aún si no sabes como se llama aquel símbolo griego, operador matemático o lo que fuere....solo tienes una pista, su forma...por fortuna, siempre existe una manera de llegar en menor tiempo, y una aplicación web llamada Detexify LaTeX permite que, a mano alzada dibujes la forma del símbolo que necesitas para que te devuelva un conjunto de símbolos LaTeX entre los que podría estar el que buscas.


Esta herramienta muy interesante y útil no viene a ser otra cosa que un reconocedor en tiempo real de trazos a mano alzada (handwriting recognition) de símbolos LaTeX.

Detexify LaTeX simbol classifier, una aplicación desarrollada por Daniel Kirsch, sin duda es una herramienta importante hoy en día, sencilla de usar y disponible de manera gratuita en: http://detexify.kirelabs.org/classify.html

Espero les sea de utilidad, saludos.


Quieres leer más post como éste???...suscribete aquí!!!


Suavizamiento de Imágenes usando el filtro Gaussiano en Matlab [Código]



Para el suavizamiento de imágenes con presencia de ruido, existen diversidad de filtros, uno de ellos es el filtro Gaussiano que usa una máscara basada en una distribución Gaussiana, siendo la más usada la de W = [1 2 1; 2 4 2; 1 2 1]*(1/16), la cual se caracteriza por asignar un mayor peso al píxel central y a los píxeles que se encuentran cercano a este, y menor peso a los píxeles alejados. En este post presentamos el código fuente en Matlab del filtro Gaussiano para el suavizamiento de imágenes en escala de grises.


Suavizamiento de Imágenes usando el Filtro del Promedio en Matlab [código]



En Procesamiento Digital de Imágenes, la operación de filtrado es usada con el objetivo de aumentar o disminuir ciertas características presentes en una imagen. Una de las técnicas más usadas para realizar el filtrado es usar la convolución de una máscara. Es así que, uno de estos tipos de filtros es llamado Filtro de Suavizamiento y tiene por objetivo hacer borrosa la imagen y reducir la presencia de ruido, es decir, eliminar componentes de altas frecuencias y mantener las de bajas frecuencias. En este post presentamos el código fuente en Matlab del filtro de Promedio para imágenes en escala de grises.


Suavizamiento de Imágenes usando el Filtro de la Mediana en Matlab [código]



Otro método utilizado para el Procesamiento Digital de Imágenes para el suavizamiento de imágenes que presentan ruido, es el filtro de la Mediana, el cual, reemplaza al píxel central de una región de convolución por la mediana de sus píxeles. Este filtro tiene el problema de que genera la pérdida de lineas finas y de bordes, por lo que, para evitar este inconveniente, se deberá usar una máscara de 4 vecinos en forma de cruz. En este post presentamos el código fuente en matlab de la aplicación del filtro de Mediana para el suavizamiento de imágenes en escala de grises.


Posgradc: Estudios de Posgrado en Computación en el extranjero


Recientemente se ha lanzado un sitio web muy interesante y sobre todo bastante informativo, de carácter indispensable en revisión para aquellas personas que tengan la intensión de realizar estudios de posgrado (sea maestría o doctorado) en el extranjero, incluso para aquellos que ya tienen ganado cualquier tipo de bolsas de estudios puesto que brinda información acerca de los trámites que hay que seguir para poder tener listos todos los documentos necesarios. Este sitio se llama Posgradc y es una propuesta de la Sociedad de Estudiantes de Ciencia de la Computación a la comunidad estudiantil de todo nivel.

Posgradc nace como una iniciativa de estudiantes de posgrado en Brasil auspiciada por la Sociedad de Estudiantes de Ciencia de la Computación, con la intención de convertirse en una fuente de apoyo para todos los interesados en realizar estudios de computación en el exterior.

Esta iniciativa tiene como objetivos:
  • Promover estudios de posgrado en computación en el exterior.
  • Promover la capacitación de profesionales en computación.
  • Apoyar el crecimiento de la comunidad de maestros y doctores en computación en el Perú.

En el site de Posgradc se podrá encontrar, en entre otras cosas, la siguiente información:
  1. Preguntas Frecuentes sobre Brasil y estudios de posgrado en Brasil
  2. Programas de maestría/doctorado en Brasil
  3. Presentación
  4. Ubicación
  5. Infraestructura y Servicios
  6. Líneas de investigación
  7. Información sobre la ciudad
  8. Información de contacto de alumnos y ex-alumnos peruanos estudiando en Brasil
  9. Tramites en Perú para obtención de la Visa de estudios.
  10. Trámites durante el ingreso y estadía en Brasil.
  11. Enlaces de Interés

Para que esta iniciativa tenga éxito y pueda alcanzar a una variedad de personas, se requiere de la colaboración de todos, tanto en DIFUSIÓN como CONTRIBUCIÓN con información relevante para el site (por el momento, solo se cuenta con información de estudios en Brasil, pero se espera disponer de información de programas en otros países). Si deseas colaborar con esta iniciativa, por favor envía un e-mail a posgradc@seccperu.org.

Visita http://posgradc.seccperu.org/. Esperamos que el site cumpla con los objetivos planteados y, especialmente, sea de utilidad a los futuros posgraduandos.



Quieres leer más post como éste???...suscribete aquí!!!

Umbral basado en Entropía para la Binarización de Imágenes en Matlab [código]



Otro de los métodos utilizados para el cálculo de un umbral óptimo aplicado a la binarización de imágenes es el método del umbral por entropía, el cual se basa en el cálculo de la incertidumbre para las diversas distribuciones que se puedan originar para los píxeles de la imagen analizada. En este post presentamos el código fuente en Matlab del cálculo del umbral por entropía para la binarización de imágenes.


Umbral basado en Probabilidades para la Binarización de Imágenes en Matlab [código]



El proceso de binarización de una imagen puede resumirse en clasificar un tono de píxel como blanco o negro, sin embargo, esta clasificación se realiza a través de un valor umbral, el cual debe ser el más adecuado posible para obtener resultados buenos en la determinación del color del píxel. Uno de los métodos de cálculo de umbral aplicado a la binarización de imágenes es el método de umbral de probabilidades del cual presentaremos su código fuente en Matlab y algunos de los resultados obtenidos.


Histograma Normalizado de una imagen en Matlab [código]



Para muchas tareas de Procesamiento Digital de Imágenes es necesario el uso del Histograma, como fue presentado en el post respectivo, sin embargo, a veces es necesario realizar la normalización del vector de histograma el cual mide el promedio del histograma con respecto a la cantidad de píxeles de la imagen analizada. En este post presentamos el código en Matlab para el cálculo del histograma normalizado.


Problema de Raices Cuadradas Módulo n [código]

El problema de calcular las raíces cuadradas módulo n (square roots module n problem), llamado también SQROOT es un problema muy usado como fundamento en diversas funciones criptográficas. Este problema tiene dos casos a solucionar, el primero cuando n es primo, en el cual el cálculo a realizar es fácil, pero si n es compuesto, el cálculo es difícil debido a que se desconoce los factores primos de n. En este post presentaremos el código fuente en java de una implementación de la solución de este problema.

En esta implementación sencilla calcularemos la raíz cuadrada módulo n de manera independiente para cuando n es primo y compuesto. Así en nuestro código fuente en Java, calcularemos la raíz cuadrada de a módulo p.

Empezamos con el caso en en que p es primo, se tendrá el resultados r o - r que representa la raíz cuadrada calculada, si el resultado es mayor que p se entenderá que se obtuvo un ERROR.

  1. private static long inv = 0; //variable global

    public static long SRPrimo(long a, long p)
  2. {
  3. long r=0;
  4. if(esCongruente(p,3,4)==true)
  5. r = SRPrimo1(a,p);
  6. else
  7. if(esCongruente(p,5,8)==true)
  8. r = SRPrimo2(a,p)
    else //resuelve cualquier caso,
  9. r = SRPrimoGeneral(a,p);//pero para un n muy
    // grande no es eficiente
  10. return r;
  11. }
La función esCongruente() la pueden encontrar aquí. Luego:

  1. public static long SRPrimoGeneral(long a, long p)
  2. {
  3. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
  4. System.out.println("Simbolo de jacobi de "+
    a+"modulo "+p+" es = "+jac);
  5. if(jac==-2)
  6. {
  7. System.out.println("Error!!"+a+
    " no pertenece a Z_"+p);
  8. return (p+1); //Error
  9. }
  10. if(jac==-1) //devolvera un numero fuera de rango,
  11. //lo que significa ERROR
  12. {
  13. System.out.println("Error!!"+a+" no tiene"+
    "raices modulo "+p);
  14. return (p+1); //a no tiene raiz cuadrada
    // modulo p
  15. }
  16. if(moduloInverso(a,p)==false)//si existe
    //modulo inverso, este se almacena en la var global inv
  17. {
  18. System.out.println("Error!"+a+" no tiene "+
    "inverso modulo "+p);
  19. return (p+1); //a no tiene raiz
    //cuadrada modulo p
  20. }
  21. long b,s,t,c,d,r=0;
  22. boolean flag=false;
  23. do{ //usamos la divison repetida por 2
  24. s = hallarExponente((int)(p-1));
  25. t = (int)((p-1)/(Math.pow(2,s)));
  26. }while(t%2==0); // t tiene que ser impar
  27. //ahora seleccionaremos enteros b.
  28. for(b=1; b<=p-1 && flag==false; b++)
  29. {
  30. jac = jacobi(b,p);
  31. if(jac==-1) //b no es residuamente
    //cuadratico modulo p
  32. {
  33. flag = true;
    //el resultado de a^-1 mod p, se almaceno
    // en la variable global llamada inv
  34. c = exponenciacionModular(b,t,p);
  35. r = exponenciacionModular(a,((t+1)/2),p);
  36. for(int i=1; i<=s-1; i++)
  37. {
  38. d = exponenciacionModular((r*r*inv),
    ((long)Math.pow(2,s-i-1)),p);
  39. System.out.println(" d = "+d);
  40. if(esCongruente(d,-1,p)==true)
  41. r = (r*c)%p;
  42. c = exponenciacionModular(c,2,p);
  43. System.out.println(" r = "+r);
  44. }
  45. }
  46. }
  47. System.out.println(" s = "+s);
    System.out.println(" t = "+t);
  48. return r;
  49. }
El símbolo de Jacobi que calcula la función jacobi() y hallarExponente() se encuentran aqui, mientras que la función moduloInverso() y exponenciacionModular() lo encuentran en este post.

  1. //CASO 1: cuando p es congruente con 3 modulo 4
  2. public static long SRPrimo1(long a, long p)
  3. {
  4. System.out.println("Estamos en el caso 1");
  5. long r=0;
  6. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
  7. System.out.println("Simbolo de jacobi de "+a+
    "modulo "+p+" es = "+jac);
  8. if(jac==1)
  9. r = exponenciacionModular(a,((p+1)/4),p);
  10. else
  11. {
  12. System.out.println("Error! "+a+
    " no pertenece a Q_"+p);
  13. return (p+1); //Errrorrrrrr
  14. }
  15. return r;
  16. }
  17. //CASO 2: cuando p es congruente con 5 modulo 8
  18. public static long SRPrimo2(long a, long p)
  19. {
  20. System.out.println("Estamos en el caso 2");
  21. long r=0,d=0;
  22. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
  23. System.out.println("Simbolo de jacobi de "+a+
    "modulo "+p+" es = "+jac);
  24. if(jac==1)
  25. {
  26. d = exponenciacionModular(a,((p-1)/4),p);
  27. if(d==1)
  28. r = exponenciacionModular(a,((p+3)/8),p);
  29. if(d==p-1)
  30. r = (2*a*((long)Math.pow(4*a,
    ((p-5)/8))))%p;
  31. }
  32. else
  33. {
  34. System.out.println("Error! "+a+
    " no pertenece a Q_"+p);
  35. return (p+1); //Error
  36. }
  37. return r;
  38. }
Finalmente, para el caso en que p es compuesto.

  1. public static long[] SRCompuesto(long a, long n)
  2. {
  3. long[] resp = new long[4];
  4. boolean band = false;
  5. long p,q;//factores no triviales de n
  6. p = pollardRho(n);
  7. q = n/p;
  8. System.out.println(" "+n+" = "+p+"x"+q);
  9. long r=0,s=0,x=0,y=0;
  10. do{
  11. r = SRPrimoEspecial(a,p);
  12. s = SRPrimoEspecial(a,q);
  13. //si todo salio OK hasta ahora, entonces seguimos
  14. long[] euc = new long[3];
  15. euc = euclidesExtendido(p,q);
  16. long c = euc[1];
  17. long d = euc[2];
  18. //resto chino
  19. x = ((r*d*q)+(s*c*p))%n;
  20. y = ((r*d*q)-(s*c*p))%n;
  21. //probamos si la respuesta es valida o no
  22. if(esCongruente(x*x,a,n) &&
    esCongruente(y*y,a,n))
  23. band = true;
  24. }while(band==false);
  25. resp[0] = x;
  26. resp[1] = -x;
  27. resp[2] = y;
  28. resp[3] = -y;
  29. return resp;
    }
  30. public static long SRPrimoEspecial(long a, long p)
  31. {
  32. if(moduloInverso(a,p)==false)//si existe modulo inverso,
    //este se almacena en la var global inv
  33. {
  34. System.out.println("Error! "+a+
    " no tiene inverso modulo "+p);
  35. return (p+1); //a no tiene raiz cuadrada modulo p
  36. }
  37. long b,s,t,c,d,r=0;
  38. boolean flag=false;
  39. do{ //usamos la divison repetida por 2
  40. s = hallarExponente((int)(p-1));
  41. t = (int)((p-1)/(Math.pow(2,s)));
  42. }while(t%2==0); // t tiene que ser impar
  43. long jac;
  44. //ahora seleccionaremos enteros b.
  45. do{
  46. b =(long)Math.floor(Math.random()*(p-1));
  47. }while(b<1 || b>p-1);
  48. jac = jacobi(b,p);
  49. if(jac==-1) //b no es residuamente
    //cuadratico modulo p
  50. {
  51. //el resultado de a^-1 mod p, se almaceno
    //en la variable global llamada: inv
  52. c = exponenciacionModular(b,t,p);
  53. r = exponenciacionModular(a,((t+1)/2),p);
  54. for(int i=1; i<=s-1; i++)
  55. {
  56. d = exponenciacionModular((r*r*inv),
    ((long)Math.pow(2,s-i-1)),p);
  57. if(esCongruente(d,-1,p)==true)
  58. r = (r*c)%p;
  59. c = exponenciacionModular(c,2,p);
  60. }
  61. }
  62. return r;
  63. }

Para esta condición hacemos uso del algoritmo de Pollard Rho para enfrentar el problema de la factorización entera, el código lo pueden encontrar aquí.

Con las funciones presentadas arriba, podemos usar en nuestra función principal una llamada para calcular la raíz cuadrada módulo n según sea el caso:

  1. public static void main(String[] args){
  2. //Prueba raices cuadradas modulo p, p primo
  3. long a =12;//12345;
  4. long p =37;//1234533;
  5. long r = SRPrimo(a,p);
  6. if(r<p && esCongruente(r*r, a,p) )//verificamos
  7. System.out.println("La raiz cuadrada de "+
  8. a+" modulo "+p+" es = "+r+" y "+-r);
  9. //Prueba raices cuadradas modulo n, n compuesto
  10. long c=11;
  11. long n=1315;
  12. long[] resp = new long[4];
  13. resp = SRCompuesto(c,n);
  14. for(int i=0; i<4; i++){
  15. if(resp[i]<n)//verificacion
  16. System.out.println(" raiz"+(i+1)+
  17. " es = "+resp[i]+" ==>: "+
  18. resp[i]+"^2 mod "+n+" = "+c);
  19. else
  20. i = 4;//ya no imprime nada
  21. }
  22. else
  23. System.out.println("ERROR");
  24. }


Quieres leer más post como éste???...suscribete aquí!!!
Related Posts Plugin for WordPress, Blogger...