Algoritmos (panorama general).

   La resolución de un problema mediante una computadora, se refiere al proceso que consiste en partir de la descripción de un problema y desarrollar un programa de computadora que resuelva dicho problema. Cabe mencionar que el problema está expresado, habitualmente, en lenguaje natural y en los términos propios del dominio del problema, lo cual conlleva sus propias complicaciones independientemente de la complejidad de éste. El proceso involucrado en la solución considera, grosso modo, las siguientes etapas:

1. Comprensión del problema.
2. Análisis del problema.
3. Diseño o desarrollo de un algoritmo.
4. Transformación del algoritmo en un programa (codificación).
5. Ejecución y validación del programa.

   Aunque cada una de las etapas es de significativa importancia, la experiencia indica que las tres primeras de ellas son en las que el estudiante presenta mayor dificultad.

   En este sentido, el orden en el que se presentan dichas etapas no es aleatorio, ya que cada una de ellas supone la adecuada terminación de la anterior; así por ejemplo, sería imposible tratar de analizar un problema que ni siquiera se ha comprendido en su contexto más general, y ni qué decir entonces de la elaboración de un algoritmo.

   Probablemente la etapa más sencilla de las cinco sea la número cuatro: la codificación; ya que una vez que el problema se ha comprendido, analizado, y obtenido un algoritmo que lo resuelve, su transformación a un programa de computadora es una tarea de simple traducción, que si bien requiere del conocimiento de la sintaxis del lenguaje elegido para ello, la parte intelectual y de raciocinio queda plasmada en el algoritmo.

   La meta de la programación estructurada es la de hacer programas que sean fáciles de diseñar, depurar (analizar), y susceptibles de ser entendidos por personas diferentes a las que escribieron el programa [Ullman]. No se trata de escribir programas que solamente su creador entienda, se trata de algo más que eso.

   Ahora bien, un programa puede ser visto como un sistema en el que sus componentes son programas más pequeños, y a su vez estos componentes pueden ser vistos como otros, compuestos por similares todavía más pequeños y así sucesivamente hasta un nivel granular razonable, en donde los componentes finales están compuestos de unas cuantas sentencias de código. Los programas escritos siguiendo este diseño se denominan programas estructurados [Jeffrey Ullman].

   En un programa estructurado, el flujo lógico de ejecución se gobierna por tres estructuras de control:

1. Estructura secuencial.
2. Estructuras de selección.
3. Estructuras de repetición.

Teorema de Böhm y Jacopini.

   El teorema de Böhm y Jacopini establece que un programa propio puede ser escrito utilizando únicamente tres tipos de estructuras de control: estructura secuencial, estructuras de selección y estructuras de repetición.

   Para que un programa sea estructurado el programa debe ser propio, y un programa se define como propio si cumple las siguientes condiciones:

• Tiene un único punto de entrada, y un único punto de salida.
• Todas las sentencias del algoritmo son alcanzables, y existe al menos un camino que va desde el inicio hasta el fin del algoritmo.
• No tiene ciclos infinitos.

   De lo anterior se deduce que, si los algoritmos se diseñan empleando las estructuras de control anteriormente mencionadas, los algoritmos, y en consecuencia los programas derivados de ellos, serán propios siempre y cuando se cumplan también las tres condiciones antes mencionadas.

Estructuras de Control.
   Las estructuras secuencial, de selección y de repetición se denominan estructuras de control porque son las que controlan el modo o flujo de ejecución del algoritmo. Su importancia es tal que, una vez que se comprendan, se podrá tener el control respecto al flujo de ejecución de los algoritmos.

   Estructura secuencial.

   La estructura secuencial es las más simple de las tres, y se caracteriza porque una acción o sentencia se ejecuta detrás de otra; es decir, el flujo del algoritmo coincide con el orden físico en el que se han colocado las sentencias en el algoritmo.

   Estructuras de selección.

   Este tipo de estructuras realizan una selección de las acciones o sentencias a ejecutar. La selección de qué sentencias se procesarán está en directa función o dependencia de una condición.

   La condición puede ser tan elaborada como la naturaleza del problema lo requiera, pero se deberá asegurar de que dicha condición pueda ser evaluada de manera booleana, esto es, como verdadera o falsa: sin ambigüedad (la ambigüedad viola una de las cinco condiciones de un algoritmo como se describirá más adelante).

   En este sentido, existen tres tipos de estructuras de selección:

1. Estructura de selección simple.
2. Estructura de selección doble.
3. Estructura de selección múltiple.

   Los flujos de ejecución que siguen, dependiendo de la evaluación de su condición, pueden visualizarse mejor al observar sus representaciones en diagrama de flujo o en pseudocódigo, y se describirán en las entradas correspondientes.

   Estructuras de repetición.

   En las estructuras de repetición las acciones o sentencias del cuerpo del ciclo se repiten mientras se cumpla una determinada condición, misma que deberá seguir los mismos lineamientos descritos para las estructuras de selección.

   En este tipo de estructuras, es frecuente el uso de contadores (utilizados cuando se conoce de antemano el número de repeticiones) o centinelas (utilizados cuando no se conoce con anticipación el número de repeticiones que se realizarán) para controlar el número de repeticiones de un ciclo.

   En la entrada Diagramas de flujo y Pseudocódigo se muestran las notaciones algorítmicas respectivas utilizadas en las estructuras de control aquí mencionadas.

Contenido temático.

• Prólogo (íntegro de lo que en su momento fue la edición impresa).
  
• 1 El proceso de programación.
• 1.1 Etapas del proceso de programación en C.
•     Diseño del algoritmo.
•     Pruebas de escritorio para el algoritmo.
•     Edición del programa en código fuente.
•     Compilación.
•     Vinculación.
•     Carga y ejecución.
•     Depuración.
• 1.2 Estructura de un programa en C.
• 1.3 Ejercicios selectos.
• 2 Bienvenido a C!
• 2.1 El primer programa en C.
• 2.2 Lectura de datos.
• 2.3 Consideraciones adicionales respecto a la E/S de procesos.
• 2.4 Ejercicios selectos.
• 3 Estructuras de control.
• 3.1 Estructuras de control para la selección.
• La estructura de control if.
• La estructura de control if-else.
• El operador ternario ? : .
• La estructura de control switch.
• 3.2 Estructuras de control para la repetición.
• La estructura de control while.
• La estructura de control do-while.
• La estructura de control for.
• 3.3 Estructuras de control combinadas.
• 3.4 Tipos de repetición.
• Repetición controlada por contador.
• Repetición controlada por centinela.
• Repeticiones híbridas.
• 3.5 Ejercicios selectos.
• 4 Módulos de programa: funciones.
• 4.1 Funciones de biblioteca.
• 4.2 Estructura para las funciones en C.
• 4.3 Ejemplos de definición de funciones.
• 4.4 Ámbitos de variables.
• 4.5 Bibliotecas personalizadas de funciones.
• 4.6 Ejercicios selectos.
• 5 Recursividad. 
• 5.1 Definición y conceptos.
• 5.2 Soluciones iterativas vs recursivas.
• 5.3 Torres de Hanoi.
• 5.4 Ejercicios selectos.
• 6 Arreglos.
• 6.1 Arreglos de una dimensión (vectores).
•     Arreglos y funciones.
•     Ordenamiento por burbuja.
•     Búsqueda lineal y búsqueda binaria.
•     Arreglos de caracteres (cadenas).
• 6.2 Arreglos de dos dimensiones (matrices).
•     Suma de matrices.
• 6.3 Arreglos de n dimensiones.
• 6.4 Consideraciones finales con arreglos.
• 6.5 Ejercicios selectos (arreglos/vectores).
• 6.6 Ejercicios selectos (matrices).
• 7 Apuntadores.
• 7.1Definición, estructura y representación.
• 7.2 Parámetros por valor y por referencia.
• 7.3 Aritmética de apuntadores.
• 7.4 Apuntadores y arreglos.
•     Asignación dinámica de memoria.
•     Arreglos.
•     Matrices.
•     Argumentos en la invocación de programas.
• 7.5 Apuntadores a funciones.
•     Arreglos de apuntadores a funciones.
• 7.6 Ordenamiento genérico.
•     Burbuja genérico. 
•     Invocación.
  
• 7.7 Ejercicios selectos (apuntadores).
• 7.8 Ejercicios selectos (doble apuntador).
• 8 Abstracción de datos.
• 8.1 Conceptos, representación y estructura.
• 8.2 Abstracción en acción.
• 8.3 Estructuras compuestas.
• 8.4 Arreglos de estructuras.
• 8.5Abstracción de matrices.
• 8.6 Ejercicios selectos.
• 9 Archivos.
• 9.1 Definición y conceptos.
• 9.2 Archivos de texto.
•    Dos aplicaciones de archivos de texto.
•    Consideraciones adicionales con archivos de texto.
• 9.3 Archivos binarios.
• 9.4 Ejercicios selectos.
• 10 Algoritmos: panorama general.
• 10.1 Panorama general.
• 10.2 Teorema de Böhm y Jacopini.
• 10.3 Estructuras de control.
• 10.4 Definición y conceptos.
• Uso de la computadora en la resolución de problemas.
• Cinco importantes condiciones de un algoritmo.
• Estructura de un algoritmo.
• Pruebas de algoritmos.
• 10.5 Diagramas de flujo.
• Estructuras de control.
• Algoritmo de Euclides.
• 10.6 Pseudo código.
• Estructuras de control.
• Algoritmo de Euclides.
• 10.7 Pruebas de escritorio.
• 10.8 Diseño básico de programas estructurados y consideraciones finales.
• 11 Bibliografía sugerida.
• 12 Miscelánea.
• C Reference.
  
• Comentarios y sugerencias.
  
• Compilación de programas.
• El Yoda del Valle del Silicio (Silicon Valley).
  
• Errores frecuentes de programación.
• FOLDOC (Free OnLine Dictionary Of Computing).
  
• Manual de referencia en línea (cplusplus).
• Móvil C (Compilador de C para móviles). 
• The Community Wiki for GLIBC.
  
• The GNU C Library.
  
• To teach or not to teach.

El interés que despierta en mí un filósofo depende exactamente de su capacidad para darnos un ejemplo.
Friedrich Nietzsche.

Ejercicios selectos (archivos).

1. Investigue para qué sirven los modos de apertura w+ y a+.
2. Modifique el Ejemplo 9.1 en las líneas 47 y 48. Substituya archivoPtr por stdout y vea lo que sucede ¿Se comprueba lo descrito en el blog?
3. Para el programa del Ejemplo 9.1, ¿qué sucede si en lugar de abrir el archivo en modo agregar (a) se abre en modo lectura (r) sin cambiar ninguna otra sentencia? Pruebe utilizando el archivo "contactos.txt" generado por el Ejemplo 9.1 y también sin dicho archivo (elimínelo).
4. Para el programa del Ejemplo 9.1, ¿qué sucede si en lugar de abrir el archivo en modo agregar (a) se abre en modo escribir (w) sin cambiar ninguna otra sentencia? Pruebe utilizando el archivo "contactos.txt" generado por el Ejemplo 9.1 y también sin dicho archivo (elimínelo).
5. Modifique la función llenaDirectorio del Ejemplo 9.1 para que en lugar de la función gets use la función fgets.
6. Con base en el Ejemplo 9.1 y Ejemplo 9.2, escriba un programa que integre las dos funcionalidades respectivas. Agregue además la posibilidad, a través de funciones, de que los contactos sean ordenados y almacenados en otro archivo, que se puedan realizar búsquedas (lineal y binaria) con base en el nombre o el teléfono del contacto. No olvide trabajar con los datos en memoria, acceda a archivos de texto sólo para leer información o almacenarla. En este sentido, puede resultar útil guardar, como primera línea del archivo, el número de contactos almacenados, con lo que podría generar un arreglo utilizando asignación dinámica de memoria. La idea de este ejercicio es poner en práctica todo lo aprendido en el blog hasta ahora.
7. Modifique el programa del Ejemplo 9.3 para que procese, y en consecuencia presente en la salida estándar, todos los archivos que se le proporcionen en la invocación.
8. Escriba un programa que compare dos archivos y determine si dichos archivos son o no iguales. Los archivos procesados serán proporcionados desde la invocación del programa. Así, si su programa se llama compara, la ejecución: $./compara archivo1 archivo2 implica que se deben comparar archivo1 con archivo2. Si los archivos son iguales, se notifica al usuario de dicha situación; en caso contrario, se indicará la primera línea de cada archivo que no coincidió.
9. Para el programa del Ejemplo 9.4, pruebe lo siguiente:
1. Seleccione un archivo de texto que contenga la letra de una canción por ejemplo. Busque de preferencia la letra de una canción en inglés para omitir los detalles referentes a la letra ñ, los acentos, y la diéresis de nuestro lenguaje.
2. Cambie la vocal a del archivo fuente (archivo1) por el símbolo # en el archivo destino (archivo2).
3. Use el archivo generado en el paso anterior (archivo2) como archivo fuente para una nueva ejecución, en la que cambiará ahora el símbolo # por la vocal a, generándose un nuevo archivo destino: archivo3.
4. Si todo está bien y suponiendo que en archivo1 no estaba el símbolo #, archivo1 debe ser idéntico a archivo3. Compruebe que así sea. Puede apoyarse de programas que comparan archivos, como el comando diff de Unix y GNU/Linux, y el programa compara del Ejercicio 7.

    10. Modifique el programa del Ejemplo 9.3 para que presente en la salida estándar, dos veces: una seguida de otra, el archivo procesado. La idea de este ejercicio es que pueda practicar el uso de la función rewind descrita brevemente en el blog.
    11. Escriba un programa que procese un archivo de texto proporcionado en la invocación del programa, y presente ordenadas en la salida estándar cada una de las líneas del archivo. Así, la ejecución de: $./ordena archivo presenta en la salida estándar cada una de las líneas de texto del archivo archivo, ordenadas alfabéticamente. Consulte el funcionamiento del programa sort de Unix y GNU/Linux para tener una mejor idea acerca del funcionamiento de su programa.
    12. Tomando como referencia el Ejemplo 9.4, escriba un programa que cambie una palabra por otra. Genere un nuevo archivo con los cambios, y tome en cuenta que deberá analizar tres casos:

1. Si la palabra a cambiar tiene la misma longitud, el cambio es simple.
2. Si la palabra a cambiar es de menor longitud, deberá recorrer los caracteres hacia la izquierda después de la nueva palabra para no dejar "basura" en el arreglo y en consecuencia en el nuevo archivo.
3. Si la palabra a cambiar es de mayor longitud, deberá introducir "más espacio" en la cadena para no sobre escribir caracteres existentes. Analice detenidamente cómo resolver dicha situación.

        Nota: La idea de este ejercicio es poner en práctica lo aprendido en el
        blog. Tome en cuenta que los cambios se deben realizar directamente
        sobre el arreglo antes de escribirlo en el nuevo archivo.

    13. Pruebe lo que sucede si elimina la función getchar (línea 53) del Ejemplo 9.6.
    14. El programa del Ejemplo 9.6 está incompleto. Modifíquelo para completar las opciones de menú:

• Eliminar contacto. Tome en consideración que la eliminación de un contacto requiere de la confirmación de la eliminación de dicho contacto antes de proceder.
• Modificar contacto. La modificación del contacto puede ser en varios sentidos:
• Conservar los datos del contacto pero moverlo de lugar, es decir, que sea ahora otro número de contacto, lo cual implica verificar que el nuevo número de contacto seleccionado no esté ya ocupado.
• Modificar sólo el nombre del contacto.
• Modificar únicamente el teléfono del contacto.
• Modificar tanto el nombre como el teléfono del contacto.
• No olvide también confirmar los cambios.

    15. En relación con en el Ejercicio 12 de la sección de ejercicios Abstracción de Datos, complemente la funcionalidad planteada en dicho ejercicio para que su programa sea capaz de leer figuras geométricas desde un archivo de texto especificado por el usuario.
    16. Escriba un programa que en base a lo siguiente: $ ./morse cadena archivo1 archivo2 permita leer el archivo de texto archivo1, de tal forma que si cadena es "a", su programa:

• Procese únicamente símbolos alfanuméricos y espacios de archivo1 y los convierta a su correspondiente representación en código Morse en archivo2. Los espacios quedan sin cambio alguno. Cualquier otro símbolo es ignorado y descartado.
• Cada símbolo representado en código Morse irá separado por comas en archivo2. Los espacios quedan sin cambio alguno.
• Por otro lado, si cadena es "de", se deberá hacer el proceso inverso: convertir de Morse a texto (en efecto, se habrá perdido la redacción original pero la esencia del texto deberá ser la misma). Sugerencia: para el caso de Morse a texto, investigue la función strtok de la biblioteca string.h.

    17. En la entrada referente a Abstracción de Datos se desarrolló una biblioteca de funciones que inició con el Ejemplo 8.5. Posteriormente, en la sección de ejercicios, se fueron desarrollando nuevas funciones que fueron incorporadas a dicha biblioteca. Tomando en cuenta lo anterior, realice lo siguiente:

• Genere una nueva biblioteca de funciones que incorpore gestión de archivos a todas las operaciones realizadas con matrices:
• suma.
• resta.
• producto.
• transpuesta.
• esSimetrica.
• inversa.
• Presente un menú de opciones con las operaciones que es posible realizar con matrices. Agregue al menú la opción de Matriz Aleatoria la cual deberá realizar lo siguiente:
• Solicitar las dimensiones del matriz: m (renglones) y n (columnas).
• Solicitar un rango para el numerador (num) y un rango para el denominador (den).
• Generar dinámicamente una matriz de m x n de números racionales aleatorios. El numerador y el denominador deberán estar en sus respectivos rangos.
• Para cada operación se deberá permitir introducir la o las matrices (según sea el caso), desde la entrada estándar o desde un archivo de texto especificado por el usuario.
• Para cada operación, excepto esSimetrica, se deberá permitir además de visualizar el resultado en la salida estándar, guardarlo en un archivo de texto especificado por el usuario.

    18. Modifique el Ejemplo 9.7 para que pueda procesar archivos de cualquier tamaño. Sugerencia: defina un buffer de un tamaño fijo, digamos 4 KB, y lea bloques de 4 KB en cada acceso al archivo. Tome en cuenta que el último bloque leído podría tener menos de 4 KB y que si el archivo es muy pequeño dicha situación podría presentarse desde el primer bloque leído, por lo que deberá verificar el número de bytes leídos por la función fread en cada lectura.
Tome como referencia el Ejemplo 9.7 para hacer una implementación del comando cp (copy) de GNU/Linux.