PDF de programación - Bits de ciencia 09

3
1
0
2
o
ñ
a

•


9


.

o
N



REVISTABITS

DE CIENCIA
UNIVERSIDAD DE CHILE

D E P A R T A M E N T O D E C I E N C I A S D E L A C O M P U T A C I Ó N

TEoríA dE lA
CompuTACIÓN EN CHIlE

“Kurt Gödel y Alan Turing: una
nueva mirada a los límites de
lo humano”, Claudio Gutiérrez

“Discretización en ingeniería
computacional y visualización
científica”, María Cecilia Rivara

INVESTIGACIÓN
CONTENIDOS
DESTACADA

04

10

14

18

28

34

38

46

52

60

INVESTIGACIÓN
DESTACADA
Discretización en ingeniería
computacional y visualización
científi ca
/ María Cecilia Rivara

COMPUTACIÓN
Y SOCIEDAD
Historia del desarrollo de la
Computación en la Universidad
de Concepción (1960 – 1980)
/ Yussef Farrán, José Durán

U-papers: accediendo a las
publicaciones científi cas del
DCC
/ Felipe Chacón, José A. Pino

Kurt Gödel y Alan Turing: una
nueva mirada a los límites de lo
humano
/ Claudio Gutiérrez

TEORÍA DE LA
COMPUTACIÓN EN CHILE
Teoría de la Información
/ Gonzalo Navarro

Planifi cación, preferencias y
conocimiento: motivación y
problemas abiertos
/ Jorge Baier

Tipos: garantías a medida
/ Éric Tanter

Teoría de Bases de Datos
/ Jorge Pérez

Indexación y Compresión
de Datos para motores de
búsqueda
/ Diego Arroyuelo

Algoritmos, Estructuras y
Datos y mousse de chocolate
/ Jérémy Barbay

2

64

Demostraciones de Nula Di-
vulgación: o cómo convencer
a alguien que mi sudoku tiene
solución, sin revelarla
/ Alejandro Hevia

72

80

SURVEY
Problemas de satisfacción de
restricciones
/ Miguel Romero

CONVERSACIONES
Entrevista a Roberto Camhi
/ Benjamín Bustos, Claudio Gutiérrez

82

GRUPOS DE
INVESTIGACIÓN
UC Temuco: la investigación
como elemento que fortalece
la docencia. Una mirada desde
la región
/ Oriel Herrera, Marcos Lévano

Comité Editorial
▪ Nelson Baloian, profesor.
▪ Claudio Gutiérrez, profesor.
▪ Alejandro Hevia, profesor.
▪ Gonzalo Navarro, profesor.
▪ Sergio Ochoa, profesor.
Editor General
Pablo Barceló, profesor.

Editora Periodística
Ana Gabriela Martínez.

Periodista
Karin Riquelme.

Diseño y Diagramación
Anzuelo Creativo.

Imagen Portada
Anzuelo Creativo.

Fotografías
Comunicaciones DCC U. de Chile.
Comunicaciones FCFM U de Chile.
Comunicaciones DCC PUC.
Anzuelo Creativo.

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-29780652
Fax: 56-2-26895531
[email protected]

Revista BITS de Ciencia del Departamento
de Ciencias de la Computación de la Facul-
tad de Ciencias Físicas y Matemáticas de la
Universidad de Chile se encuentra bajo Li-
cencia Creative Commons Atribución-NoCo-
mercial-CompartirIgual 3.0 Chile. Basada en
una obra en www.dcc.uchile.cl

Revista Bits de Ciencia Nº 9
ISSN 0718-8005 (versión impresa)

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

INVESTIGACIÓN
EDITORIAL
DESTACADA

La Teoría de la Computa-

ción es una maravillosa
disciplina que constituye
los fundamentos de la
Computación como tal.
Su importancia es doble:
por un lado nos permite entender los
límites de lo computable, es decir, qué
problemas pueden ser resueltos utilizan-
do un algoritmo y, por otro, nos ayuda a
diseñar herramientas para la resolución
más eficiente de problemas en función
de recursos limitados (memoria, tiem-
po, número de procesadores, etc.).

En su acepción tradicional, la Teoría de
la Computación estudia qué problemas
pueden ser computados y a qué costo.
Para este número, sin embargo, hemos
decidido utilizar una definición amplia
del área, que incluya además de los te-
mas más ortodoxos –como algoritmos,
computabilidad y complejidad– otros
que utilicen una buena dosis de teoría en
su estudio, como por ejemplo Inteligen-
cia Artificial, Lenguajes, Recuperación
de la Información o Bases de Datos.

Nuestra idea ha sido dar una “vista de
pájaro” al estudio de la Teoría de la
Computación en Chile. Esto incluye co-
laboraciones de Gonzalo Navarro sobre
Teoría de la Información; Jorge Baier
sobre Planificación; Diego Arroyuelo
sobre Indexación y Compresión; Jor-
ge Pérez sobre Lenguajes de Consulta
para Bases de Datos; Alejandro Hevia
sobre Criptografía; Éric Tanter sobre
Sistemas de Tipos para Lenguajes de
Programación; y Jérémy Barbay sobre
Algoritmos. Una de las conclusiones
que podemos sacar de todos estos inte-
resantes artículos es que la Teoría de la
Computación que se hace en Chile es de
excelente nivel, pero que es indispensa-

3

ble una mayor masa crítica para lograr
convertirnos en referentes mundiales.

Además de los artículos sobre Teoría de
la Computación, la Revista incluye las
secciones usuales:

• Investigación Destacada, con un artí-
culo de María Cecilia Rivara sobre su
trabajo en Visualización Computacional.

• Computación y Sociedad, que con-
tiene un artículo de Yussef Farrán y
José Durán sobre la historia del De-
partamento de Ingeniería Informáti-
ca y Ciencias de la Computación de
la Universidad de Concepción; otro
de Claudio Gutiérrez con un análisis
comparativo de la vida y obra de Kurt
Gödel y Alan Turing; y finalmente uno
de Felipe Chacón y José A. Pino sobre
el sistema U-papers, que nuestro DCC
ha desarrollado para que la comunidad
acceda a sus publicaciones.

• Survey , donde el alumno de Doctora-
do Miguel Romero nos habla de la reso-
lución de problemas bajo restricciones.

• Grupos de Investigación, a cargo de
Oriel Herrera y Marcos Lévano, don-
de nos cuentan sobre la experiencia de
realizar docencia a través de la inves-
tigación en la Universidad Católica de
Temuco.

En este número inauguramos una nueva
sección que incluye entrevistas a nues-
tros ex alumnos. Esta vez entrevistamos
a Roberto Camhi, creador y actual ge-
rente de Mapcity.

Ojalá que disfruten esta edición de Bits
de Ciencia tanto como nosotros disfru-
tamos preparándola.

Pablo Barceló
Editor General Revista Bits de Ciencia

INVESTIGACIÓN
INVESTIGACIÓN
DESTACADA
DESTACADA

discretización
en ingeniería
computacional
y visualización
científi ca

María Cecilia Rivara
Profesora Titular Departamento de
Ciencias de la Computación, Universidad
de Chile. Dr. in Applied Sciences (1984) y
Master of Engineering (1980), Katholieke
Universiteit Leuven, Leuven, Bélgica;
Ingeniera Matemática, Universidad de Chile
(1973). Intereses en investigación: Mallas
Geométricas y aplicaciones, Algoritmos
para Triangulaciones, Algoritmos Paralelos,
Métodos Numéricos, Computación Gráfi ca,
Métodos de Elementos Finitos, Modelación
Geométrica, Visualización Científi ca,
Ingeniería y Ciencia Computacional,
aplicaciones a Ingeniería, aplicaciones
Médicas.
[email protected]

4
4

Discretización es un an-

glicismo que aún no es
aceptado por la Real Aca-
demia Española. Es un
concepto importante que
cruza todos los campos
relacionados con Ingeniería y Ciencia
Computacional, y que da soporte a la
computación gráfica, la visualización
científica, la visualización realista, el
diseño de las arquitecturas de hardware
gráficas, y todas las aplicaciones de estos
temas. Se refiere a la necesidad de mo-
delar objetos geométricos continuos en
base a una cantidad finita y adecuada de
información para los fines requeridos por
una aplicación específica. En este artícu-
lo revisamos el uso interdisciplinario de
estas ideas y lo relacionamos con inves-
tigación realizada en el Departamento de
Ciencias de la Computación de la Uni-
versidad de Chile.

Discretización
De superficies

Para introducir el tema consideremos
una geometría simple: una placa plana
rectangular y sin grosor en dos dimen-
siones. La modelación computacional
más simple de esta geometría consiste en
seleccionar un conjunto finito y ordena-
do de puntos (arreglo o matriz) sobre la
superficie de la placa que se usa como
base para construir una aproximación
del objeto geométrico. Con estos datos
se puede usar este mismo modelo discre-
to simple para aproximar la geometría
continua (ver Figura 1a), lo que permite
definir funciones discretas sobre estos
puntos como los usados en los métodos
de diferencias finitas. Una alternativa
más compleja es construir una aproxi-
mación poligonal de la geometría de la

placa en base a cuadriláteros o triángulos
(Figuras 1b y 1c). En estos dos últimos
casos se tiene una aproximación conti-
nua de la superficie construida en base a
los puntos discretos de la Figura 1a que
se transforman en vértices de la malla de
cuadriláteros (Figura 1b) y de la triangu-
lación (Figura 1c). Las aproximaciones
poligonales tienen la ventaja de ser su-
perficies continuas, donde cada polígono
está definido por la ecuación de un pla-
no; tiene área definida y normal asocia-
da. Sobre estas mallas de polígonos se
pueden definir funciones con distintos
grados de continuidad, de acuerdo a los
requerimientos de aplicaciones comple-
jas. También permite realizar trabajo so-
fisticado de visualización, que requiere
de modelos de iluminación que necesitan
las normales a la geometría para pintar
el objeto.

(a)

(b)

(c)

Figura 1 • (a) Modelo discreto: conjunto de puntos. (b) Malla de cuadriláteros. (c) Triangulación (malla de triángulos).

5

INVESTIGACIÓNDESTACADAejemplos De
Discretizaciones
poligonales

Modelos poligonales más avanzados se
ilustran en las Figuras 2 y 3. La Figura
2 muestra dos triangulaciones de la su-
perficie del Lago Superior, compartido
entre Canadá y Estados Unidos. La trian-
gulación 2a se ha construido en base a
una aproximación poligonal del borde
de dicho lago. Observe que los vértices
de la triangulación corresponden sólo a
los vért