HISTORIA


La palabra algoritmo proviene del nombre del matemático llamado Muhammad ibn Musa al-Jwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal logro no fuera el de crear nuevos teoremas o corrientes de pensamiento, sino el de simplificar la matemática a punto tal que pudieran ser comprendidas y aplicadas por un mayor número de personas. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aún no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.
Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.

DEFINICIÓN


En matemáticas, ciencias de la computación, y disciplinas relacionadas, un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de la algoritmia, y su definición queda formalizada por el modelo computacional de la Máquina de Turing.

CARACTERÍSTICAS DE LOS ALGORITMOS

El científico de computación Donald Knuth ofreció una lista de cinco propiedades, que son ampliamente aceptadas como requisitos para un algoritmo:

  • Carácter finito. "Un algoritmo siempre debe terminar después de un número finito de pasos".
  • Precisión. "Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso".
  • Entrada. "Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos".
  • Salida. "Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas".
  • Eficacia. "También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel".

Knuth admite que, aunque su descripción pueda ser intuitivamente clara, carece de rigor formal, puesto que no está exactamente claro qué significa "precisamente definido", "de manera rigurosa y no ambigua", o "suficientemente básicas", y así sucesivamente.
A partir del caracter finito y de la salida se deduce que ante una misma situación inicial (o valores de entrada) un algoritmo debe proporcionar siempre el mismo resultado (o salida), con excepción de los algoritmos probabilistas.

MEDIOS DE EXPRESIÓN DE UN ALGORITMO

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

La descripción de un algoritmo usualmente se hace en tres niveles:
  1. Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
  2. Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
  3. Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.

También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos.

Estructura Básica de un Algoritmo:

  • inicio
  • datos de entrada (operaciones básicas)
  • procesamiento de los datos
  • datos de salida
  • fin

Pseudocódigo

Un pseudocódigo (falso lenguaje), es una serie de normas léxicas y gramaticales parecidas a la mayoría de los lenguajes de programación, pero sin llegar a la rigidez de sintaxis de estos ni a la fluidez del lenguaje coloquial. Esto permite codificar un programa con mayor agilidad que en cualquier lenguaje de programación, con la misma validez semántica, normalmente se utiliza en las fases de análisis o diseño de Software, o en el estudio de un algoritmo. Forma parte de las distintas herramientas de la ingeniería de software.
No hay ningún compilador o intérprete de pseudocódigo informático (en el caso de que lo hubiera serían los lectores de dicho pseudocódigo informatico, por ej. una idea de un jefe de programación a el staff de programadores), y por tanto no puede ser ejecutado en un ordenador, pero las similitudes con la mayoría de los lenguajes informáticos lo hacen fácilmente convertible.
El pseudocódigo describe un algoritmo utilizando una mezcla de frases en lenguaje común, instrucciones de programación y palabras clave que definen las estructuras básicas. Su objetivo es permitir que el programador se centre en los aspectos lógicos de la solución a un problema.
No siendo el pseudocódigo un lenguaje formal, varían de un programador a otro, es decir, no hay una estructura semántica ni arquitectura estándar. Es una herramienta ágil para el estudio y diseño de aplicaciones, veamos un ejemplo, que podríamos definir como: lenguaje imperativo, de tercera generación, según el método de programación estructurada.

Diagrama de flujo

El diagrama de flujo representa la forma más tradicional y duradera para especificar los detalles algorítmicos de un proceso. Se utiliza principalmente en programación, economía y procesos industriales; estos diagramas utilizan una serie de símbolos con significados especiales. Son la representación gráfica de los pasos de un proceso, que se realiza para entender mejor al mismo.
Son modelos tecnológicos utilizados para comprender los rudimentos de la programación lineal.
Otra definición del diagrama de flujo es la siguiente:

"Es un esquema para representar gráficamente un algoritmo Se basan en la utilización de diversos símbolos para representar operaciones específicas. Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. Para hacer comprensibles los diagramas a todas las personas, los símbolos se someten a una normalización; es decir, se hicieron símbolos casi universales, ya que, en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de flujo. Esto trajo como consecuencia que sólo aquel que conocía sus símbolos, los podía interpretar. La simbología utilizada para la elaboración de diagramas de flujo es variable y debe ajustarse a un patrón definido previamente."


Símbolos de Diagramas de Flujo


Los símbolos tienen significados específicos y se conectan por medio de flechas que indican el flujo entre los distintos pasos o etapas:

ANALISIS DE ALGORITMOS

Como medida de la eficiencia de un algoritmo, se suelen estudiar los recursos (memoria y tiempo) que consume el algoritmo. El análisis de algoritmos se ha desarrollado para obtener valores que de alguna forma indiquen (o especifiquen) la evolución del gasto de tiempo y memoria en función del tamaño de los valores de entrada.
El análisis y estudio de los algoritmos es una disciplina de las ciencias de la computación y, en la mayoría de los casos, su estudio es completamente abstracto sin usar ningún tipo de lenguaje de programación ni cualquier otra implementación; por eso, en ese sentido, comparte las características de las disciplinas matemáticas. Así, el análisis de los algoritmos se centra en los principios básicos del algoritmo, no en los de la implementación particular. Una forma de plasmar (o algunas veces "codificar") un algoritmo es escribirlo en pseudocódigo o utilizar un lenguaje muy simple tal como Léxico, cuyos códigos pueden estar en el idioma del programador.
Algunos escritores restringen la definición de algoritmo a procedimientos que deben acabar en algún momento, mientras que otros consideran procedimientos que podrían ejecutarse eternamente sin pararse, suponiendo el caso en el que existiera algún dispositivo físico que fuera capaz de funcionar eternamente. En este último caso, la finalización con éxito del algoritmo no se podría definir como la terminación de éste con una salida satisfactoria, sino que el éxito estaría definido en función de las secuencias de salidas dadas durante un periodo de vida de la ejecución del algoritmo. Por ejemplo, un algoritmo que verifica que hay más ceros que unos en una secuencia binaria infinita debe ejecutarse siempre para que pueda devolver un valor útil. Si se implementa correctamente, el valor devuelto por el algoritmo será válido, hasta que evalúe el siguiente dígito binario. De esta forma, mientras evalúa la siguiente secuencia podrán leerse dos tipos de señales: una señal positiva (en el caso de que el número de ceros sea mayor que el de unos) y una negativa en caso contrario. Finalmente, la salida de este algoritmo se define como la devolución de valores exclusivamente positivos si hay más ceros que unos en la secuencia y, en cualquier otro caso, devolverá una mezcla de señales positivas y negativas.

PROGRAMA A UTILIZAR Borland C++

Para esto, necesitamos conocer el Lenguaje C

LENGUAJE C

C es un lenguaje de programación de propósito general que ofrece economía sintáctica, control de flujo y estructuras sencillas y un buen conjunto de operadores. Es un lenguaje potente, con un campo de aplicación ilimitado y sobre todo, se aprende rápidamente. Este lenguaje ha sido estrechamente ligado al sistema operativo UNIX, puesto que fueron desarrollados conjuntamente. Sin embargo, este lenguaje no está ligado a ningún sistema operativo ni a ninguna máquina concreta. Se le suele llamar lenguaje de programación de sistemas debido a su utilidad para escribir compiladores y sistemas operativos, aunque de igual forma se pueden desarrollar cualquier tipo de aplicación. La base del C proviene del BCPL, escrito por Martin Richards, y del B escrito por Ken Thompson en 1970 para el primer sistema UNIX. Estos son lenguajes sin tipos, al contrario que el C que proporciona varios tipos de datos. El primer compilador de C fue escrito por Dennis Ritchie.

Datos







Operadores aritméticos y de Admisión

OPERADORES ARITMÉTICOS

Existen dos tipos de operadores aritméticos:
Los binarios:
+ Suma
- Resta
* Multiplicación
/ División
% Módulo (resto)
y los unarios:
++ Incremento (suma 1)
-- Decremento (resta 1)
- Cambio de signo

Su sintaxis es:
binarios:

unarios:


OPERADORES DE ASIGNACIÓN

La mayoría de los operadores aritméticos binarios tienen su correspondiente operador de asignación: = Asignación simple += Suma -= Resta *= Multiplicación /= División %= Módulo (resto) Con estos operadores se pueden escribir, de forma más breve, expresiones del tipo: n=n+3 se puede escribir n+=3 k=k*(x-2) lo podemos sustituir por k*=x-2 JERARQUÍA DE LOS OPERADORES Es importante tener en cuenta la precedencia de los operadores a la hora de trabajar con ellos: ( ) Mayor precedencia ++, -- *, /, % +, - Menor precendencia

Operadores Relacionales

Utilizados para comparar el contenido de dos variables. En C existen seis operadores relacionales básicos:
> Mayor que
< Menor que
>= Mayor o igual que
<= Menor o igual que
== Igual que
!= Distinto que

El resultado que devuelven estos operadores es 1 para Verdadero y 0 para Falso. Si hay más de un operador se evalúan de izquierda a derecha. Además los operadores == y != están por debajo del resto en cuanto al orden de precedencia.

Funciones De Entrada – Cin

cin es el comando complementario de cout. Lee lo que se introduce desde el teclado, y en este sentido es también una caja negra, pues no sabemos cómo lo hace. La sintaxis es similar a la de cout:

#include
main(){
int numero;
cout << "Introduce un número:";
cin >> numero;
}
El operador >>, llamado operador de extracción, es obviamente el opuesto de <<: toma los datos de cin y los asigna a la variable, en nuestro ejemplo numero. Ya que numero es un entero, cin convertirá la entrada en un entero, si es posible; si la entrada es "hola", por ejemplo, no debemos esperar que sea convertido a un entero.

Funciones De Salida - Cout

C++ no tiene operaciones de entrada/salida como parte del lenguaje en sí, sino que define la librería iostream.h para añadir estas funciones. La salida por pantalla se hace a través de cout, por ejemplo "Hello, mundo":

#include
main(){
cout << "Hello, mundo";
}
El operador <<, llamado operador de inserción, le dice al sistema que imprima la variable que le sigue, pero deja que el sistema decida cómo imprimir los datos. No le hemos indicado el tipo de la variable que queremos imprimir, es el sistema el que determina el tipo de la variable, y lo imprime adecuadamente. Tampoco hemos formateado la salida. De nuevo es el sistema el que determina el número de cifras, el de espacios en blanco ... Se pueden utilizar los caracteres de escape de C. Por ejemplo, en el programa anterior podemos añadir un retorno de carro:

#include
main(){
cout << "Hello\n";
cout << "mundo";
}

cout saca por pantalla cualquier tipo de dato estándar que existe en C++, bien sea un carácter, un número o movimientos especiales del cursor, como \n en el ejemplo anterior.

SESIONES DE CLASES CON C++

ESTRUCTURA SECUENCIAL

Es aquélla en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso. La estructura secuencial tiene una entrada y una salida. Su representación gráfica es la siguiente:

ESTRUCTURA SELECTIVA O CONDICIONAL

  1. IF
  2. SWITCH

Sentencia: IF

SINTAXIS: IF

if (condición es verdad)
acción1;
else
acción2;

Sentencia: IF (Multiple)

SINTAXIS: IF MULTIPLE

If (Condicion 1)
{
Else if (condicion 2)
accion 1
Else if (condicion 3)
accion 2
Else if (condicion n)
accion n
Else
{
Accion x
}

Sentencia: Switch

SINTAXIS: SWITCH

case ‘N1’:
Accion 1;
break;
case ‘N2’:
Accion 2;
break;
case ‘Nn ’:
Accion n;
break;
default:
Accion x;
}

ESTRUCTURAS DE CONTROL REPETITIVO

  1. WHILE
  2. DO…WHILE
  3. FOR( inicialización; condición; incremento)

Sentencia: While

SINTAXIS:

WHILE (CONDICION)
{
SENTENCIAS;
}

Sentencia: Do…While

SINTAXIS

DO
{
SENTENCIAS;
}
WHILE (CONDICION)

Sentencia: For

SINTAXIS:

FOR (inicialización; condición; incremento)
{
sentencias;
}

FUNCIONES

Sintaxias
void main ( )
{
Func1( );
………….
Func1( );
}

MATRICES Y VECTORES

Los vectores y matrices son pasados siempre por referencia como argumentos de una función. La única diferencia con los tipos simples es que no se usa el ‘&’ ya que basta simplemente el nombre del vector o matriz.

Ejemplo