publicado a la(s) 20/12/2009 11:56 por Ignacio Matilla Iraola
[
actualizado el 20/12/2009 12:07
]
publicado a la(s) 20/12/2009 11:55 por Ignacio Matilla Iraola
En mi opinión, el mundo
de la algoritmia consiste en la tarea de ver cómo problemas que
normalmente no piensas en como resolver se pueden expresar de un modo
que nunca te habias planteado, y en la fascinación de ver cómo los
comandos encajan poco a poco hasta realizar la acción que tú deseas
que realicen. Esto alcanza su máximo exponente cuando te topas con
un problema que ni siquiera tú sabes como resolver, y, utilizando
las herramientas que has ido obteniendo durante el aprendizaje de
algoritmia y programación, consigues hallar la forma de obtener la
solución (y eso es la algoritmia: no tanto el obtener la solución
sino obtener el procedimiento necesario para llegar a ella).
|
publicado a la(s) 20/12/2009 11:53 por Ignacio Matilla Iraola
Con
todas las herramientas en la mano
y el algoritmo preparado, ya solo queda ver la relación entre el
algoritmo construido y el código resultante de la traducción a
lenguaje de programación. Si bien las estructuras básicas son
prácticamente las mismas, las instrucciones son menos “explicativas”
y más concretas. Así, en lenguaje c, para declarar una variable
numérica entera se escribe “int”, al escribir un mensaje se usa
“printf”, para que en la pantalla se pase a la siguiente línea
se usa “\n” (en el pseudocódigo se obvia), para iniciar y
terminar un bucle se utilizan los signos “{” y “}”...
En
los pseudocódigos de este documento,
Y
no hay que olvidar que cada lenguaje de programación tiene sus
propias especificaciones. En este documento he utilizado
pseudocódigos cercanos al lenguaje C, pero para otros lenguajes
(pascal, html, php) se utilizan comandos distintos o incluso la
estructura tiene diferente apariencia.
|
publicado a la(s) 20/12/2009 11:51 por Ignacio Matilla Iraola
Empezaremos
por explicar un poco las variables. En alguno de los algoritmos
se ven en el entorno las palabras “variable numérica entera”.
Hay tres tipos de variables: numéricas enteras, numéricas reales y
alfanuméricas. En una variable entera se puede meter un número
entero (positivo o negativo, pero sin decimales), en una variable
real se puede meter un número real (positivo y negativo con coma
flotante) y en una variable alfanumérica se pueden meter números,
caracteres y cadenas de caracteres (hay una gran diferencia entre
estos dos últimos a la hora de programar; sin embargo, no es
significativo a la hora de diseñar un algoritmo).
En
todos los tipos de bucles y selecciones se verifica el valor de una
variable (normalmente; como excepción se pueden usar sentencias del
tipo “mientras 1 sea distinto de 2” para crear bucles infinitos).
Dentro del bucle, el valor de esa variable se deberá modificar para,
en algún momento, llegar a la condición de salida del bucle. Para
ello, se puede pedir al usuario un nuevo valor de la variable, o se
puede crear lo que se llama contador; esto es, una variable que
inicializas en cualquier valor y luego modificas de forma constante
su valor dentro del bucle para “contar” algo. A continuación
incluyo un ejemplo:
variable
numérica entera
contador /*la variable puede tener cualquier nombre. */
contador
← 1 /*Llamarla contador es un capricho del
autor*/
mientras
contador <> 5 hacer
escribir
“es la “,contador,”ª vez que hago el bucle”
contador ← contador + 1
Fmientras
Falgoritmo
Parecidos
a los contadores son los acumuladores: Variables en las que vas
guardando valores que se pueden sumar, multiplicar, elevar a una
potencia, etc. Ejemplo:
variable
numérica entera
acumulador, contador, numero
contador
← 1
acumulador
← 0
mientras
contador <> 5 hacer
escribir
“introduzca un número”
leer
numero
acumulador
← acumulador + numero
contador=
← contador + 1
Fmientras
escribir
“el total introducido es ” acumulador
Falgoritmo
Otra
gran herramienta es el switch, ya nombrado en el ejemplo “juego de
nim” ( Que puede encontrarse en la sección de ejemplos). Resumiendo, se trata de una variable que puede tener 2
valores. Pueden ser cualquiera, pero a lo largo del programa tiene
que intercambiar de valor entre uno y otro sin cambiar a otro valor.
Se suele utilizar 0 y 1, aunque una de las posibilidades que ofrece
es utilizar 1 y -1; de este modo, solo habrá que cambiar su valor
una vez al final del bucle, multiplicandolo por -1. La diferencia
sería algo así.
/*Ejemplo
con SW=0 ó 1*/
variable
numérica entera
contador, SW
contador
← 1
SW
← 0
Mientras
contador <> 5 hacer
si
SW=0 entonces
escribir
“hola”
SW
← 1
sino
escribir
“adiós”
SW
← 0
Fsi
Fmientras
Falgoritmo
/*Ejemplo con SW=1 ó -1*/
variable
numérica entera
contador, SW
contador
← 1
SW
← 1
Mientras
contador <> 5 hacer
si
SW=0 entonces
escribir
“hola”
sino
escribir
“adiós”
Fsi
SW ← SW*-1
Fmientras
Falgoritmo
Comentarios:
Habrás observado que, a lo largo de los algoritmos, en ocasiones se
ven porciones de texto entre los signos /* y */. Se llaman
comentarios, y son una herramienta utilizada en programas largos para
no perderse, o en caso de ser un programa que se va a realizar en más
de una sesión. También es válido para introducir un comentario
utilizar dobles barras (// comentario //).
Por
último, queda decir que la gran herramienta definitiva para la
creación de un algoritmo es la imaginación y la lógica. Combinando
las herramientas explicadas hasta ahora con algunas herramientas más
concretas se puede realizar casi cualquier algoritmo que, una vez
traducido a lenguaje de programación, hará que el ordenador realice
todo aquello que le quieras mandar hacer.
|
publicado a la(s) 20/12/2009 11:47 por Ignacio Matilla Iraola
Donald Knuth
Datos
biográficos:
Nacido
el 10 de enero de 1938 en Milwaukee, Wisconsin
Es
uno de los más reconocidos expertos en ciencias de la computación
por su seminal investigación dentro del análisis de algoritmos y
compiladores. Es Profesor Emérito de la Universidad
de Stanford.
Se
le conoce principalmente por ser el autor de la obra The art of
computer programming (El arte de programar computadoras u
ordenadores), una de las más respetadas referencias en el campo de
las ciencias de la computación. Sentó las bases de y dio nombre al
análisis de algoritmos y ha realizado numerosos aportes a varias
ramas teóricas de la informática. Es el creador de TEX, del sistema
de diseño de tipos METAFONT y del estilo de programación conocido
como programación literaria (Literate
programming).
Knuth
es un programador conocido por su humor geek:
ofrece una recompensa de 2,56 dólares a quien encuentre errores
conceptuales o tipográficos en sus libros (la razón detrás de la
extraña cifra es que «256 centavos son 1 dólar hexadecimal»), y
por otro lado ofrecía 3,16 por errores en 3:16 Bible Texts
Illuminated. Numeró las distintas versiones de TEX de manera que se
aproximaran al número π (3, 3,1, 3,14, etc.), al igual que los
números de versión de MetaFont se van aproximando a e. Su cita más
célebre, al enviarle sus comentarios a un colega autor de un
algoritmo, es: «Cuidado con los errores en el código anterior; sólo
he demostrado que es correcto, no lo he probado».
Knuth
es el autor de 3:16 Bible Texts Illuminated (1991, ISBN 0895792524),
libro en el que intenta examinar la Biblia por un proceso de
«muestreo estratificado aleatorio», es decir, un análisis del
capítulo 3, versículo 16 de cada libro. Cada versículo se acompaña
de un renderizado en arte caligráfico, realizado por un grupo de
calígrafos capitaneado por Hermann Zapf.
Está
casado con Jill Carter Knuth. Tienen dos hijos.
Luis Joyanes
Aguilar
Datos
biográficos:
Dr.
en Ingeniería Informática y Dr. en Sociología (Licenciado en
Ciencias Físicas y Licenciado de Enseñanza Superior Militar).
Profesor Titular de la Cátedra de Lenguajes y Sistemas Informáticos
de la Facultad de Informática de la Universidad Pontificia de
Salamanca, campus de Madrid.
Decano
de la Facultad de Informática y Director del Departamento de
Postgrado (Doctorado y Master en Ingeniería Informática). Conocido
por crear el lenguaje de pseudocódigo UPSAM, que es referencia en
gran cantidad de cursos de programación.
Su
bibliografía se puede encontrar en
la sección “cursos de diseño de algoritmos” de este website.
Robert
Sedgewick
Datos
biográficos:
Nacido
en Estados Unidos en 1946. Profesor de informática en la Universidad
de Princeton y
miembro de la directiva de Adobe
Systems.
Terminó
su doctorado en Filosofía en 1975 bajo la supervisión de Donald
Knuth en Stanford.
Su tesis fue sobre un algoritmo de ordenación quicksort. Entre 1975
y 1985 fue ayudante en la facultad de la Universidad
de Brown. Desde 1985
ha estado en el departamento de Ciencia Informática de la
Universidad de Princeton. En 1997 fue nombrado “fellow”
(compañero) de la Asociación por la Maquinaria de Computación por
su trabajo en análisis matemático de algoritmos.
Robert
Swdgewick es autor de la serie de libros Algorihtms,
publicada por Addison-Wesley. La primera edición del libro fue
publicada en 1983 y contenía código en pascal. Las siguientes
ediciones utilizaron C, C++, Modula-3 y Java.
|
publicado a la(s) 18/12/2009 09:21 por Ignacio Matilla Iraola
[
actualizado el 20/12/2009 11:22
]
Como buenos adictos a la algoritmia, uno siempre esta buscando dónde ampliar sus conocimientos, por ello a continuación referenciaré algunos cursos que me han parecido interesantes.
Uno
de los más comprensibles que he encontrado para aprendices con
escasa experiencia, a la par que muy completo, incluye tanto
pseudocódigos como ordinogramas, guías de como anidar distintas
estructuras y obtener buenos resultados, explica todas las
herramientas existentes en la creación de algoritmos (acumuladores,
contadores, funciones, subprogramas, etc.). http://www.carlospes.com/curso_de_algoritmos/
Curso
ejercido por Luis Joyanes Aguilar, profesor de la UPSAM y creador del
lenguaje UPSAM de pseudocódigo. Libro disponible en librerias o en
compra por internet. Este y otros libros del mismo autor (todos
relacionados con la programación pueden encontrarse en el siguiente
website.
http://www.casadellibro.com/libros/joyanes-aguilar-luis/joyanes2aguilar32luis
Libro
con todo lo necesario para programar en lenguaje c, explicando todas
las bases algorítmicas y todas las funciones, secuencias y
herramientas disponibles en este lenguaje. Libro escrito por Carlos
Pes Rivas (el mismo autor que el curso citado arriba). Cabe destacar
que en el website de este autor se incluye un listado de las
bibliotecas en las que puedes pedir prestado su libro (de forma
gratuita), así como las librerías colaboradoras donde se puede
comprar, y un índice de información con un par de erratas,
contenidos, metodologías y más información sobre el producto y
contenidos gratuitos (incluso partes del libro en PDF).
http://www.carlospes.com/libro_edc_lenguajec/
|
publicado a la(s) 18/12/2009 09:16 por Ignacio Matilla Iraola
[
actualizado el 20/12/2009 11:32
]
Anidamiento
Hasta
ahora hemos visto estructuras en cuyo interior hay instrucciones,
pero: ¿En qué consisten esas instrucciones? Pueden ser
instrucciones del estilo de x ← 1+2, pero también puede
haber más estructuras dentro de una estructura
(de hecho el “Sino si” es en realidad un “si” dentro del
conjunto de instrucciones del “sino”), dando lugar a una
estructura anidada.
Funciones
y procedimientos
Una
función, al igual que una función matemática, recibe uno o más
valores de entrada
y devuelve una salida,
mientras que un procedimiento no devuelve nada.
Función
x (a, …, n) /*Comentario: En el parentesis vienen los valores de
entrada*/
Instrucciones
Devolver
r /*r sera un valor obtenido de las instrucciones*/
Ffunción
Para
llamar a una función desde la principal se tendrá que escribir el
nombre de la función
y en el interior del paréntesis las variables que envias a esa
función (en blanco si no envias nada).
Ventajas
de usar un pseudocódigo
La
principal diferencia es que ocupa mucho menos espacio para algoritmos
más largos, sobre todo si incluyen iteraciones y condiciones. En
estructuras repetitivas también da facilidad para representar
operaciones complicadas. Puesto que se usa de base para realizar un
programa, tiene la ventaja de ser más facil de traducir, puesto que
la estructura es básicamente la misma. Si se utilizan los márgenes
correctamente, es más facil ver los niveles de la estructura del
algoritmo, y al estar escrito linealmente es fácil seguir una por
una las instrucciones para llegar a la solución del problema.
Pseudocódigo
de la UPSAM
El
pseudocódigo de la UPSAM (Universidad Pontificia de SAlamanca,
campus de Madrid) es un lenguaje basado en pascal y traducido al
castellano, creado por el profesor Luis Joyanes Aguilar. Cuenta con
equivalentes a prácticamente todas las funciones, y es fácil de
entender y traducir. Para conocer las especificaciones de este, entra aquí
Para obtener ejemplos de algoritmos en pseudocódigo y un ejemplo de programa, visita esta sección del site
|
publicado a la(s) 18/12/2009 09:11 por Ignacio Matilla Iraola
Como
su nombre indica, se trata de “códigos falsos”. Se refiere a
códigos de programación,
y consiste en transcribir, con la estructura de un programa, la lista
de pasos de forma que sea traducible a algún lenguaje de
programación. Al contrario que en los ordinogramas, no hay ningun
estándar
oficial para los pseudocódigos, aunque se intenta que se asemejen al
lenguaje en el que se espera tradudirse. Suelen utilizar los símbolos
comunes a la hora de realizar operaciones matemáticas, a diferencia
de los programas que requieren un lenguaje propio para referirse a la
mayoría de operaciones.
Estructuras
de control
Las
instrucciones se siguen de forma lineal una tras otra, de arriba
hacia abajo, de la siguiente forma:
Instrucción
1
Instrucción 2
Instrucción 3
…
Instrucción n
-Selectiva
simple (si)
Comprueba
una condición, y si se cumple, realiza las instrucciones en el
interior.
Si
condición entonces
Instrucciones.
Fsi.
-Selectiva
doble (si, sino)
Parecida
a la anterior, pero, si no se cumple, realiza otras instrucciones.
Si
condición entonces
Instrucciones1.
Sino
Instrucciones2.
Fsi
-Selectiva
múltiple.(si, sino si)
Da lugar a selecciones con más de dos opciones.
Si
condición entonces
Instrucciones1.
Sino
Si
condición2 entonces
Instrucciones2.
…
Sino
Instrucciones n
Fsi
En este tipo de
selección, cada condición excluye a las siguientes. Si el que
realiza las instrucciones del algoritmo entra en una
condición, no hará ninguna de las demás. En caso de
poder darse una situación en la cual no se cumple ninguna de las
situaciones, se
haría el último “Sino” o, en ausencia de este, se saldría
de la selección sin hacer nada.
-Selectiva
múltiple en casos.
Esta es un poco distinta, aunque en esencia es similar a la
anterior. Se busca en el contenido de un
“indicador” el valor de uno de los casos, en el cual se entrará
y se
realizarán las instrucciones
del interior. La aparencia de esta estructura sería así:
Seleccionar
indicador
Caso
1
Instrucciones1
Caso
2
Instrucciones2
Caso
3
Instrucciones3
…
En otro caso
Instrucciones
n.
Fseleccionar
Realiza
unas acciones un número de veces que viene definido por una
condición.
-Bucle
mientras:
Realiza las instrucciones mientras la condición dada sea
cierta. La variable que se
compruebe en el inicio del bucle debe tratarse antes de entrar
en este y antes de salir (si
no se tratara antes de salir, daría lugar a un bucle
infinito).
Mientras
condición Hacer
Instrucciones
Fmientras
-Bucle
repetir:
Tiene como principal diferencia con el anterior que realiza las
instrucciones mínimo
una vez, ya que comprueba la condición al final. Además, este
bucle realizara las
instrucciones hasta
que se cumpla la condición, y no mientras.
Repetir
Instrucciones
Hasta
condición
-Bucle
para:
Este se utiliza cuando se conoce el número de veces que se
desean realizar las
instrucciones.
Para
i ← x
hasta
n
hacer
Instrucciones
Fpara
Aclaración:
en este caso, “i” tiene un valor inicial “x” y va aumentando
en 1 hasta
llegar a “x”. Si se quisiera incrementar (o reducir) el
valor de i en otra cantidad, la
línea inicial sería así:
Para
i ← x
hasta
n
en
y hacer
-Bucle
para cada:
Se utiliza cuando hay una lista
L
y se quiere realizar las instrucciones para cada
componente de dicho grupo.
Para
cada x
de L
hacer
instrucciones
Fpara
cada
(Continua en la parte 2)
|
publicado a la(s) 18/12/2009 09:01 por Ignacio Matilla Iraola
[
actualizado el 18/12/2009 09:10
]
También
conocidos como diagramas de flujo, consisten en una representación
gráfica del algoritmo. Siguen un estándar oficial que regula el
significado de la forma de cada “globo” de información; por
ejemplo, el rombo significa decisión entre dos o más caminos. En
un ordinograma, se deben cumplir tres condiciones:;)
1. Existe
un camino para hallar la solución.
2. Solo existe un inicio
para el proceso.
3. Existe un solo final, a
no ser que haya más de un camino.
Antes de realizar un ordinograma
se deben llevar a cabo los siguientes puntos.
Identificar
las ideas principales a ser incluidas en el diagrama de flujo. Deben
estar presentes el dueño o responsable del proceso, los dueños o
responsables del proceso anterior y posterior y de otros procesos
interrelacionados, otras partes interesadas.
Definir
qué se espera obtener del diagrama de flujo.
Identificar
quién lo empleará y cómo.
Establecer
el nivel de detalle requerido.
Determinar
los límites del proceso a describir.
Una
vez hecho esto, para construir el diagrama de flujo, se deben seguir
los siguientes pasos.
Establecer
el alcance del proceso a describir. De esta manera quedará fijado
el comienzo y el final del diagrama. Frecuentemente el comienzo es
la salida del proceso previo y el final la entrada al proceso
siguiente.
Identificar
y listar las principales actividades/subprocesos que están
incluidos en el proceso a describir y su orden cronológico.
Si
el nivel de detalle definido incluye actividades menores, listarlas
también.
Identificar
y listar los puntos de decisión.
Construir
el diagrama respetando la secuencia cronológica y asignando los
correspondientes símbolos (consultar
los anexos para conocer el significado estándar de los símbolos).
Asignar
un título al diagrama y verificar que esté completo y describa con
exactitud el proceso elegido.
Como
ventajas, los diagramas de flujo tienen a su favor una rápida
y fácil interpretación. Se distinguen fácilmente los bucles,
repeticiones, etc...
Como
desventaja principal es la cantidad de espacio que ocupa, mucho mayor
que un algoritmo que solo tenga texto, lo cual limita los
ordinogramas a algoritmos pequeños y más o menos sencillos.
|
publicado a la(s) 18/12/2009 08:54 por Ignacio Matilla Iraola
La
algoritmia consiste en la búsqueda de soluciones a un problema
concreto. Pero, en aras de entender mejor lo que esto significa, hace
falta una definición más extensa. Un algoritmo es la transcripción
exacta de una serie de instrucciones
concretas con las
cuales se encuentra una
solución.
Para
el mejor entendimiento, lo mejor es un ejemplo: Si quieres encender
una televisión, nadie se plantea que eso pueda ser un problema,
puesto que el objetivo es verla. Sin embargo, si te planteas el
encender la televisión como el problema a resolver, verás que los
pasos exactos e infalibles son:
-
Buscar el mando.
-
Comprobar que tiene pilas.
-
Comprobar que la televisión esta enchufada.
-
Comprobar que los fusibles están encendidos.
-
Pulsar el botón de encendido.
Este
es un ejemplo, pero cada paso a su vez se podría plantear como un
problema (¿Cómo compruebo si tiene pilas? ¿Cómo busco el mando si
no se donde está?). Además. Puede haber caminos alternativos, más
o menos seguros que este para llegar a la misma solución: Puede ser
una televisión sin mando o que simplemente prefieras encender desde
el botón, por ejemplo. Por lo tanto, hay
infinidad de posibles algoritmos para el mismo problema.
Si dos personas realizan un algoritmo, es más que probable que los
algoritmos serán distintos puesto que cada uno tiene su punto de
vista de la forma correcta de llegar a su objetivo.
Tampoco
son necesarios ejemplos “rebuscados” para encontrar un algoritmo:
Casi cualquier aparato electrónico (o no) viene con instrucciones de
uso: He ahí un algoritmo.
|
|
