programacion - en - c-metodologia - algoritmos - y-estructura - de - datos - editorial - mcgraw - hill

programacion - en - c-metodologia - algoritmos - y-estructura - de - datos -...

(Parte 5 de 7)

Tabla 1.2. Características de un PC ideal.

Procesador Microprocesador de las marcas Intel o AMD, de 800 Mz o superior. Memoria 128 Mb y recomendable para aplicaciones profesionales 256 o 5 12 Mb.

Caché Memoria especial que usa el procesador para acelerar sus operaciones. 5 12 Kb o 128 Kb.

Disco duro 20 Gigabytes (mínimo).

Internet Video

Preparado para Internet (incluso con módem instalado de 56 Kb). Memoria de vídeo, con un mínimo de 4 Mb.

Monitor 17” o 19” (pantalla tradicional o plana “TFT”). Almacenamiento CD-RW, DVD. Puertos Serie, paralelo y USB. Marcas HP, Compaq, Dell, IBM, El System, Futjisu, Inves, . .

Introducción a la ciencia de la computación y a la programación 15

1.3. CONCEPTO DE ALGORITMO

El objetivo fundamental de este texto es enseñar a resolver problemas mediante una computadora. El programador de computadora es antes que nada una persona que resuelve problemas, por lo que para Ile- gar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sis- temático. A lo largo de todo este libro nos referiremos a la metodología necesaria para resolver pro- blemas mediante programas, concepto que se denomina metodología de la programación. El eje central de esta metodología es el concepto, ya tratado, de algoritmo.

Un algoritmo es un método para resolver un problema. Aunque la popularización del término ha Ile- gado con el advenimiento de la era informhtica, algoritmo proviene de Mohammed al-KhoW¿irizmi, matemático persa que vivió durante el siglo IX y alcanzó gran reputación por el enunciado de las reglas paso a paso para sumar, restar, multiplicar y dividir números decimales; la traducción al latín del ape- llido en la palabra algorismus derivó posteriormente en algoritmo. Euclides, el gran matemático griego (del siglo IV a.c.) que inventó un método para encontrar el máximo común divisor de dos números, se considera con Al-Khowirizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos).

El profesor Niklaus Wirth -inventor de Pascal, Modula-2 y Oberon- tituló uno de sus más famo- sos libros, Algoritmos + Estructuras de datos = Programas, significándonos que sólo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. Esta ecua- ción será una de las hipótesis fundamentales consideradas en esta obra. La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto.

Problema Diseño del algoritmo

Programa de

computadora I I I I

Figura 1.13. Resolución de un problema.

Los pasos para la resolución de un problema son:

I. Diseño del algoritmo que describe la secuencia ordenada de pasos -sin ambigüedades- que conducen a la solución de un problema dado. (Andisis del problema y desarrollo del algorit- mo.) Expresar el algoritmo como un programa en un lenguaje de programación adecuado. (Fase de codificación.)

Ejecución y validación del programa por la computadora. 2. 3.

Para llegar a la realización de un programa es necesario el diseño previo de un algoritmo, de modo que sin algoritmo no puede existir un programa.

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje dife- rente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siem- pre el mismo. Así, por ejemplo, en una analogía con la vida diaria, una receta de un plato de cocina se puede expresar en español, inglés o francés, pero cualquiera que sea el lenguaje, los pasos para la ela- boración del plato se realizarán sin importar el idioma del cocinero.

En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan sólo un medio para expresar un algoritmo y una computadora es sólo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente.

16 Programación en C. Metodología, algoritmos y estructura de datos

Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. A la enseñanza y práctica de esta tarea se dedica gran parte de este libro. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la téc- nica de la programación. En esencia, la solución de un problema se puede expresar mediante un algo- ritmo.

1.3.1. Características de los algoritmos

Las características fundamentales que debe cumplir todo algoritmo son:

Un algoritmo debe ser preciso e indicar el orden de realización de cada paso. Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo

Un algoritmo debe ser$nito. Si se sigue un algoritmo, se debe terminar en algún momento; o sea,

La definición de un algoritmo debe describir tres partes: Entrada, Proceso y Salida. En el algorit- mo de receta de cocina citado anteriormente se tendrá:

Entrada: ingredientes y utensilios empleados. Proceso: elaboración de la receta en la cocina. Salida: terminación del plato (por ejemplo, cordero).

resultado cada vez. debe tener un número finito de pasos.

Ejemplo 1.1

Un cliente ejecuta un pedido u una fábrica. La fábrica examina en su banco de datos la ficha del clien- te, si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario, rechazará el pedi- do. Redactar el algoritmo correspondiente.

Los pasos del algoritmo son:

1. Inicio. 2. Leer el pedido. 3. Examinar la ficha del cliente. 4. Si el cliente es solvente, aceptar pedido; en caso contrario, recha

5. Fin. zar pedido.

Ejemplo 1.2

Se desea diseñar un algoritmo para saber si un número es primo o no.

algoritmo de resolución del problema pasa por dividir sucesivamente el número por 2, 3,4, etc.

Un número es primo si sólo puede dividirse por sí mismo y por la unidad (es decir, no tiene más divi- sores que él mismo y la unidad). Por ejemplo, 9,8,6,4, 12, 16,20, etc., no son primos, ya que son divi- sibles por números distintos a ellos mismos y a la unidad. Así, 9 es divisible por 3, 8 lo es por 2, etc. El

1. Inicio. 2. Poner X igual a 2 (X = 2, X variable que representa a los divisores del

3. Dividir N por X (N/X). 4. Si el resultado de N/X es entero, entonces N no es un número primo y

5. Suma 1 a X (X c X + 1).

número que se busca N). bifurcar al punto 7; en caso contrario, continuar el proceso.

Introducción a la ciencia de la computación y a la programación 17

6. Si X es igual a N, entonces N es un número primo; en caso contrario,

7. Fin. bifurcar al punto 3.

Por ejemplo, si N es 13 1, los pasos anteriores serían:

3. 131/X, etc.

1. Inicio. 2. x = 2. 3. 131/X. Como el resultado no es entero, se continúa el proceso. 5. X t 2 + 1, luego X = 3. 6. Como X no es 131, se bifurca al punto 3. 3. 131/X resultado no es entero. 5. x t 3 + 1, x = 4. 6. Como X no es 131 bifurca al punto 3. 7. Fin.

Ejemplo 1.3 Realizar la suma de todos los números pares entre 2 y 1000.

y NUMERO (variables, serán denominadas más tarde) para representar las sumas sucesivas ( 2 +4 ( 2 + 4 + 6 ) , ( 2 + 4 + 6 + 8 ) , etc. La solución se puede escribir con el siguiente algoritmo:

El problema consiste en sumar 2 + 4 + 6 + 8+ 1000 . Utilizaremos las palabras SUMA

1. Inicio. 2. Establecer SUMA a O. 3. Establecer NUMERO a 2. 4. Sumar NUMERO a SUMA. El resultado será el nuevo valor de la suma (SUMA). 5. Incrementar NUMERO en 2 unidades. 6. Si NUMERO =< 1000 bifurcar al paso 4 ; en caso contrario, escribir el

7. Fin. ultimo valor de SUMA y terminar el proceso.

1.4. EL SOFTWARE (LOS PROGRAMAS)

Las operaciones que debe realizar el hardware son especificadas por una lista de instrucciones, Ilama- das programas, o software. El software se divide en dos grandes grupos: sofnvare del sistema y softwa- re de aplicaciones.

El software del sistema es el conjunto de programas indispensables para que la máquina funcione; se denominan también programas del sistema. Estos programas son, básicamente, el sistema operativo, los editores de texto, los compiladores/intérpretes (lenguajes de programación) y los programas de utilidad.

dows 2000, UNIX, Lynux, y en casi todas las computadoras personales actuales PC, Mac, Sun, etc.

Uno de los programas más importante es el sistema operativo, que sirve, esencialmente, para faci- litar la escritura y uso de sus propios programas. El sistema operativo dirige las operaciones globales de la computadora, instruye a la computadora para ejecutar otros programas y controla el almacenamien- to y recuperación de archivos (programas y datos) de cintas y discos. Gracias al sistema operativo es posible que el programador pueda introducir y grabar nuevos programas, así como instruir a la compu- tadora para que los ejecute. Los sistemas operativos pueden ser: monousuarios (un solo usuario) y mul- tiusuarios, o tiempo compartido (diferentes usuarios), atendiendo al número de usuarios y monocarga (una sola tarea) o multitarea (múltiples tareas) según las tareas (procesos) que puede realizar simultá- neamente. C corre prácticamente en todos los sistemas operativos, Windows 95, Windows NT, Win-

Los lenguajes de programación sirven para escribir programas que permitan la comunicación usua- rio/máquina. Unos programas especiales llamados traductores (compiladores o intérpretes) convier-

18 Programación en C. Metodología, algoritmos y estructura de datos

Figura 1.14. Diferentes programas de software.

ten las instrucciones escritas en lenguajes de programación en instrucciones escritas en lenguajes máqui- na (O y 1, bits) que ésta pueda entender.

Los programas de utilidad' facilitan el uso de la computadora. Un buen ejemplo es un editor de textos que permite la escritura y edición de documentos. Este libro ha sido escrito en un editor de tex- tos o procesador de palabras («wordprocesor»).

Los programas que realizan tareas concretas, nóminas, contabilidad, análisis estadístico, etc. es decir, los programas que podrá escribir en C, se denominan programas de aplicación. A lo largo del libro se verán pequeños programas de aplicación que muestran los principios de una buena programa- ción de computadora.

Se debe diferenciar entre el acto de crear un programa y la acción de la computadora cuando ejecuta las instrucciones del programa. La creación de un programa se hace inicialmente en papel y a conti- nuación se introduce en la computadora y se convierte en lenguaje entendible por la computadora.

Figura 1.15. Relación entre programas de aplicación y programas del sistema.

Introducción a la ciencia de la computación y a la programación I1 19 I

Memoria externa - ----'

I L--_ -2 UCP Terminal externos

Datos de salida

(rociiitadocl Programador

Figura 1.16. Acción de un programador

La Figura 1.16 muestra el proceso general de ejecución de un programa: aplicación de una entrada (datos) al programa y obtención de una salida (re.sultados). La entrada puede tener una variedad de for- mas, tales como números o caracteres alfabéticos. La salida puede también tener formas, tales como datos numéricos o caracteres, señales para controlar equipos o robots, etc.

La ejecución de un programa requiere -generalmente- unos datos como entrada (Fig. 1.17), ade- más del propio programa, para poder producir una salida.

Memoria externa

'- Entrada Salida

(datos) (resultados)

Figura 1.17. Ejecución de un programa

I .5. LOS LENGUAJES DE PROGRAMACI~N

Como se ha visto en el apartado anterior, para que un procesador realice un proceso se le debe sumi- nistrar en primer lugar un algoritmo adecuado. El procesador debe ser capaz de interpretar el algoritmo, lo que significa:

Comprender las instrucciones de cada paso. Realizar las operaciones correspondientes.

Cuando el procesador es una computadora, el algoritmo se ha de expresar en un formato que se denomina programa. Un programa se escribe en un lenguaje de programación y las operaciones que conducen a expresar un algoritmo en forma de programa se llaman programación. Así pues, los len- guajes utilizados para escribir programas de computadoras son los lenguajes de programación y pro- gramadores son los escritores y diseñadores de programas.

20 Programación en C. Metodología, algoritmos y estructura de datos

Los principales tipos de lenguajes utilizados en la actualidad son tres:

Lenguajes máquina. Lenguaje de bajo nivel (ensamblador). Lenguajes de alto nivel.

1.5.1. Instrucciones a la computadora

Los diferentes pasos (acciones) de un algoritmo se expresan en los programas como instrucciones, sen- tencias o proposiciones (normalmente el término instrucción se suele referir a los lenguajes máquina y bajo nivel, reservando la sentencia o proposición para los lenguajes de alto nivel). Por consiguiente, un programa consta de una secuencia de instrucciones, cada una de las cuales especifica ciertas operacio- nes que debe ejecutar la computadora.

La elaboración de un programa requerirá conocer el juego o repertorio de instrucciones del lengua- je. Aunque en el Capítulo 3 se analizarán con más detalle las instrucciones, adelantaremos los tipos fun- damentales de instrucciones que una computadora es capaz de manipular y ejecutar. Las instrucciones básicas y comunes a casi todos los lenguajes de programación se pueden condensar en cuatro grupos:

Instrucciones de enrraúdsalidu. Instrucciones de transferencia de información y datos entre dis-

lnstrucciones aritmético-lógicas. Instrucciones que ejecutan operaciones aritméticas (suma, res- Instrucciones selectivas. Instrucciones que permiten la selección de tareas alternativas en función 0 Instrucciones repetitivas. Instrucciones que permiten la repetición de secuencias de instruccio- positivos periféricos (teclado, impresora, unidad de disco, etc.) y la memoria central. ta, multiplicación, división, potenciación), lógicas (operaciones and, or, not, etc.). de los resultados de diferentes expresiones condicionales. nes un número determinado de veces.

1.5.2. Lenguajes máquina

Los lenguajes máquina son aquellos que están escritos en lenguajes directamente inteligibles por la máquina (computadora), ya que sus instrucciones son cadenas binarias (cadenas o series de caracteres -dígitos- O y 1) que especifican una operación, y las posiciones (dirección) de memoria implicadas en la operación se denominan instrucciones de máquina o código máquina. El código máquina es el conocido código binario.

Las instrucciones en lenguaje máquina dependen del hardware de la computadora y, por tanto, dife- rirán de una computadora a otra. El lenguaje máquina de un PC (computadora personal) será diferente de un sistema HP (Hewlett Packard), Compaq o un sistema de IBM.

Las ventajas de programar en lenguaje máquina son la posibilidad de cargar (transferir un progra- ma a la memoria) sin necesidad de traducción posterior, lo que supone una velocidad de ejecución supe- rior a cualquier otro lenguaje de programación.

Los inconvenientes -en la actualidad- superan a las ventajas, lo que hace prácticamente no reco- mendables los lenguajes máquina. Estos inconvenientes son:

Dificultad y lentitud en la codificación. Poca fiabilidad. Dificultad grande de verificar y poner a punto los programas. Los programas sólo son ejecutables en el mismo procesador (UPC, ünidad Central de Proceso).

(Parte 5 de 7)

Comentários