TEORÍA BÁSICA DE ALGORITMOS

ALGORITMOS Y DIAGRAMAS

lAlgoritmos y Programas

lObjetivos

lAl terminar este tema deberás ser capaz de:

–Definir qué es un algoritmo.

–Describir las características que debe cumplir un algoritmo.

–Representar un algoritmo.

–Definir qué es un programa.

–Describir las propiedades del lenguaje C.

lContenidos 

1.Introducción

2.Concepto de algoritmo

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

lIntroducción 

lUn ordenador es un sistema para procesar información

lIntroducción

lCiclo de vida del software

lContenidos 

1.Introducción

2.Concepto de algoritmo

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

lConcepto de algoritmo 

lAlgoritmo (según el DRAE):
(del árabe al-Khowârizmî) “Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema”

–Ejemplos sencillos de algoritmos según esta definición podrían ser una receta de cocina o las instrucciones para armar una bicicleta.

lConcepto de algoritmo  

lBreve reseña histórica:

–Los primeros algoritmos registrados datan de Babilonia, originados en las matemáticas como un método para resolver un problema usando una secuencia de cálculos más simples.

–El primer algoritmo famoso es el cálculo del MCD de dos números (Grecia, aproximadamente del s. IV a. C.).

lConcepto de algoritmo  

lEn Informática:

–Un algoritmo es una secuencia de pasos a seguir para resolver un problema usando un computador u ordenador.

–La algoritmia o ciencia de los algoritmos, es uno de los pilares de la informática.

lConcepto de algoritmo  

lDefiniciones básicas:

–Procesador: cualquier entidad capaz de resolver un problema

–Entorno: conjunto de utensilios que el procesador puede utilizar

–Estado: situación en la que se encuentra un entorno en un momento dado.

lConcepto de algoritmo  

lDefiniciones básicas

–Acción:
Conjunto finito de operaciones que permiten llegar de un estado inicial bien definido a otro también bien definido.

–Tipos de acciones:

lAcción primitiva o elemental

–Puede ser realizada directamente por el procesador.

lAcción compuesta o abstracta

–Ha de descomponerse en acciones más elementales para poder ser entendida por un procesador.

lConcepto de algoritmo

lDefinición formal de algoritmo:
“Dado un procesador, un entorno, y un problema bien definido, un algoritmo es la secuencia finita de acciones primitivas que llevan a la solución del problema”

lConcepto de algoritmo 

lCaracterísticas de un algoritmo:

–Preciso (no ambiguo): la instrucción a ejecutar en cada paso queda determinada perfectamente.

–Determinista: debe comportarse del mismo modo ante las mismas condiciones. Si se sigue dos veces en el mismo entorno, el resultado obtenido es el mismo.

–Finito: Tiene fin tras un número determinado de pasos.

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

lLenguajes
de representación algorítmica

l¿Cómo se escribe un algoritmo?

Representándolo mediante un lenguaje à

lenguaje de representación algorítmica

lDos tipos de representación:

–Pseudocódigo

–Diagramas de flujo

lRepresentación algorítmica  

lPseudocódigo:

–Lenguaje similar al natural, pero al que se añaden reglas para conseguir una definición precisa del algoritmo

–Algunas reglas:

lEmpieza por la palabra “Inicio” y termina con la palabra “Fin”

lSe escribe una acción por línea

lSe subrayan las palabras clave

lRepresentación algorítmica  

lDiagrama de Flujo (DF):

–Representación gráfica del flujo de control de un algoritmo

–Elementos del (DF):

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

lEjemplos de algoritmo  

lHay que tener en cuenta que para resolver un determinado problema existe más de un algoritmo

–Todos encuentran la solución correcta…

    pero unos lo hacen mejor que otros.

lEjemplos de algoritmo

Multiplicar 981 por 1234

–Varias formas (algoritmos) de hacerlo:

lMétodo clásico

lMultiplicación “à la russe”

lDivide y vencerás

–Con todas se alcanza la solución

l¿Cuál es la mejor?  ¿Por qué?

lEjemplos de algoritmo

lMétodo tradicional

     981

  * 1234

    3924

   2943

  1962

  981

 1210554

lEjemplos de algoritmo

Método tradicional

          Pero en UK…

     981       981

  * 1234    * 1234

    3924    981

   2943           1962

  1962     2943

  981      3924

 1210554  1210554

lEjemplos de algoritmo

lMultiplicación “à la russe”

–Se escriben el multiplicando y el multiplicador iniciando dos columnas.

–Se obtienen los siguientes elementos de las columnas, hasta que quede un 1 en la columna de la izquierda:

lLa columna de la izquierda se va dividiendo entre dos, ignorando los restos.

lLa columna de la derecha se va multiplicando por dos.

–El resultado se obtiene sumando los números de la columna de la derecha cuyo número correspondiente  de la columna  izquierda sea impar.

–Sólo es necesario saber sumar, multiplicar por 2 y dividir entre 2.  Se encuentra en el hardware de las ALU’s.

lEjemplos de algoritmo

lMultiplicación “à la russe”

    981    1234

    490    2468

    245    4936

    122    9872

     61  19744

     30  39488

     15  78976

      7  157952

      3  315904

      1  631808

lEjemplos de algoritmo

lMultiplicación “à la russe”

    981    1234

    490 

    245    4936

    122 

     61  19744

     30 

     15  78976

      7  157952

      3  315904

      1  631808

lEjemplos de algoritmo

lDivide y vencerás

–Números con precisión par

–Se dividen por la mitad ambos operandos

–Se realizan las 4 multiplicaciones cruzadas

–Se suman los resultados desplazando previamente hacia la izquierda

–Algoritmo recursivo

lEjemplos de algoritmo

lDivide y vencerás

 

  0981   

  1234

lEjemplos de algoritmo 

lEjercicio:

–¿Cuál es mejor y por qué?

–¿Qué criterios podemos utilizar para valorar un algoritmo?

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

●

lProgramas

lPrograma: Algoritmo codificado en un lenguaje de programación.

lProgramar:  Fraccionar un problema en forma de instrucciones adecuadamente formuladas para que un ordenador pueda llevarlas a la práctica.

l

lProgramas

lLas instrucciones se forman con elementos o símbolos tomados de un determinado repertorio, y se construyen siguiendo unas reglas precisas.

lTodo lo relativo a los símbolos y reglas para construir o redactar con ellos un programa se denomina lenguaje de programación.

l

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

●

lLenguajes de programación
Clasificación

lLenguaje máquina:

–Es el que entienden los circuitos del computador (CPU)

–Inconvenientes:

ldepende del modelo de computadora;

lel repertorio de instrucciones es muy reducido

les muy laborioso

lEnsamblador (lenguaje de bajo nivel)

–Código nemotécnico para recordar mejor las instrucciones máquina

–Se mantienen los otros inconvenientes del lenguaje máquina

lLenguajes de alto nivel

–No dependen de la computadora, y facilitan la tarea de programación

lLenguajes de programación
Lenguajes de alto nivel

l

lFORTRAN (Formula Translation): Primer LAN(década de los 50). Aplicaciones científico-técnicas (grandes computadores y supercomputadores)

lCOBOL (COmmon Busines Oriented Language): 1960. Aplicaciones comerciales y de gestión.

lBASIC (Beginner’s All-purpose Symbolic Instruction Code). Desarrollado a mediados de los 60 como lenguaje interactivo paraprincipiantes de programación.

lVisual BASIC: es el lenguaje más popular. Versión de Microsoft del BASIC. Permite crear programas en un ambiente visual (lenguaje de 4ª generación).

lC: Desarrollado en Bell Labs a comienzos de los 70. Es complejo, pero es potente, flexible y eficiente (el más utilizado para PCs y estaciones de trabajo).

lLenguajes de programación
Lenguajes de alto nivel

lPascal: Creado por Wirth en 1971. El mejor lenguaje para aprender a programar y describir algoritmos.

lAda: Es un lenguaje definido por el Ministerio de Defensa de USA a finales de los 70. Esta basado en el Pascal y tiene unas reglas muy estrictas.

lC++: Ideado a comienzos de los 80 en los BellLabs. Es una variante del C que permite utilizar la moderna metodología de la programación (“programación orientada a objetos”)

lJava: Desarrollado en 1991 por Sun, es similar a C++ pero más sencillo de aprender y usar. Muy usado para programa interactivos y dinámicos (“applets” de web). Se ha definido un computador virtual Java compatible, cualquier computador con un programa que lo emule puede ejecutar aplicaciones Java.

lLenguajes de programación
Lenguajes de alto nivel

lOtros lenguajes (usados en Inteligencia artificial):

–LISP (LISt Processing): Finales de los 50. Procesamiento de datos no numéricos (caracteres, palabras y otros símbolos). Se usa en Inteligencia Artificial.

–PROLOG:(Programming Logic): Trabaja con relaciones lógicas entre hechos. Muy usado en inteligencia artificial.

–LOGO: versión simplificada del LISP para niños.

lLenguajes de programación
Traductores

lTraducción: Proceso por el cual se convierte el texto del programa de entrada en el de salida.

–Lenguaje fuente: lenguaje en el que se escribe la entrada

–Lenguaje objeto: lenguaje en el que se escribe la salida. En general, muy diferente del lenguaje fuente

lCompilador: Programa que acepta como entrada un texto de programa escrito en un cierto lenguaje de alto nivel y genera como salida texto de programa en otro lenguaje, generalmente lenguaje máquina.

l

lLenguajes de programación
Compiladores

lCompilar ≈ Convertir de un formato a otro

–El significado deberá permanecer inalterado en la conversión

–La entrada está escrita en un lenguaje ® Tiene estructura

–Semántica asociada y descrita en términos de esa estructura

l

lEl compilador “comprende” el programa y recolecta su significado en una representación semántica intermedia

l

lA la hora de generar la salida ® se genera estructura y significado

lLenguajes de programación Intérpretes

lForma de trabajar cada vez más frecuente: Intérpretes

–En vez de traducir, realiza las acciones directamente

–Por ejemplo, la máquina virtual de Java

lVentajas del uso de intérpretes

–Portabilidad: Un intérprete se escribe, habitualmente, en lenguaje de alto nivel

–Sencillez: Escribir un intérprete es menos costoso que escribir un compilador

–Señalización y manejo de errores: los compiladores cuidan “demasiado” la eficiencia de código

–Seguridad: Funcionamiento más transparente al usuario

lDesventajas: Velocidad de los programas interpretados y consumo de memoria.

lLenguajes de programación
Compiladores vs. Intérpretes

lCompiladores:

–El procesamiento del programa es considerable

–El mecanismo de interpretación previsto es la CPU (hw)

–La ejecución del programa traducido es relativamente rápida

l

lIntérpretes:

–El procesamiento del programa es entre mínimo y moderado

–El mecanismo de interpretación es un programa (sw)

–La ejecución del programa es, en general, más lenta y más segura

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

●

l

lContenidos 

1.Introducción

2.Definiciones básicas

3.Lenguajes de representación algorítmica

4.Ejemplos de algoritmo

5.Programas

6.Lenguajes de programación

7.El proceso de programación

8.Introducción al lenguaje C

●

l
Lenguaje C

lEs un lenguaje estructurado de propósito general, orientado a la programación de sistemas

–Origen:

lEvolución de BSPL y B

l“The C programming language”, B. Kernighan & D. Ritchie.  (1978)

–ANSI C:

lVersión estándar en 1983

lNueva revisión en 1999

–Uno de los lenguajes más utilizados en la industria del software actual y en el mundo Unix/Linux

l
Lenguaje C

lCaracterísticas de C

–Propósito general

lVálido para diversos objetivos

–Portable

lNOTA: Sin embargo, siempre hay que compilar y probar un programa en el ordenador “destino”

–Eficiente

lApropiado para la programación de sistemas

–Extendido.

lGran cantidad de bibliotecas de funciones, compiladores, etc.

lAmplia difusión y uso.

lBibliografía 

lJoyanes Aguilar, L. “Fundamentos de programación. Algoritmos y Estructura de Datos”, McGrawHill. Capítulo 2.

lLlanos Ferraris, D. “Curso de C bajo UNIX”. Capítulo 1.

Dirección de ejemplos de aplicaron de algoritmos
http://www.profmatiasgarcia.com.ar/uploads/tutoriales/Ej_resueltos_algoritmos.pdf