PDF de programación - Bits de ciencia 03

R e v i s t a

BITS

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

de Ciencia

UNIVERSIDAD DE CHILE

Nº 3 / Segundo Semestre 2009

Educación en
Informática

• Orígenes de la Disciplina de la
Computación en Chile 1961-1975

• Nuevo Plan de Estudios de Computación

BITS

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Revista

de Ciencia
UNIVERSIDAD DE CHILE

Comité Editorial
Claudio Gutiérrez, profesor.

Alejandro Hevia, profesor.

Nancy Hitschfeld, profesora.

Gonzalo Navarro, profesor.

Sergio Ochoa, profesor.

Editor General
Pablo Barceló

Editora Periodística
Claudia Páez

Periodista
Ana G. Martínez

Diseño y Diagramación
Sociedad Publisiga Ltda.

Imagen Portada
Fotografías del curso
IE 2001, Taller de Proyecto

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 es una
publicación del Departamento
de Ciencias de la Computación
de la Facultad de Ciencias Físicas
y Matemáticas de la Universidad
de Chile. La reproducción total
o parcial de sus contenidos debe
citar el nombre de la Revista y su
Institución.

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

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

contenidos
02

investigación destacada
Estructuras de Datos Compactas
Gonzalo Navarro

computación y sociedad
Evaluación e Investigación en Computación
Claudio Gutiérrez

Orígenes de la Disciplina de la Computación en
Chile 1961-1975 (Resumen Extendido)
Juan Alvarez / Claudio Gutiérrez
Buscador de la Transparencia
Senén González /Mauricio Marín / Víctor Sepúlveda

EDUCACIÓN EN INFORMÁTICA
Computing Curricula en América Latina
Ernesto Cuadros-Vargas

Universidad de Chile: Nuevo Currículo de Ingeniería
Patricio Poblete

En FCFM de la U. de Chile: Nuevo Plan de Estudios
de Computación
Nancy Hitschfeld / José Miguel Piquer / Juan Alvarez Rubio

Programación Robots Lego:Aprender Jugando en el DCC
Jérémy Barbay / Johan Fabry / José Miguel Piquer

Enseñar y Aprender HCI: Amalgama Perfecta entre
Teoría y Praxis
Jaime Sánchez Ilabaca / Mauricio Sáenz Correa

CONVERSASIONES
Entrevista Internacional: Claudia Bauzer Medeiros
Alejandro Hevia

SURVEYS
Modelos de Base de Datos de Grafo
Renzo Angles

GRUPOS DE INVESTIGACION
PRISMA: Similarity Search, and Indexing in Multimedia
Archives
Benjamín Bustos

Universidad de Concepción Nuevo Programa de
Doctorado en Ciencias de la Computación

CONFERENCIAS
Lo Mejor de lo Nuestro
Marcelo Arenas

09
13
18
23
28
31
35
39

44

47

53
56

59

EDitorial

La educación en Ciencia de la Computación
e Informática ha sido históricamente la mayor
preocupación del Departamento (DCC). De hecho,
uno de nuestros principales nortes -como está explícito
en la Misión- es entregar educación superior integral
y de excelencia en esta área.

Sin embargo, como es evidente, la disciplina ha
cambiado dramáticamente en los últimos 15 ó 20
años. El advenimiento de la Internet y de una multitud
de nuevas tecnologías y aplicaciones que hacen que
el mundo se vuelva cada vez más conectado, y la
gente más familiarizada con los computadores y la
computación, ha obligado a replantear el concepto
de Informática desde sus fundamentos. La Ciencia
de la Computación hoy en día, y mucho más que
antes, es un ente fantásticamente dinámico que se
nutre para su estudio de un sinnúmero de problemas
del mundo real; aquellos que aparecen día tras día
en la práctica de la Computación. Todo esto implica
que el experto en Informática debe ser, con especial
énfasis, un profesional capaz de adecuarse a los
cambios, de proponer soluciones y desafíos. Pero
para lograr formar a este nuevo tipo de profesional es
indispensable adecuar la educación de esta disciplina
a los actuales requerimientos.

El tema central del presente número de la revista
Bits de Ciencia intenta dar una breve -aunque
significativa - visión sobre las nuevas maneras de
enseñar Informática. Para ello hemos invitado a varios
expertos nacionales, más dos invitados internacionales,
a contarnos sus experiencias. Es el caso de Ernesto
Cuadros-Vargas, de la Sociedad Peruana de la

Computación, quien nos habla del trabajo realizado
con su grupo para desarrollar un modelo curricular,
en que el contenido de un currículo particular puede
ser analizado y comparado con otro. Y de Cláudia
Bauzer Medeiros, profesora de la Universidad de
Campinas y ex presidenta de la Sociedad Brasileña
de Computación (2003-2007), quien responde en una
entrevista acerca de la enseñanza de esta disciplina.
También Patricio Poblete, de la Escuela de Ingeniería
y Ciencias de la Universidad de Chile, nos describe
el nuevo currículo de Ingeniería adoptado en el
último tiempo por la Facultad de Ciencias Físicas y
Matemáticas y que es, a grandes rasgos, el marco para
el nuevo currículo en Computación. Sobre éste último
-que ha sido recientemente adoptado por nuestro
Departamento- trata el artículo de Juan Alvarez, Nancy
Hitschfeld y José M. Piquer, todos ellos profesores
del DCC. Finalmente, tenemos dos artículos en que
profesores y colaboradores del DCC nos cuentan
acerca de las nuevas tecnologías y metodologías de
enseñanza en los cursos de la carrera de Ingeniería
Civil en Computación.

Junto con el tema central encontrarán, al igual que
en el número anterior, diversas secciones de amplio
interés: Investigación Destacada, Computación
y Sociedad, Surveys, Grupos de Investigación y
Conferencias. Todas ellas esperamos que sean del
gusto de ustedes.

Profesor Pablo Barceló
Editor Revista Bits de Ciencia

investigación destacada

Estructuras de Datos
Compactas

Las diferencias de velocidad en la jerarquía de memoria son cada vez más
pronunciadas. Esto ha propiciado una tendencia al estudio de las estructuras
de datos que puedan operar usando poco espacio, ya que aunque realicen más
operaciones, las pueden ejecutar en una memoria muchas veces más rápida. En
una época en que la cantidad de datos a manipular es gigantesca, y las memorias
donde pueden ser almacenados son las más lentas de la jerarquía, las estructuras
de datos compactas están ofreciendo soluciones muy atractivas en áreas como
recuperación de información, Web, bioinformática, bases de datos multimediales,
y muchas otras. En este artículo paso revista a algunos de los resultados más
espectaculares que ha obtenido esta fascinante área de investigación, e incluyo
algunas contribuciones propias relevantes.

INTRODUCCIóN

Gonzalo Navarro
Profesor Titular, DCC, Universidad de
Chile. Doctor en Ciencias mención
Computación de la misma Universidad
(1998). Sus áreas de interés incluyen
algoritmos y estructuras de datos,
búsqueda en texto, compresión y
búsqueda en espacios métricos.
[email protected]

En 1965, el co-fundador de Intel, Gordon Moore, estimaba que “el número de transistores que
consigue el menor costo por transistor en un circuito integrado se duplica cada 24 meses”.
La llamada “Ley de Moore” se ha mantenido válida durante décadas y se aplica a varios
aspectos de la tecnología de los computadores: las capacidades de la memoria principal
(RAM), el poder de las CPUs, las capacidades de almacenamiento de los discos, etc. Este
fabuloso incremento en las capacidades del hardware es en gran parte el responsable de la
revolución tecnológica de los últimos 50 años, permitiendo afrontar desafíos de una magnitud
impensable hace unos pocos años.

2

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Sin embargo, existen otros aspectos del
hardware que no siguen esta ley. Los más
notorios son posiblemente la velocidad de
acceso al disco y a la RAM. La respuesta a
este estancamiento en las velocidades de
las memorias ha sido el enriquecer esta
jerarquía con nuevas componentes más
rápidas, aunque también más caras y (por
lo mismo) menores. Las cachés L1, de unos
pocos KBs y prácticamente pegadas al chip
de la CPU, y luego las L2, de unos pocos
MBs, ofrecen “buffers” intermedios, en
tamaño y velocidad, entre los registros de
la CPU y la RAM de unos pocos GBs. Estos
buffers pueden ser desde sólo 2 hasta 50
veces más rápidos que la RAM, y a su vez
la RAM es unas cien mil veces más rápida
que el disco. Recientemente, las memorias
Flash han agregado un nivel entre estas dos,
resultando unas 100 veces más rápidas (y
menores en capacidad) que los discos.
Diversas razones económicas (velocidad vs
costo por bit) y físicas (límites fundamentales,
distancia a la CPU) hacen pensar que esta
jerarquía de memoria se mantendrá por
mucho tiempo.

Por otro lado, tenemos las aplicaciones cada
vez más ambiciosas en términos de cantidad
de datos a generar y manipular. La Web
sigue creciendo a un ritmo exorbitante, con
cientos de terabytes sólo en la parte estática,
y duplicándose aproximadamente cada
ocho meses. La minería de su utilización
(qué sitios visitan los usuarios, qué consultas
hacen) genera un flujo gigantesco de datos
diariamente. La bio-informática está cerca
de lograr secuenciar cada individuo a un
costo razonable, lo cual abre las puertas
a tener que mantener los tres mil millones
de bases del genoma humano para cada
persona. Las aplicaciones astronómicas
amenazan con inundarnos de terabytes
de datos por día provenientes de los
telescopios. La TV y multimedios digitales
generan exabytes (millones de terabytes)
de material al año. Las tecnologías actuales
pueden permitir almacenar esta cantidad de
datos, pero eso es lo de menos. Lo que se
necesita es manipular esos datos: analizarlos,
transformarlos, extraer información útil de
ellos. Y esta tarea es extremadamente penosa
si requiere acceder a los datos de forma
intensiva y debe llevarse a cabo sobre los
datos almacenados en disco.

Tomaré un ejemplo bastante modesto como
motivación concreta. Supongamos que
quer