PDF de programación - Bits de ciencia 06

R e v i s t a

BITS

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Nº 6 / Segundo Semestre 2011

de Ciencia

UNIVERSIDAD DE CHILE

Alejandro Barros:
Open Data: nuevo
paradigma en el
manejo de datos

• En camino hacia la Web Semántica:


Experiencias de la Biblioteca del
Congreso Nacional de Chile


• Ricardo Baeza Yates:
32 años de computación:

de estudiante a Fellow

BITS

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Revista

de Ciencia
UNIVERSIDAD DE CHILE

Comité Editorial:
Nelson Baloian, profesor.
Claudio Gutiérrez, profesor.
Alejandro Hevia, profesor.
Gonzalo Navarro, profesor.
Sergio Ochoa, profesor.

Editor General
Pablo Barceló

Editora Periodística
Ana Gabriela Martínez A.

Periodista
Karin Riquelme D.

Diseño y Diagramación
Sociedad Publisiga Ltda.

Imagen Portada:
La nube de Linked Data

Fotografías:
DCC
Gastón Carreño
Daniel Hernández
Biblioteca del Congreso Nacional
La Nación
René Cabezas

Dirección
Departamento de Ciencias de la Computación
Avda. Blanco Encalada 2120, 3º piso
Santiago, Chile.
837-0459 Santiago
www.dcc.uchile.cl
Teléfono: 56-2-9780652
Fax: 56-2-6895531
[email protected]

Revista Bits de Ciencia del Departamento de
Ciencias de la Computación de la Facultad de
Ciencias Físicas y Matemáticas de la Universidad de
Chile se encuentra bajo Licencia Creative Commons
Atribución-NoComercial-CompartirIgual 3.0 Chile.
Basada en una obra en www.dcc.uchile.cl


Revista Bits de Ciencia N°6
ISSN 0718-8005 (versión impresa)

www.dcc.uchile.cl/revista
ISSN 0717-8013 (versión en línea)

contenidos

investigación destacada

Expresiones regulares (autómatas) con variables y sus aplicaciones
Pablo Barceló

computación y sociedad

El DCC 1983 – 1988: refundando el Departamento
Jorge Olivos

32 años de computación: de estudiante a Fellow
Ricardo Baeza Yates

El primer computador digital en Chile: Aduana de Valparaíso,
diciembre de 1961
Juan Álvarez

OPEN DATA

Open Data: nuevo paradigma en el manejo de datos
Alejandro Barros

Open Government Data en el mundo
Álvaro Graves

En camino hacia la Web Semántica: experiencias de la Biblioteca
del Congreso Nacional de Chile
Biblioteca del Congreso Nacional de Chile (BCN)

Open Source Software: similitudes y diferencias con Open Data
Jens Hardings

OpenStreetMap: el mapa libre del mundo
Julio Costa

Análisis de Datos Astronómicos
Karim Pichara, Rodolfo Angeloni, Susana Eyheramendy

Entendiendo la privacidad hoy
Alejandro Hevia

SURVEYS

La Web de los Datos
Claudio Gutiérrez, Daniel Hernández

CONVERSACIONES

Entrevista a Héctor García Molina
Claudio Gutiérrez

CONFERENCIAS

Latin American Theoretical INformatics (LATIN 2012)

02

08
14
19

25
28
33
42
46
52
58

66

76

80

EDitorial

La Computación está más viva que nunca. Todo el
espectro de nuestros campos - incluyendo la teoría,
la simulación, la implementación, etc.- debería estar
más atento y ser más propositivo que nunca antes en
la historia. Esto porque la sociedad del futuro (que ya
es la sociedad del presente en un puñado de países),
la tan manoseada pero no por eso menos importante
sociedad del conocimiento, solo podrá ser construida
a través de la aplicación masiva de las tecnologías de
la información.
Uno de los mayores desafíos que esta sociedad moderna
impone en nuestra área es la inmensa proliferación
de datos de todo tipo. Cada vez producimos más
información, y cada vez tenemos mayor capacidad
computacional para almacenarla. Por ejemplo, las bases
de datos astronómicas generan diariamente terabytes
de información describiendo el estado del cielo, las
bases de datos genómicas describen secuencias de
ADN de muchísimos organismos, nuestro paso por
las redes sociales genera cada vez más datos sobre
nuestros gustos, relaciones y posición geográfica, entre
muchos otros. Lo importante de todo esto, es notar
que el real valor de la sociedad del conocimiento está
en esos datos. O puesto de otra forma, los datos serán
en la sociedad del conocimiento lo que alguna vez
fue el oro o el dinero.
Este paso hacia una sociedad basada en la información
ha hecho cambiar muchos de nuestros paradigmas.
Por ejemplo, Tim Berners-Lee –el creador de nuestro
fetiche moderno más relevante, la Web– declaró hace
poco que ésta debía pasar lo antes posible de su actual
estado centrado en documentos (es decir, donde los
documentos o páginas son lo más importante) a un
estado centrado en datos (es decir, donde los datos
sean ciudadanos de primera clase). El modelo de esta
Web del futuro puede verse como el de una inmensa
red de bases de datos distribuidas, que colaboran
activamente intercambiando su información. Este es
el famoso concepto de Linked Data.
Pero si los datos son el capital del futuro, entonces,
¿quiénes deberían ser los dueños de esos datos? Esta
es sin duda una decisión política. Pero lo que es claro
es que si queremos que la sociedad del conocimiento
sea, a la vez, la sociedad de la inclusión, entonces una
respuesta justa a esta pregunta sería: “Todos”. Todos
deberíamos ser dueños de la mayor cantidad de datos

posibles (con las debidas reservas de privacidad). Lo
más interesante de esto es que la información se presta
perfectamente para esta idea: al contrario del capital
que es limitado, los datos claramente abundan; los
datos no se gastan, y además pueden ser replicados
y compartidos.
Pero todo esto que suena tan bonito es bastante más
complejo en la práctica. Por ejemplo, por el momento
muchas de las compañías más exitosas se están haciendo
gratuitamente con nuestros datos (supongo que no
necesito nombrarlas). Además, en general los datos
son como el material en estado crudo, no refinado.
Saber sacar la información relevante que hay en ellos
es una habilidad que debe ser enseñada y entrenada.
Es como si a uno le regalaran un cerro que está lleno
de oro. Para hacerse rico hay que saber sacarlo.
Pero no nos adelantemos. El tema de la Revista es
Open Data, es decir, la idea de hacer públicos la mayor
cantidad de datos posibles a la mayor cantidad de
gente posible. Esto acarrea problemas que van desde
los legales, hasta los más técnicos que tienen que ver
con el formato de publicación de esos datos. Lo que
hemos tratado de hacer en este número de la Revista
es acercarnos a esos problemas a través de la visión de
varios expertos: Alejandro Barros, sobre el paradigma
de Open Data; Álvaro Graves, sobre la aplicación
de este paradigma en los gobiernos; la Biblioteca del
Congreso Nacional, acerca de cómo esta entidad está
dejando disponibles sus datos; Jens Harding, sobre el
concepto de open software; Julio Costa, sobre un sistema
abierto de mapas; Karim Pichara, Rodolfo Angeloni y
Susana Eyheramendy, acerca de Datos Astronómicos;
y Alejandro Hevia, sobre temas de privacidad.
Por otro lado, también seguimos con nuestras secciones
habituales: Investigación Destacada, Computación
y Sociedad (con artículos de Jorge Olivos, Ricardo
Baeza Yates y Juan Álvarez), Surveys (donde Claudio
Gutiérrez y Daniel Hernández nos cuentan sobre la
Web de Datos), y Conversaciones (con el destacado
profesor Héctor García-Molina, de la Universidad de
Stanford).

¡Esperamos les guste!

Pablo Barceló
Editor Revista Bits de Ciencia

investigación destacada

Expresiones regulares (autómatas)
con variables y sus aplicaciones

En este artículo estudiamos expresiones
regulares que utilizan tanto símbolos de
un alfabeto finito como variables. Tales
variables se interpretan como símbolos
en el alfabeto. Además, consideramos
dos tipos de lenguajes definidos por estas
expresiones: bajo la semántica existencial,
una palabra pertenece al lenguaje de la
expresión con variables E si pertenece al
lenguaje definido por alguna expresión que
se puede obtener desde E al reemplazar
variables por símbolos; bajo la semántica
universal, una palabra pertenece al lenguaje
de la expresión con variables E si pertenece
al lenguaje definido por toda expresión que
se puede obtener desde E al reemplazar

variables por símbolos. Tales lenguajes
son regulares, y además demostramos que
aparecen naturalmente en varias aplicaciones
como consultar bases de datos de grafos
con información incompleta y el análisis
de programas. Para proveer un análisis
computacional más sólido, mencionamos
también ciertos resultados teóricos que
ayudan a entender el comportamiento de
las expresiones regulares con variables,
así como la complejidad de algunos de
los problemas de decisión más básicos
asociados con ellas.

Organización: en la siguiente sección
introducimos las definiciones básicas de
lenguajes regulares y autómatas que son

Pablo Barceló
Profesor Asistente DCC, Universidad
de Chile. Ph.D. in Computer Science,
University of Toronto (2006); Magíster
en Ciencias de la Computación,
Pontificia Universidad Católica de Chile
(2002); Ingeniero en Electricidad,
Pontificia Universidad Católica de
Chile. Áreas de interés: Bases de
Datos, Lógica para la Ciencia de la
Computación, autómata.
[email protected]

2

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Revista / Bits de Ciencia

necesarias para entender la investigación
realizada. Luego, motivamos la introducción
de las expresiones regulares con variables
con dos aplicaciones diferentes: análisis
de programas y bases de datos de grafos
con información incompleta. A partir de
éstas definimos las dos semánticas para
las expresiones regulares con variables:
Existencial y Universal. En la siguiente sección
listamos y explicamos las propiedades
computacionales más importantes de estas
expresiones, y finalmente discutimos las
conclusiones de nuestro trabajo, así como
los problemas relacionados que deseamos
estudiar a futuro.

ExPRESIONES REGULARES
Y AUTóMATAS

Las expresiones regulares son un método
gramatical ampliamente utilizado en
computación para especificar conjuntos
(posiblemente infinitos) de palabras sobre
un alfabeto finito. Su objetivo