|
Computabilidad: fundamentos y aplicaciones
|
Esta página NO es para
saber cómo se sigue y se aprueba la asignatura: para esto
tienes la Guía de Aprendizaje
entregar prácticas, comunicar conmigo, bajar el material:
para esto tienes la página de la asignatura en
Áula Virtual (el Moodle)
|
|
|
Esta página es para
saber de qué va esta asignatura
hacerte una idea de si te va a gustar o no
|
Supongamos que Alice y Bob
están implementando un sistema informático. Alice se
encuentra con un fragmento de código P que quiere
reutilizar, pero no está segura de lo que el código
hace. Por esto pide a Bob que le diga lo que P calcula
(Nota: este programa está escrito en el lenguaje usado por
el analizador Interproc;
se trata de una lenguaje muy sencillo que cualquier informático
con conocimientos de algún lenguaje imperativo puede entender
fácilmente):
proc p(a:int) returns (b:int)
begin
b = a*2;
end
var x:int, y:int;
begin
x = 20;
y = p(x);
end
Es muy fácil entender el resultado del
cálculo de P, así que Bob puede contestar a la
pregunta en pocos segundos y sin ninguna dificultad.
Ahora supongamos que Alice encuentra otro
fragmento de código, Q, y, otra vez, quiere usarlo en su
sistema. Para ello, pide a Bob que eche un vistazo a Q y le
diga lo que calcula (Nota: para los que tengan dudas, "/" es la
división entera y "%" es el resto):
proc p(a:int) returns (b:int)
var c1:int, c2:int, c3:int;
begin
c1 = a / 3;
c2 = a % 3 - 1;
b = c2;
c3 = c1;
while (c3>0) do
b = b + c3 % 3 + 2;
c3 = c3 - 1;
done;
if (c2 > 1) then
b = b + 2;
else
b = b + c2 + 1;
endif;
b = b + c1 * 3;
if (c1 % 3 == 2) then
b = b + c3;
else
b = b + 1;
endif;
end
var x:int, y:int;
begin
x = 20;
y = p(x);
end
Es evidente que entender lo que hace Q
es mucho más difícil, así que Bob tarda un buen
rato para contestar. Sin embargo, el resultado final es
que... ¡P y Q calculan exactamente lo mismo!
En general, Bob podrá con cualquier
fragmento de código, y encontrará una respuesta para
todas las preguntas que Alice le pueda poner. Lo malo es que
podría tardar muchísimo (no sería muy
difícil producir programas mucho más largos y complejos
que sigan calculando la misma función). Por esto los
informáticos intentan desarrollar unos programas, que
llamaremos analizadores, que realicen el trabajo de Bob
tardando mucho menos y con un mayor nivel de fiabilidad.
Lo que pasa es que ni siquiera el
analizador más potente podrá contestar a todas las
preguntas de Alice: siempre habrá un programa para el que
no sabrá dar una respuesta (en este caso, que el valor final de
"y" es 40).
En este curso vamos a entender por qué
pasa esto.
|