6. Algoritmos de
búsqueda y ordenación
En muchas situaciones de programación es necesario repetir ciertos
procedimientos
hasta alcanzar un punto en que no se puede o no se desea
continuar. Esta repetición de tareas puede llevarse a cabo
básicamente de dos maneras diferentes: la iteración
y la recursión. Como se supone que en cada
repetición se procesa un estado
diferente de cosas -sin lo cual el proceso
tendería al infinito-, ambos métodos
presentan también alguna forma de control de fin de
tarea.
La idea básica en un algoritmo
iterativo es que la repetición de la tarea se controla
desde afuera. Se ejecuta un conjunto de acciones en
forma completa, se verifica la condición de salida y si es
necesario se vuelve a ejecutar el conjunto de acciones en
forma completa. El orden en que se ejecuta y evalúa
determina que el algoritmo sea
de evaluación
previa (primero se evalúa la condición de salida y
luego se ejecutan las acciones) o de evaluación
posterior (primero se ejecutan las acciones y luego se
evalúa el resultado). En ambos casos, sin embargo, el
control de las
repeticiones es exterior al grupo
principal de acciones.
En un algoritmo recursivo, en cambio, la
tarea se controla desde adentro. Se comienza a ejecutar un
conjunto de acciones, pero antes de finalizar se evalúa si
se ha llegado a la condición de salida; si no es
así, se continúa ordenando una nueva
ejecución del mismo conjunto de acciones. Finalmente se
concluye con la tarea iniciada. Dicho en otros términos,
el procedimiento se
llama repetidas veces a sí mismo, y el control de esas
llamadas forma parte del grupo
principal de acciones.
Por otra parte, si bien hay problemas que
se resuelven más directamente en forma iterativa y otros
que son más naturalmente recursivos, ambas técnicas
son compatibles e intercambiables, por lo que todo algoritmo
recursivo puede transformarse en iterativo y
viceversa.
Algoritmos De Búsqueda
Cuando se trata de buscar un valor en un
arreglo ordenado de datos, el
algoritmo de búsqueda binaria es el más
frecuentemente utilizado. La idea central de este algoritmo es
comparar el elemento ubicado en el lugar central del arreglo con
el valor buscado.
Si el elemento central es igual al valor buscado la
búsqueda finaliza con éxito.
Si no es así, puede ocurrir o bien que el elemento central
sea mayor que el buscado -en cuyo caso el elemento coincidente
debe estar en la mitad inferior del arreglo- o bien que sea menor
-y el elemento coincidente se encuentra en la mitad superior. En
ambos casos se prosigue la búsqueda en la mitad que
corresponde, si es que quedan elementos en esa dirección, o bien se finaliza la
búsqueda sin éxito,
en caso contrario. Existe naturalmente una solución
recursiva, ya que si el valor buscado no es hallado en la
posición del centro se repite el mismo procedimiento con
una de las mitades del arreglo, y así hasta que se
encuentre el valor o no queden más "mitades".
Compárese esto con el problema de las bolillas dentro de
las cajas, en el cual la "bolilla blanca" sería el valor
buscado y la "caja interior" sería la mitad que se debe
seguir examinando.
En ocasiones es necesario determinar no sólo si el valor
buscado se halla en el arreglo, sino además saber en
qué posición está (o debería estar,
si es que no existe). Por ejemplo, si se desea insertar un nuevo
valor en un arreglo ordenado, una solución eficaz es
"buscar" el valor en el arreglo (aunque se sepa de antemano que
no se encuentra) para determinar la posición correcta en
la que debe ser insertado. En esos casos se debe informar por
algún medio (generalmente un puntero pasado como
parámetro o una variable global) cuál es la
posición lógica
del elemento buscado dentro del arreglo.
Ejemplo de un Algoritmo de Búsqueda
A modo de ejemplo se presenta una versión de la
función
int busbin (int *vec, unsigned tam, int val, unsigned *ord);
Ésta realiza una búsqueda binaria del elemento val
en el vector de enteros apuntado por vec de tam elementos y deja
en la memoria
apuntada por ord la posición lógica
que tiene (o debería tener) el elemento buscado. Retorna 1
si el elemento es hallado o 0 en caso contrario. Para calcular el
elemento mitad del vector se desplaza tam un bit a la derecha, lo
que equivale a dividirlo en dos, pero resulta mucho más
rápido para el procesador que la
operación de división.
int busbin (int *vec, unsigned tam, int val, unsigned *ord)
{if (!(vec && tam && ord)) return 0;
unsigned mitad = tam >> 1; // Divide tam en 2 desplazando
un bit a la// derecha. Es más rápido que tam /
2.
if (vec [mitad] == valor) { *ord += mitad; return 1; }
if (vec [mitad] < valor)
{ mitad++; *ord += mitad; vec += mitad; tam -= mitad; }
else tam = mitad;
return tam? busbin (vec, tam, va, ord): 0;}
Algoritmos De Ordenacion
Se presentan aquí dos métodos
muy utilizados para obtener el ordenamiento de un conjunto de
datos: el
algoritmo de ordenamiento por inserción y el algoritmo
conocido como quick sort (ordenamiento rápido). Estos dos
algoritmos son
ilustrativos, además, porque el algoritmo de ordenamiento
por inserción es esencialmente iterativo, mientras que el
algoritmo de quick sort es esencialmente recursivo.
A continuación se comentan las características de ambos algoritmos para
ordenar en forma ascendente los valores
dentro de un vector en memoria.
Siguiendo este ejemplo, para obtener ordenamientos descendentes
basta cambiar el sentido de las comparaciones por desigualdad, y
para otro tipo de soporte de datos (archivos en
disco, por ejemplo) los cambios se referirán
principalmente al modo de leer y escribir los datos.
Ordenación por Inserción:
La idea central de este algoritmo es recorrer secuencialmente y
hacia delante el conjunto de datos comparando cada elemento con
el anterior. Si el elemento actual es igual o mayor que el
anterior entonces ese par de datos se encuentra en la secuencia
correcta, por lo que no hay que modificar nada. Si, en cambio, el
actual es menor que el anterior, significa que el actual
está fuera de secuencia, por lo que debe ser insertado en
el lugar correcto entre los valores que
han quedado atrás. Una vez resuelta esta cuestión,
se repite el proceso con el
elemento siguiente del conjunto hasta que no haya más
elementos.
Dos características surgen directamente de esta
descripción:
- Si hay que comparar cada valor con el anterior,
entonces se debe comenzar el proceso por el segundo elemento,
ya que es el primero en tener uno anterior. - Si se van reinsertando correctamente "hacia
atrás" los valores
a medida que se avanza (o si se avanza sin reinsertar porque no
es necesario), entonces los elementos anteriores al actual ya
están ordenados.
La tarea de reinsertar un elemento "hacia atrás"
cuando se descubre que está fuera de secuencia es
accesoria y puede ser realizada por una función
auxiliar. Esta función
auxiliar se puede implementar de varias maneras, pero todas ellas
deben partir de la certeza de que ese subconjunto de elementos ya
está ordenado. A continuación se presentan una
implementación de la función principal
int *ordins (int *vec, unsigned tam);
y dos implementaciones alternativas de la función
auxiliar
void insertar (int *ult, unsigned tam);
La función ordins () ordena por inserción el vector
de enteros apuntado por vec de tamaño tam y retorna vec,
mientras que ambas versiones de insertar (), ubican el valor
contenido en el elemento apuntado por ult entre los tam elementos
ordenados que han quedado atrás. Ambas funciones
auxiliares son estáticas -esto es, de uso "privado" dentro
del módulo donde están insertas- ya que la tarea
que realizan es subsidiaria y dependiente de la función
ordins ().
int *ordenar (int *vec, unsigned tam)
{int *ant = vec, *act = vec + 1;unsigned i;for (i = 1; i <
tam; i++, ant++, act++)
if (*act < *ant) insertar (act, i);return vec;}
La primera versión de insertar () es
típicamente iterativa y efectúa una especie de
rotación de los valores de los
elementos. Primeramente resguarda en la variable local auxiliar
aux el valor del ítem a reinsertar -que se encuentra en
*ult- y a continuación procede a mover una posición
hacia delante cada uno de los elementos anteriores a aux
retrocediendo en el vector hasta que no hay más elementos
o encuentra uno que no es mayor que aux. Finalmente reinserta el
valor de aux en el lugar donde se encontraba el último
elemento removido.
static void insertar (int *ult, unsigned tam)
{int *ant = ult – 1; // ant apunta siempre al ítem
anterior a ult.
int aux = *ult; // aux contiene el valor a reinsertar.
do *(ult–) = *(ant–); // Evaluación posterior porque ya
se sabe que el
while (–tam && aux < *ant); // primer ítem
anterior a ult es mayor que *ult.
*ult = aux; // Restituye el valor de aux en la última} //
posición vacante.
La segunda versión de insertar () recurre a su
vez a la función auxiliar de búsqueda binaria
busbin (), con el fin de determinar la posición que debe
ocupar el elemento *ult entre los anteriores a ult. Para ello
inicializa las variables
globales estáticas valor y orden, que son utilizadas por
busbin () para conocer el elemento buscado e informar su
posición. Obsérvese que para que esta
versión de insertar () pueda acceder a otras funciones y
variables
globales estáticas, debe estar incluida a su vez en el
mismo módulo de código
que ellas. Luego de obtener a través de busbin () el lugar
que debe ocupar el nuevo ítem, calcula la cantidad de
elementos a desplazar y -como la primera versión- mueve
una posición hacia delante cada uno de los elementos
anteriores a ult retrocediendo en el vector hasta llegar a la
posición correcta. Ya no necesita comparar y contar puesto
que, al conocer la cantidad de elementos a desplazar, sólo
necesita contar. Finalmente reinserta el valor de aux en el lugar
donde estaba el último elemento removido.
static void insertar (int *ult, unsigned tam)
{unsigned _ord = 0; // _ord contendrá la posición
correcta de *ult.
int *ant = ult – 1; // ant apunta al ítem anterior a
ult.
valor = *ult; // Inicializa las variables globales
estáticas
orden = &_ord; // que utilizará busbin ().
if (–tam) // Si hay más de un elemento llama a busbin
()
busbin (ant – tam, tam); // con la dirección inicial del vector.
tam -= _ord; // Descuenta de tam la posición del nuevo
ítem.
do *(ult–) = *(ant–); // Desplaza la cantidad necesaria de
elementos
while (tam–); // hacia delante y restituye el valor de valor
*ult = valor; // en la última posición
vacante.}
La ventaja de la primera versión es que es
autónoma, ya que no depende de otras funciones ni
variables globales estáticas, por lo que puede ser
incluida en cualquier módulo de código.
Presenta sin embargo el inconveniente de que tiene que comparar
una y otra vez cada elemento del arreglo para encontrar su
posición correcta. En vectores de gran
tamaño esto puede resentir en forma notable la eficiencia. La
segunda versión, en cambio, soluciona el problema de las
comparaciones sucesivas utilizando un algoritmo de
búsqueda más eficiente, aunque esto la obliga a
convivir en el mismo módulo con otras funciones y
variables globales estáticas de las cuales
depende.
Algoritmo de Quick Sort:
La idea central de este algoritmo es la siguiente: si se toma un
conjunto de elementos desordenados y se ubica uno cualquiera de
ellos -llamado pivote- en una posición tal que todos los
que estén antes sean menores o iguales y todos los que
estén después sean mayores, entonces esa
posición particular sería la correcta para ese
elemento si el conjunto estuviera ordenado. Asimismo se verifica
que el conjunto ha quedado dividido en dos partes: en la primera
están todos los elementos menores o iguales al pivote y en
la segunda todos los mayores. Esto permite aplicar recursivamente
el mismo procedimiento en ambas partes del conjunto hasta que
éste quede completamente ordenado. La tarea de dividir el
conjunto de datos en dos grupos en
torno al
pivote es accesoria y puede ser realizada por una función
auxiliar. Esta función auxiliar se puede implementar de
varias maneras, pero todas ellas deben informar de algún
modo en qué posición ha quedado ubicado el
pivote.
Al igual que busbin (), la función qsort () es recursiva,
y cada llamada provocará que la función se llame
"internamente" a sí misma varias veces. Los valores de los
parámetros vec y tam seguramente variarán entre una
llamada y otra, ya que son los que definen la parte del arreglo
que se ordenará cada vez. Sin embargo, tanto los controles
de que los parámetros sean legales como el retorno de la
función con la dirección original del vector deben
hacerse sólo una vez.
Para evitar tener que hacer estos controles redundantes en cada
llamada recursiva, la tarea se divide entre dos funciones. La
primera está declarada públicamente como
int *qsort (int *vec, unsigned tam);
No es recursiva y sólo realiza las tareas que deben ser
ejecutadas una sola vez: verifica que vec y tam sean legales y
llama a la segunda función, que es la que completa la
tarea. Si vec o tam son ilegales la función retorna vec
sin hacer nada más. La segunda función, definida
como
void _qsort (int *vec, unsigned tam);
Es estática
(por lo tanto inaccesible desde fuera del módulo), y es la
que realmente lleva a cabo la tarea recursiva de ordenamiento.
Recibe los parámetros vec y tam, que varían entre
una llamada y otra, pero que tienen siempre valores legales.
A continuación se presentan dos pequeños
módulos de librería con una versión
optimizada de la función: el módulo qsort.h
contiene simplemente la declaración, mientras que el
módulo qsort.cpp incluye la implementación de la
función principal
int *qsort (int *vec, unsigned tam);
y una implementación de las dos funciones auxiliares
int dividir (int *vec, unsigned tam);
void _qsort (int *vec, unsigned tam);
La función qsort () verifica la validez de los
parámetros vec y tam y llama a _qsort () antes de retornar
vec. La función _qsort () ordena por el algoritmo de quick
sort el vector de enteros apuntado por vec de tamaño tam,
llamando a su vez a la función dividir (). Ésta
divide los tam elementos del vector apuntado por vec en dos
grupos
alrededor de un pivote y retorna la cantidad de elementos del
primer grupo -que incluye al pivote. Ambas funciones auxiliares
son estáticas -esto es, de uso "privado" dentro del
módulo donde están insertas- ya que la tarea que
realizan es subsidiaria y dependiente de la función qsort ().
7. Verificación y derivación de
programas
Conceptos Basicos
La definición del significado de un elemento del lenguaje se
puede realizar de distintas formas, cada una de las cuales define
una semántica diferente del lenguaje. En
esta lección se van a introducir los conceptos más
importantes de algunas de estas formas semánticas, y se
van a tratar más extensamente los conceptos de
corrección, verificación y prueba, ya mencionados
en la lección.
Semántica:
Ahondando en la situación de la introducción anterior sobre la
definición del lenguaje pascal, se puede
conjeturar que la manera informar de definir el significado de
las construcciones del lenguaje es insatisfactoria. El motivo es
la falta de precisión con la que se define el significado
de dichos conceptos, lo cual deja abierta como posibilidad que
dicho significado dependa de la maquina donde se utilice el lenguaje.
Otro problema importante es la ambigüedad del lenguaje
natural, que permite que distintos implementadotes o
programadores entiendan de modo distintos una definición.
Acerca de este tema, el lenguaje
pascal vuelve
a servirnos de ejemplos. Hasta hace no mucho tiempo
existía una gran variedad de versiones del mismo, cada una
realizada específicamente.
Dependiendo del objetivo
prioritario que se presenta cubrir al dar el significado de un
lenguaje podemos encontrar diversas aproximaciones. Entre todas
ellas, las más frecuentemente utilizadas son la sematica
operacional, la sematica declarativa y la sematica axiomatica.
Veamos a continuación una peque son la sematica
operacional, la sematica declarativa y la sematica axiomatica.
Veamos a continuación una pequeña introducción a cada una de estas
aproximaciones.
Semántica operacional:
La semántica operacional define el significado de un
lenguaje de
programación en términos de los cambios de
estado que
producen las instrucciones primitivas del lenguaje. Estos cambios
no se reflejan directamente en la maquina real, sino en una
maquina (virtual) abstracta asociada que sirve como instrumento
de conexión con aquella. Expresado de otra forma, podemos
decir que la semántica operacional define el significado
de un programa en
términos del efecto producido por la ejecución paso
a paso del mismo, de tal modo que la especificación de las
instrucciones del lenguaje mediante instrucciones primitivas de
la maquina abstracta es, precisamente, la definición
semántica del mismo.
A pesar de la aparente simplicidad de este formalismo, este tipo
de semántica no describe con igual claridad todo tipo de
lenguaje de
programación. El motivo es que el mecanismo que
emplean los distintos lenguajes de
programación para realizar un cómputo no
siempre puede expresarse de una manera clara, comprensible y
concisa.
Semántica denotacional:
La semántica denotacional define unas aplicaciones
(funciones) de valoración semántica que asignan a
cada construcción denotada tal objeto
matemático que modela su significado.
Se dice que la construcción denota tal objeto o que este
objeto es la denotación de dicha construcción. En
otras palabras, la semántica denotacional indica que
función matemática
se obtiene a la salida ante unas entradas del programa, sin
preocuparse de la ejecución paso a paso del programa.
Existe una variante de esta semántica que es la
semántica algebraica, en la que se utiliza conceptos
algebraicos a la hora de modelar el significado de las
construcciones.
El primer paso a realizar en la definición de la
semántica denotacional de un determinado lenguaje es el
establecimiento de un dominio semantico
al que pertenecerán los resultados obtenidos de la
evaluación de las construcciones del lenguaje. Esta
evaluación es proporcionada por un conjunto de funciones
de significado cuyo dominio esta
constituido por el conjunto de construcciones del lenguaje y cuyo
rango (o imajen) viene dado por el dominio semantico.
Este tipo de semántica dotan de significado a los
elementos del lenguaje de una manera mas formal y abstracta, pero
sin embargo también necesitan un mayor conocimiento
de conceptos matemáticos, que no tienen por que ser
básicos ni elementales.
Recursividad:
Una función recursiva es una función que se define
en términos de si misma., es decir, en su cuerpo aparece
alguna aplicación suya. La recursividad es un mecanismo
que se usa cuando hay que repetir cierto tratamiento o cálculo
pero el número de repeticiones es variable. De hecho ya se
han visto definiciones recursivas, el tipo suma permite definir
tipos de datos
recursivos, como el tipo de lista. La definición del tipo
lista permite repetir la adición de elementos a una lista.
el numero de adicciones es
variable y determina el numero final de elementos de
lista.
Iteración:
Una instrucción iterativa engloba una secuencia de
instrucciones que se escribe una sola vez, pero permite que se
ejecute varias veces. Una instrucción iterativa
también se llama Bucle. Las instrucciones englobadas
suelen denominarse cuerpo del bucle; cada ejecución del
cuerpo de un bucle se llama iteración del mismo. Hay
varios formatos de bucles que vemos a continuación.
Una instrucción LOOP tiene el siguiente formato:
LOOP
<Instrucción>
Su efecto es ejecutar eternamente la instrucción
englobada. Sin embargo, puede terminarse la ejecución del
bucle si se ejecuta una instrucción especial, formada por
la palabra clave EXIT. Obsérvese que la instrucción
EXIT debe ir incluida dentro de una instrucción
condicional; en caso contrario, el bucle LOOP terminaría
su ejecución al llegar a ella, realizando una
iteración como mucho. Pero esto no tiene mucho sentido,
porque si se hubiera querido realizar una sola ejecución
de dichas instrucciones, no se hubieran incluido en una
instrucción iterativa.
La instrucción EXIT no puede usarse en ninguna de las dos
clases de bucles que se exponen a continuación.
Una instrucción WHILE tiene el siguiente formato:
WHILE <condición>DO
<Instrucción>
La ejecución de una instrucción WHILE comienza
evaluando la condición booleana. Si es cierta, se ejecuta
la secuencia de instrucciones y se comienza de nuevo. Si la
condición es falsa, la ejecución del WHILE termina
y el algoritmo continúa por la instrucción
siguiente al bucle.
La instrucción FOR tiene el siguiente formato:
FOR <variable> IN <subrango>BY<expresión
entera>DO
<Instrucción>
La instrucción FOR usa una variable, llamada variable de
índice, que toma distintos valores en las sucesivas
ejecuciones del cuerpo. La variable de índice debe ser
entera, enumerada o subrango. Los valores que toma la variable de
índice se indica mediante un subrango del mismo tipo y un
incremento. El subrango se expresa de la manera usual: un valor
inicial y un valor final separados por dos puntos. El incremento
viene dado por una expresión entera; puede suprimirse, en
cuyo caso se supone que es igual a uno.
Al comenzar la ejecución del bucle, la variable
índice toma el valor inicial del subrango y se
evalúa la expresión entera para determinar el
incremento.
Veamos el resto del comportamiento
del bucle cuando el tipo de la variable índice es un
subrango entero. Tras cada iteración, el valor del
índice se actualiza, sumándose a su valor el
incremento. Si el incremento es positivo, solo se realiza la
siguiente iteración si el valor de la variable
índice es menor o igual que el valor final del subrango;
por el contrario, si el incremento es negativo, solo se itera de
nuevo cuando su valor es mayor o igual que el valor del final del
subrango.
Si la variable es enumerada o de un subrango enumerado, el
comportamiento
del bucle es parecido. Un valor es menor que otro si tiene un
ordinal menor. El incremento de un valor enumerado produce otro
valor cuyo ordinal es mayor que el inicial en la cantidad
expresada por el incremento.
Semantica Axiomatica
La semántica axiomatica asociada a cada
construcción del lenguaje un axioma lógico que
relaciona el estado del
computo (valores que tienen las variables utilizadas) antes y
después de ejecutar esta construcción. Existen
distintas semánticas, axiomatica, de la que la mas
conocida es la introducida por el sistema formal de
hoare y que es utilizada para definir el significado de lenguaje
imperativos (por ejemplo, pascal).
El método
axiomatico expresa la semántica de un lenguaje de programación asociado al lenguaje una
teoría
matemática
o sistema formal
que permita demostrar propiedades de los programas
escritos en ese lenguaje. Esta aproximación formal
contrasta con el método
denotacional mostrando anteriormente, que asocia a cada
construcción del lenguaje una denotación
(significado) en un intento de encontrar un modelo
matemático (colección abstracta de objetos
matemáticos) del lenguaje.
Un sistema formal puede entenderse como un metalenguaje que pose
su propia sintaxis y semántica. Desde el punto de vista
sintáctico, es necesario definir una gramática en la que se reflejen las
contrucciones validas del sistema formal, normalmente se suele
emplear la sintaxis sde la lógica de predicado de primer
orden ampliada com. expresiones aritméticas y de teoría
de conjuntos. Una
vez fijada la sintaxis a emplear, un sistema formal se define
mediante un conjunto de axiomas (propiedades ciertas escritas en
forma de sentencias logicas) que expresen las propiedades de las
construcciones básicas y un conjuntos de
reglas de inferencias (forma de deducir una propiedades de otras)
que permitan deducir las propiedades de construcciones mas
complejas.
Las definiciones de sistemas formales
para lenguajes funcionales suele hacerse fundamentalmente para
demostrar propiedades que tiene que ver con el tipo de una
expresión y de las subexpresiones que la
componen.
Diseño De Algoritmos Recursivos
Las definiciones recursivas pueden resultar sorprendentes a
primera vista.Incluso puede dar lugar a funciones que nunca
terminen (inútiles como algoritmos), Sin embargo, usadas
juiciosamente son un instrumento potentisimo de diseño
de algoritmos.
En primer lugar, hay que identificar el proceso repetitivo por
realizar. En segundo lugar, hay que considerar que una
función recursiva solo es útil si su
evaluación termina.
Clasificación
Según el número de llamadas recursivas realizadas,
se distinguen tres clases:
Recursividad lineal: El cuerpo de la función contiene una
llamada recursiva. Son las funciones recursivas. Son las
funciones recursivas más sencillas. Todas las funciones
especificadas en este capitulo son recursivas lineales.
Un caso importante de recursividad lineal aparece cuando la
expresión más externa del caso recursivo de la
función es la misma llamada recursiva. Esta clase de
recursividad se llama recursividad de cola.
Recursividad no lineal.
El cuerpo de la función contiene varias llamadas
recursivas. Lo mas frecuente que contenga dos llamadas
recursivas, en cuyo caso se habla de recursividad binaria.
Recursividad mutua: Es un caso curioso de recurcion, una
función no contienen ninguna llamada recursiva, pero
durante la evaluación de su aplicación surgen
llamadas recursivas. Auque a primera vista parezca imposible
obtenérsete comportamiento, la recursividad puede
conseguirse indirectamente si hay dos funciones que se llaman
entre si.
Otra clasificación basada en el formato de los
parámetros de las llamadas recursivas.
Recursividad estructural: Las sucesivas llamadas recursivas sobre
un dato se hacen siguiendo la estructura
recursiva del mismo. En el caso de los elementos enteros, una
recurcion estructurar significa que el valor se vaya
decrementando en uno.
Recurcion bien fundada: Aunque hablando con propiedad,
cualquier recursividad esta bien fundada, suele utilizarse este
término para aquellas recursividades que no son
estructurales. Un ejemplo de función recursiva bien es
invertir Entero, donde el parámetro entero se divide entre
diez.
La primera clasificación dada es útil para decidir
si es conveniente usar una definición recursiva o
iterativa en los algoritmos imperactivo.
La segunda clasificación es útil para decidir el
principio de inducción necesaria para necesaria para
verificar el algoritmo.
Diseño De Algoritmos Iterativos
Cada clase de bucle resulta útil en situaciones
diferentes. El bucle FOR se utiliza cuando se conoce el
número de iteraciones que se quiere realizar. El bucle
WHILE es usado en las otras situaciones en que no se conoce el
número de iteraciones. El bucle LOOP es útil cuando
puede haber varias condiciones de salida del bucle, situadas en
diferentes partes del cuerpo, o cuando la condición de
salida no esta al comienzo del bucle.
Sin embargo, conocer la instrucción iterativa que mas
conviene para un algoritmo es solo el comienzo de la
construcción de la instrucción. Es conveniente
tener algunas guías para el diseño
de algoritmos iterativos.
El diseño de un algoritmo iterativo se hace sobre una base
distinta de la de uno recursivo. En los algoritmos imperativos se
tiene disponible toda la información del problema en las variables.
Por esta razón, es útil partir los datos del
problema en dos:
- La parte que representa el problema aun no
resuelto. - La parte que representa el problema ya resuelto; es
decir, el resultado ya calculado.
Una vez que se han distinguido estas dos partes, el
bucle se construye a partir de tres decisiones hechas sobre dicha
partición:
- Fijar la situación inicial. El problema a
resolver se encuentra en los parámetros de entrada o de
entrada/salida; si estos datos quieren modificarse durante el
algoritmo, deben copiarse en variables auxiliares.
también hay que dar un valor inicial a las variables que
representan la solución vacía. - Formar el cuerpo del bucle. Para ello puede usarse un
razonamiento parecido al recursivo. Se supone, por generalidad,
que la iteración se encuentra en un estado intermedio.
Debe entonces determinarse que hacer en una iteración
para avanzar en la resolución del problema. - Determinar la condición de terminación.
Corresponde a la situación en que se ha hallado la
solución completa. Esta parte esta totalmente
relacionada con la elección de la instrucción
iterativa. Según la forma de la iteración, se
elige un bucle FOR, WHILE o LOOP, como se describió
antes.
Normalmente, la terminación del bucle puede
especificarse de forma sencilla, incluso en casos relativamente
complicados. Por ejemplo, cuando se tiene un bucle WHILE con una
condición compuesta es posible que pueda usarse la
técnica del centinela para obtener una
especificación más sencilla.
Algo con lo que hay que tener especial cuidado es la
terminación de los bucles. Esta es fácil de
determinar en un algoritmo recursivo porque basta con tomar una
medida de los parámetros y comprobar que disminuye en cada
llamada recursiva, de forma que se acerca al tamaño de los
casos básicos. En una solución iterativa se razona
igual, pero la tarea es algo mas complicada porque el control del
proceso repetitivo no tiene parámetros, sino que se hace a
partir de la información contenida en las
variables.
8. Análisis Foda
Introducción:
El análisis
FODA es una herramienta que permite conformar un cuadro de la
situación actual de la empresa u
organización, permitiendo de esta manera
obtener un diagnóstico preciso que permita en
función de ello tomar decisiones acordes con los objetivos y
políticas formulados.
El término FODA es una sigla
conformada por las primeras letras de las palabras Fortalezas,
Oportunidades, Debilidades y Amenazas (en inglés
SWOT: Strenghts, Weaknesses, Oportunities, Threats). De entre
estas cuatro variables, tanto fortalezas como debilidades son
internas de la
organización, por lo que es posible actuar
directamente sobre ellas. En cambio las oportunidades y las
amenazas son externas, por lo que en general resulta muy
difícil poder
modificarlas.
- Fortalezas: son las capacidades especiales con que
cuenta la empresa, y por
los que cuenta con una posición privilegiada frente a la
competencia.
Recursos que se
controlan, capacidades y habilidades que se poseen, actividades
que se desarrollan positivamente, etc. - Oportunidades: son aquellos factores que resultan
positivos, favorables, explotables, que se deben descubrir en
el entorno en el que actúa la empresa, y
que permiten obtener ventajas competitivas. - Debilidades: son aquellos factores que provocan una
posición desfavorable frente a la competencia.
recursos de los
que se carece, habilidades que no se poseen, actividades que no
se desarrollan positivamente, etc. - Amenazas: son aquellas situaciones que provienen del
entorno y que pueden llegar a atentar incluso contra la
permanencia de la
organización.
Análisis:
El Análisis
FODA es un concepto muy
simple y claro, pero detrás de su simpleza residen
conceptos fundamentales de la
Administración. Intentaré desguazar el FODA para exponer
sus partes fundamentales.
Tenemos un objetivo:
convertir los datos del universo
(según lo percibimos) en información, procesada y
lista para la toma de
decisiones (estratégicas en este caso). En
términos de sistemas, tenemos
un conjunto inicial de datos (universo a
analizar), un proceso (análisis FODA) y un producto, que
es la información para la toma de
decisiones (el informe FODA que
resulta del análisis FODA).
Sostengo que casi cualquier persona puede
hacer un análisis FODA. Digo casi porque esa persona tiene que
tener la capacidad de distinguir en un sistema:
- Lo relevante de lo irrelevante
- Lo externo de lo interno
- Lo bueno de lo malo
Parece fácil, ¿verdad?
Pongámoslo en otras palabras: el FODA nos va a ayudar a
analizar nuestra empresa siempre y
cuando podamos responder tres preguntas: Lo que estoy analizando,
¿es relevante? ¿Está fuera o dentro de la
empresa? ¿Es bueno o malo para mi empresa?
Estas tres preguntas no son otra cosa que los tres subprocesos
que se ven en el proceso central del dibujo de
arriba. Pasemos a explicar:
La relevancia es el primer proceso y funciona como filtro: no
todo merece ser elevado a componente del análisis
estratégico. Es sentido común ya que en todos los
órdenes de la vida es fundamental distinguir lo relevante
de lo irrelevante. En FODA este filtro reduce nuestro universo de
análisis disminuyendo nuestra necesidad de procesamiento
(que no es poca cosa).
Ejemplos: dudosamente sea una ventaja comparativa el sistema de
limpieza de baños de una petroquímica, o el color de los
monitores, o
si el papel que se
usa es carta o A4.
Parece tonto, pero es increíble la cantidad de veces que a
los seres humanos nos cuesta distinguir lo principal de lo
accesorio, ya sea en una discusión, una decisión o
donde sea.
Claro que la relevancia de algo depende de dónde estemos
parados, y este concepto de
relatividad es importante. La higiene de los
baños puede ser clave en un Hospital o un Hotel. El orden
en el que se hacen los pasos al efectuar una compraventa no es
tan importante como los pasos que toman los bomberos para apagar
un incendio. La disciplina y
la autoridad
formal son dejadas de lado en muchas empresas de la
"Nueva Economía"… pero a un ejército en
batalla eso puede costarle la vida. Es por eso que quien hace un
análisis FODA debe conocer el negocio (ni más ni
menos que saber de lo que está hablando).
Filtrados los datos sólo nos queda clasificarlos.
Aplicando el sentido común, podemos construir una matriz con dos
dimensiones (dentro/fuera, bueno/malo):
Positivas | Negativas | |
Exterior | Oportunidades | Amenazas |
Interior | Fortalezas | Debilidades |
Quien haya inventado el Análisis FODA
eligió para cada intersección una palabra:
así la intersección de "bueno" y "exterior" es una
oportunidad, mientras que las cuestiones "positivas" del
"interior" de nuestra empresa son una fortaleza, y así
sucesivamente.
Distinguir entre el adentro y el afuera de la empresa a veces no
es tan fácil como parece. Es fácil decir que desde
el punto de vista de la Ferrari, M. Schumager es una fortaleza
(interna), y que si M. Hakkinen se queda sin empleo en su
escudería, será una Oportunidad (externa) para la
Ferrari. Pero el control de un recurso escaso (petróleo)
o un proveedor exclusivo están físicamente fuera de
mi empresa… y sin embargo son Fortalezas. La clave está
en adoptar una visión de sistemas y saber distinguir los
límites
del mismo. Para esto hay que tener en cuenta, no la
disposición física de los
factores, sino el control que yo tenga sobre ellos. Recordando
una vieja definición de límite: lo que me afecta y
controlo, es interno al sistema. Lo que me afecta pero
está fuera de mi control, es ambiente
(externo).
Sólo nos queda la dimensión positivo/negativo, que
aparentemente no debería ofrecer dificultad, pero hay que
tener cuidado. El competitivo ambiente de
los negocios
está lleno de maniobras, engaños, etc. En la Segunda Guerra
Mundial, el Eje estaba feliz de que el desembarco de los
Aliados fuera en Calais, porque tenía muchas fortalezas en
ese caso. Pero el día D fue en Normandía y por eso
hoy el mundo es lo que es.
Las circunstancias pueden cambiar de un día para el otro
también en el interior de la empresa: la Fortaleza de
tener a ese joven y sagaz empleado puede convertirse en grave
Debilidad si se marcha (y peor si se va con la competencia). Y la
Debilidad de tener a un empleado próximo a jubilarse y a
quien le cuesta adaptarse a las nuevas
tecnologías puede revelarse como Fortaleza demasiado
tarde… cuando se retira y nos damos cuenta de que
dependíamos de él porque era el único que
sabía "dónde estaba todo" y "cómo se hacen
las cosas".
La sagacidad del empresario debe convertir las Amenazas en
Oportunidades y las Debilidades en Fortalezas. Ejemplos:
Asociarnos con nuestra competencia de toda la vida para enfrentar
a un enemigo más pesado; pasar a un empleado
desestructurado y extrovertido de una tarea organizativa que hace
mal, a la línea de fuego de atención al público. Las
posibilidades son muchas.
Y esos son los tres pasos necesarios para analizar la
situación actual de la organización mediante el Análisis
FODA.
El Análisis FODA de este trabajo:
Fortaleza:
Los conceptos que se nos encomendaron investigar, están
desarrollados de forma amplia y lógica.
Tiene un contenido y una presentación al nivel de los que
significa ser estudiante universitario de un 7mo cuatrimestre de
Ing. En Sistemas.
Continuidad y constancia de la estructura,
calidad y
cantidad de contenido que los demás trabajos entregados, a
demás de mejoras considerables, lo cual nos garantiza
obtener calificaciones similares o superiores a las ya
obtenidazas de referidos trabajos.
Oportunidades:
Debido a las mejoras realizadas al mismo y una mejor coordinación y participación de los
integrantes del grupo este se concluirá en menor tiempo y
así podremos completar el procedimiento correcto de
entrega de trabajos de esta materia.
Debilidades:
A causa de la dificultad para conseguir la información
solicitada algunos de los conceptos relacionados con los problemas,
tipos, etc. No se encuentran en nuestro trabajo.
Amenazas:
Que las debilites de nuestro trabajo influyan considerablemente
en la evaluación del mismo provocando que las expectativas
y el esfuerzo realizados por los que participamos en el mismo no
lleguen a cumplirse.
Luego de realizar este trabajo hemos visto como los
algoritmos son una de las herramientas
más complejas y aplicables en el área de la
informática y el mundo de los
computadores.
Pudimos comprobar que mientras más potente, completo y
eficiente es el computador o
la aplicación que corre sobre el mismo mas grande,
complejo y exacto es el algoritmo que utiliza.
Las técnicas
de desarrollo de
algoritmos nos permiten encontrar la mejor solucion a los
problemas que se nos presentan y deben ser solucionados por el
computador,
estas técnicas están orientadas para utilizarse en
cada uno de los niveles de complejidad y variedad o alternativas
para las cuales se aplican los algoritmos.
Un algoritmo es el conjunto de operaciones y
procedimientos
que deben seguirse para resolver un problema, es por ellos que
debemos estudiarlos y conocerlos.
Correa Uribe, Guillermo. "Desarrollo de
Algoritmos y sus aplicaciones", Editora MacGraw – Hill Inc. USA,
III Edición. Abril/1992, Colombia. pp.
251.
Gálvez, Javier. Gonzáles, Juan.
"Algorítmica, Análisis y Diseño de
Algoritmos", Editora RA-MA (Addison-Wesley Iberiamericana), II
Edición. Septiembre/1993, USA. pp 502.
Matías, Cristian "Manual de
Informática Educativa", Editora Taller.
2da. Edición. Julio/1999. Sto. Dgo. R.D. pp 260.
Sean, James A. "Análisis y
Diseño de Sistemas de Información", Editora
MacGraw – Hill Inc. USA, 2 ta. Edición. Diciembre/1998,
México. pp
941.
World Wide Wed:
www.altavista.com
www.elrincondelvago.com
www.aulaclick.com
Autor:
Ing. Domingo de los Santos.
Ingeniero en Sistemas.
 Página anterior | Volver al principio del trabajo | Página siguiente  |