27,99 €
Mehr erfahren.
- Herausgeber: Marcombo
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Spanisch
Si desea adentrarse en el mundo de la programación desde cero y avanzar progresivamente hasta cubrir los aspectos más complejos de la programación en C++, mediante el análisis y desarrollo de gran cantidad de problemas algorítmicos de todos los niveles, este libro será su gran aliado. Curso de algoritmos y programación a fondo presenta 16 lecciones, distribuidas en 6 capítulos, para estudiar los recursos y las técnicas de programación que le llevarán a tratar cuestiones avanzadas, como el desarrollo de un programa compresor/descompresor de archivos basado en el algoritmo de Huffman. Además, este libro desarrolla funciones y tipos abstractos de datos (TAD) para conformar una biblioteca (API) que podrá utilizar en la resolución de una gran cantidad de ejercicios y problemas. Asimismo, gracias a esta lectura: "Aprenderá a programar ágilmente con los vídeos explicativos del autor que acompañan cada lección. "Podrá validar los conocimientos adquiridos con las autoevaluaciones que se proponen y recibirá el feedback con el que determinará si debe releer la lección o parte de esta, antes de pasar a la siguiente. En esta nueva edición se profundiza especialmente en el análisis y la resolución de problemas. Se propone un caso testigo y diversas variantes de este, que le permitirán identificar distintos tipos de problemas que estudiar y discutir estrategias de solución. Sin duda, esta es una obra imprescindible si desea ser un futuro programador o busca afianzar y profundizar sus conocimientos en la materia.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 241
Veröffentlichungsjahr: 2023
Ähnliche
Curso de algoritmos y programación a fondo
Implementaciones en C++
Pablo Augusto Sznajdleder
Derechos reservados © Alfaomega Grupo Editor Argentino S.A.
Segunda edición: 2023
ISBN: 978-842-6736-73-4
Segunda edición: MARCOMBO, S.L. 2023
© 2023 MARCOMBO, S.L.
www.marcombo.com
Cualquier forma de reproducción, distribución, comunicación pública o transformación de esta obra solo puede ser realizada con la autorización de sus titulares, salvo excepción prevista por la ley. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.cedro.org) si necesita fotocopiar o escanear algún fragmento de esta obra
ISBN del libro en papel: 978-84-267- 3633-8
ISBN del libro electrónico: 978-84-267-3673-4
Producción del ePub: booqlab
Este trabajo está dedicado muy especialmente a la memoria de mi amigo, colega y vecino, Claudio Algieri.
La familia de Pablo retratada por Lucía Belén Berro @lavidadetontacursi
Acerca del autor
Pablo Augusto Sznajdleder es Ingeniero en Sistemas de Información, licenciado de la Universidad Tecnológica Nacional (UTN.BA, 1999).
Su tesis de doctorado (UTN.BA, 2018) describe cómo implementar transferencias de conocimientos asistidas por Tecnologías de Mediación de Interacción.
Profesor titular en la cátedra de “Algoritmos y estructura de datos”, y director de cátedra en “Patrones algorítmicos para estructuras avanzadas”. Ambas materias en UTN.BA.
Autor de diversas obras, entre las que destacan: Java a fondo (Alfaomega), Algoritmos a fondo (Alfaomega) y JEE a fondo (Alfaomega).
Entre 1996 y 2001 trabajó como instructor Java para Sun Microsystems y Oracle Argentina; obteniendo, en 1997, las certificaciones SCJP y SCJD. Estas fueron las primeras certificaciones Java acreditadas en Argentina y estuvieron entre las primeras logradas en Latinoamérica.
Hoy, con más de 25 años de experiencia en tecnología Java, se desempeña en el ámbito profesional como consultor e instructor, proveyendo servicios de coaching y capacitación para las empresas líderes del país.
Antes de comenzar a leer
En este libro, se utiliza la tipografía Courier en los casos en los que se hace referencia a código o acciones por realizar en el ordenador, ya sea en un ejemplo o cuando se refiere a alguna función mencionada en el texto. También se usa para indicar menús de programas, teclas, URL, grupos de noticias o direcciones de correos electrónicos.
Los términos o definiciones cuyos significados están muy asociados al inglés se expresan en dicho idioma en cursiva.
El código fuente de los ejemplos, los tres apéndices (“Ejercicios”, “Especificaciones” y “Problemas”), así como todos los recursos didácticos y de programación que se utilizan en este libro, podrán descargarse a medida que se avanza en la lectura.
Estos recursos también están disponibles en www.marcombo.info con el código ALGORITMOS23
Contenido
Prólogo
Agradecimientos
CAPÍTULO 1
Introducción al diseño de algoritmos y programación
1.1. Lección 1
1.1.1. ¿Qué es un algoritmo?
1.1.2. Lenguaje algorítmico
1.1.3. Recursos de programación
1.1.3.1. El ordenador
1.1.3.2. Operaciones aritméticas y expresiones lógicas
1.1.3.3. Lenguaje de programación
1.1.3.4. Programa
1.1.3.5. Variables y tipos de dato
1.1.3.6. Convención de nombres de variables
1.1.3.7. Consola
1.1.3.8. Compilador
1.1.3.9. Entorno Integrado de desarrollo
1.1.4. Teorema de la programación estructurada
1.1.4.1. Acción simple
1.1.4.2. Acción condicional
1.1.4.3. Acción iterativa
1.1.4.4. Acciones de única entrada y única salida
1.1.5. Más recursos de programación
1.1.5.1. Contadores y acumuladores
1.1.5.2. Prueba de escritorio
1.1.5.3. Operadores aritméticos
1.1.5.4. Otras operaciones matemáticas
1.1.5.5. Operadores y expresiones lógicas
1.1.5.6. Operadores relacionales
1.1.5.7. Operadores relacionales y cadenas de caracteres
1.1.6. Análisis de ejercicios y problemas
1.1.6.1. Datos de entrada, de contexto y de salida
1.1.6.2. Procesos para transformar la entrada en salida
1.1.7. Tipos de problema
1.1.7.1. Problemas de registro simple y problemas de múltiples registros
1.1.7.2. Multiplicidad
1.1.7.3. Registros y tablas
1.1.7.4. Problemas de procesamiento horizontal y procesamiento vertical
1.1.7.5. Problemas de corte de control
1.1.8. Autoevaluación y ejercicios
1.2. Lección 2
1.2.1. Tipo de dato
1.2.1.1. Tipos enteros
1.2.1.2. Tipos flotantes
1.2.1.3. Tipos alfanuméricos
1.2.1.4. Tipos lógicos
1.2.1.5. Tipo de dato nulo
1.2.1.6. Tipos de dato primitivos y tipos definidos por el programador
1.2.2. Alcance de una variable
1.2.3. Metodología Top-Down
1.2.3.1. Funciones
1.2.3.2. Prototipo de una función
1.2.3.3. Compilar un programa que invoca funciones
1.2.3.4. Reusabilidad del código
1.2.3.5. Legibilidad del código fuente
1.2.3.6. Bibliotecas de funciones
1.2.3.7. Convención de nombres de funciones
1.2.3.8. Parámetros y argumentos
1.2.3.9. Parámetros por valor y referencia
1.2.3.10. Variables locales
1.2.4. Autoevaluación y ejercicios
1.3. Lección 3
1.3.1. Estructuras
1.3.1.1. Inicialización de una estructura
1.3.1.2. Convención de nombres de estructuras
1.3.1.3. Función de inicialización de una estructura
1.3.1.4. Estructuras anidadas
1.3.2. Tipo Abstracto de Dato (TAD)
1.3.2.1. Usuario del TAD
1.3.2.2. Inicialización de un TAD
1.3.2.3. Sobrecarga de funciones
1.3.3. Autoevaluación y ejercicios
1.4. ¿Qué sigue?
CAPÍTULO 2
Cadenas de caracteres y estructura de datos
2.1. Lección 4
2.1.1. Carácter
2.1.2. Cadena de caracteres
2.1.2.1. Caracteres especiales y carácter de escape
2.1.2.2. Carácter nulo que indica el final de una cadena
2.1.2.3. Acceso directo a los caracteres de una cadena
2.1.2.4. Longitud de una cadena
2.1.2.5. Operadores aritméticos unarios
2.1.2.6. Ciclo iterativo for
2.1.2.7. Concatenar cadenas de caracteres
2.1.2.8. Operadores relacionales aplicados a cadenas
2.1.2.9. Función de comparación
2.1.2.10. If-inline
2.1.3. Biblioteca de funciones y API
2.1.3.1. Tratamiento de cadenas de caracteres
2.1.3.2. Actividad práctica: API de tratamiento de cadenas de caracteres
2.1.4. Argumentos en línea de comandos
2.1.5. Autoevaluación y ejercicios
2.2. Lección 5
2.2.1. Tratamiento de tokens
2.2.2. Actividad práctica: API de tratamiento de tokens
2.2.3. Autoevaluación y ejercicios
2.3. Lección 6
2.3.1. Funciones como argumentos de otras funciones
2.3.2. Tipo de dato genérico (template)
2.3.3. Autoevaluación y ejercicios
2.4. Lección 7
2.4.1. Colecciones
2.4.2. TAD Coll
2.4.2.1. Ejemplo de uso
2.4.2.2. Estructura del TAD Coll
2.4.2.3. Actividad práctica: API del TAD Coll
2.4.3. Autoevaluación y ejercicios
2.5. Lección 8
2.5.1. Ordenamiento
2.5.1.1. Ordenamiento por inserción simple
2.5.1.2. Ordenamiento por burbujeo
2.5.1.3. Ordenamiento por burbujeo mejorado
2.5.1.4. Ordenamiento por inserción avanzado
2.5.2. Búsqueda
2.5.2.1. Búsqueda lineal
2.5.2.2. Búsqueda binaria
2.5.3. Autoevaluación y ejercicios
2.6. Lección 9
2.6.1. Estructura de datos (parte 1)
2.6.1.1. Estructuras estáticas y dinámicas
2.6.1.2. Estructura de datos como cimiento del algoritmo
2.6.1.3. Colección de estructuras
2.6.1.4. Colección de colecciones
2.6.1.5. Colecciones de estructuras que tienen colecciones
2.6.2. Autoevaluación y ejercicios
2.7. ¿Qué sigue?
CAPÍTULO 3
Archivos
3.1. Lección 10
3.1.1. Introducción
3.1.1.1. Archivo
3.1.1.2. Tipos de archivo
3.1.1.3. Archivos binarios
3.1.1.4. Archivos de texto
3.1.2. Gestión de archivos
3.1.2.1. Funciones de biblioteca
3.1.2.2. Grabar y leer datos
3.1.2.3. Archivo secuencial
3.1.2.4. Archivos de registros de longitud fija
3.1.2.5. Big-endian y Little-endian
3.1.2.6. Archivos de registros de longitud variable
3.1.2.7. Archivos de estructuras
3.1.2.8. Posicionamiento directo
3.1.2.9. Posicionamiento directo en registros
3.1.2.10. Eliminar registros físicamente
3.1.2.11. Eliminar registros lógicamente
3.1.2.12. Modificar registros
3.1.2.13. Longitud de un archivo
3.1.2.14. Cantidad de registros
3.1.2.15. Restricciones
3.1.3. Actividad práctica: API para el tratamiento de archivos de registros
3.1.4. Ejemplos de uso de las funciones de la API
3.1.4.1. Escribir y leer caracteres
3.1.4.2. Escribir y grabar números enteros (short)
3.1.4.3. Escribir y leer estructuras (Persona)
3.1.4.4. Baja lógica
3.1.5. Autoevaluación y ejercicios
3.2. Lección 11
3.2.1. Operadores de bit
3.2.1.1. Operadores de desplazamiento
3.2.1.2. Bases numéricas 8 (octal) y 16 (hexadecimal)
3.2.1.3. Operadores lógicos
3.2.1.4. Máscara de bit
3.2.2. Actividad práctica: TAD BitWriter y BitReader
3.2.3. Autoevaluación y ejercicios
3.3. ¿Qué sigue?
CAPÍTULO 4
Resolución de problemas
4.1. Cómo analizar un problema
4.1.1. Contexto, relevamiento y enunciado del problema
4.1.2. Datos persistentes
4.1.2.1. Archivos de consulta
4.1.2.2. Archivos de novedades
4.1.3. Estrategia
4.2. Tipos de problema
4.2.1. Problemas de corte de control
4.2.2. Problemas de apareo de archivos
4.2.3. Problemas de procesamiento directo
4.3. Gestión de archivos y persistencia de datos
4.3.1. Restricciones
4.3.2. Búsqueda sobre archivos
4.3.2.1. Subir el archivo a la memoria, en una colección de objetos
4.3.2.2. Búsqueda binaria sobre un archivo
4.3.2.3. Indexar un archivo
4.3.3. Ordenar archivos
4.3.3.1. Ordenamiento en la memoria
4.3.3.2. Ordenamiento por indexación
4.4. Algoritmos Tools
4.5. Caso de prueba
4.5.1. Corte de control (versión 1)
4.5.2. Corte de control, con salida bufferizada (versión 2)
4.5.3. Descubrimiento (versión 3)
4.5.4. Archivos de consultas en la memoria (versión 4)
4.5.5. Descubrimiento, otro caso (versión 5)
4.5.6. Actualizar registros (versión 6)
4.5.7. Colección de colecciones (versión 7)
4.5.8. Colección de colecciones, con descubrimiento (versión 8)
4.5.9. Apareo de archivos (versión 9)
4.5.10. Apareo de archivos, con corte de control (versión 10)
4.5.11. Búsqueda binaria sobre el archivo de consulta (versión 11)
4.5.12. Indexación directa (versión 12)
4.5.13. Indexación indirecta, con corte de control (versión 13)
4.5.14. Indexación indirecta múltiple (versión 14)
4.5.15. Ordenar y depurar un archivo (versión 15)
4.6. Autoevaluación y ejercicios
4.7. ¿Qué sigue?
CAPÍTULO 5
Estructuras indexadas, lineales y gestión de memoria
5.1. Lección 12
5.1.1. Array
5.1.1.1. Capacidad del array
5.1.1.2. Inicializar un array a partir de un conjunto de valores
5.1.1.3. Inicialización programática
5.1.1.4. Longitud del array
5.1.1.5. Arrays de estructuras
5.1.1.6. Arrays multidimensionales
5.1.2. Operaciones sobre arrays
5.1.2.1. Agregar un elemento al final de un array
5.1.2.2. Determinar si el array contiene un elemento especificado
5.1.2.3. Insertar un elemento en una determinada posición
5.1.2.4. Eliminar el elemento ubicado en una determinada posición
5.1.3. Actividad práctica: API de operaciones sobre arrays
5.1.4. Autoevaluación y ejercicios
5.2. Lección 13
5.2.1. Gestión de memoria
5.2.1.1. Punteros
5.2.1.2. Operador de dirección (&)
5.2.1.3. Operador de dirección o contenido (*)
5.2.1.4. Funciones que reciben punteros como parámetros
5.2.1.5. Punteros a punteros
5.2.1.6. Punteros a estructuras y operador -> (flecha)
5.2.1.7. Punteros y arrays
5.2.1.8. Aritmética de direcciones
5.2.1.9. Memoria estática
5.2.1.10. Memoria dinámica
5.2.1.11. Crear arrays dinámicamente
5.2.1.12. Redimensionar un array
5.2.1.13. Crear matrices dinámicamente
5.2.2. Actividad práctica: TAD Array
5.2.3. Actividad práctica: TAD Map
5.2.4. Autoevaluación y ejercicios
5.3. Lección 14
5.3.1. Nodo
5.3.2. Lista enlazada (linked list)
5.3.2.1. Recorrer una lista enlazada
5.3.2.2. Agregar un valor al final de una lista enlazada
5.3.2.3. Liberar la memoria que ocupa la lista
5.3.2.4. Determinar si la lista contiene un valor especificado
5.3.2.5. Insertar un valor en una lista ordenada
5.3.2.6. Eliminar un elemento de la lista
5.3.3. Actividad práctica: API de operaciones sobre listas enlazadas
5.3.4. Pila (stack)
5.3.4.1. Apilar un elemento (push)
5.3.4.2. Desapilar un elemento (pop)
5.3.4.3. Determinar si la pila tiene elementos
5.3.4.4. Ejemplo de uso
5.3.5. Actividad práctica: API de operaciones sobre pilas (extensión)
5.3.6. Cola (queue)
5.3.6.1. Encolar un elemento (enqueue)
5.3.6.2. Desencolar un elemento (dequeue)
5.3.6.3. Determinar si la cola tiene elementos
5.3.6.4. Implementación sobre una lista circular
5.3.7. Actividad práctica: API de operaciones sobre colas (extensión)
5.3.8. Actividad práctica: TAD List, Stack y Queue
5.3.9. Autoevaluación y ejercicios
5.4. Lección 15
5.4.1. Estructura de datos (parte 2)
5.4.1.1. Colección de estructuras
5.4.1.2. Colección de colecciones
5.4.1.3. Colección de estructuras que tienen colecciones
5.4.2. Autoevaluación y ejercicios
5.5. ¿Qué sigue?
CAPÍTULO 6
Algoritmo de Huffman. Ejercicio integrador
6.1. Lección 16
6.1.1. Introducción
6.1.2. Alcance del ejercicio
6.1.3. Algoritmo de Huffman
6.1.3.1. Paso 1 – Contar cuántas veces aparece cada byte
6.1.3.2. Paso 2 – Crear una lista enlazada
6.1.3.3. Paso 3 – Convertir la lista en un árbol binario (Árbol Huffman)
6.1.4. Árbol Huffman
6.1.4.1. Características
6.1.4.2. Códigos Huffman
6.1.4.3. Longitud máxima de un código Huffman
6.1.5. Implementación del ejercicio
6.1.5.1. Setup
6.1.5.2. TAD HuffmanTree
6.1.5.3. Estructura HuffmanTreeInfo
6.1.5.4. Recopilación de los códigos Huffman
6.1.5.5. Compresión
6.1.5.6. Estructura del archivo comprimido (.huf)
6.1.5.7. Descompresión
6.1.6. Ejemplo
6.2. ¿Qué sigue?
Prólogo
“Los algoritmos están cada vez más presentes en nuestras vidas”.
Esta frase, que escuchamos cada vez con mayor frecuencia, puede dar motivo a una búsqueda en Internet, dando una cantidad extensa de resultados que permiten apreciar que es una realidad.
Los buscadores, redes sociales y plataformas de streaming, entre otras Tecnologías de Información y Comunicación (TIC), implementan algoritmos para alcanzar sus objetivos.
A mediados de los años 90, Nicholas Negroponte, a través de su best seller Ser digital, llamó la atención sobre los nuevos vientos en la vida humana. Hoy perfectamente podríamos titular una obra con Vivir en algoritmos, y de este modo representar lo que se derrama sobre las personas como un paradigma omnipresente.
El profesor Pablo Augusto Sznajdleder, apreciado exalumno de la carrera de Ingeniería de Sistemas de Información de la querida UTN Regional Bs. As., lleva muchos años trabajando en perfeccionar el modo de facilitar y acompañar en el proceso de aprendizaje a los estudiantes de ingeniería.
En este libro Pablo aplica su experiencia en la docencia, implementando una técnica que, mediada por recursos de TIC externos, facilita a
los interesados tener continuidad con los conocimientos volcados en la obra.
Como profesor del profesor, puedo valorar su esfuerzo en simplificar didácticamente el entramado de conceptos, dando un encadenamiento gradual a las ideas para alcanzar este saber tan importante, y con alto grado de abstracción.
No dudo que esta obra tendrá el éxito esperado y será de utilidad, especialmente para estudiantes de licenciaturas o ingenierías del área de informática y de sistemas.
Mi felicitación a Pablo, que enorgullece a quienes intervinimos humildemente en su formación profesional.
Ing. MSc. Alejandro Luis EchazúProfesor UTN - BA
Agradecimientos
A Domingo Mandrafina, Damián Fernández y Alejandro Echazú.
CAPÍTULO 1
INTRODUCCIÓN AL DISEÑO DE ALGORITMOS Y PROGRAMACIÓN
1.1. Lección 1
Durante esta lección analizaremos conceptos básicos sobre algoritmos: qué es un algoritmo, para qué sirve, y cuál es la relación que existe entre algoritmo y programa.
Estudiaremos los recursos iniciales de programación: variables, tipos de dato, operadores aritméticos, lógicos y relacionales, y las estructuras de control de flujo de datos que describe el teorema de la programación estructurada.
Veremos también cómo usar la herramienta de programación Eclipse para codificar, compilar, depurar y ejecutar nuestro primer programa.
1.1.1. ¿Qué es un algoritmo?
Es un conjunto finito y ordenado de pasos o acciones cuya ejecución nos permite resolver un problema.
Dicho de otro modo: dado un determinado problema, cuáles serían las acciones y en qué orden deberíamos ejecutarlas para lograr una resolución satisfactoria.
Lección 1
Ejecutamos algoritmos para resolver los problemas cotidianos que se nos presentan día a día, independientemente de cuál sea su nivel de complejidad.
Por ejemplo, si estamos parados en el borde de la acera y queremos cruzar la calle, el siguiente algoritmo resolverá nuestra situación problemática:
Lo anterior es sólo una mínima parte del algoritmo que ejecutamos cada vez que tenemos que cruzar una calle.
Podría suceder que al mirar hacia la izquierda (o hacia la derecha) observemos que sí viene un coche, pero se encuentra a una distancia tal que igual podremos cruzar sin ser atropellados. O tal vez observemos que el coche no está tan lejos, pero se aproxima a baja velocidad, así que podremos cruzar de todos modos.
La observación sobre la distancia y velocidad del coche, así como la determinación del grado de peligrosidad que esto representa para nosotros (si es que decidimos cruzar la calle) implica resolver una serie de cálculos de relativa complejidad, que realizamos mentalmente y sin darnos cuenta.
Por ejemplo: llamemos p a nuestra ubicación, q a la ubicación del coche, v a su velocidad, z a nuestra velocidad (cuán rápido caminamos) y d a la distancia que debemos recorrer para llegar al borde de la acera de enfrente.
Entonces, el tiempo en que el coche llegará hacia nosotros lo calculamos como: |p-q|/v, y debe ser mayor que el tiempo que nos llevará cruzar la calle, que podemos calcular como: |p-d|/z. Incluso, inconscientemente manejamos un nivel de riesgo, pues no nos gustaría sentir el viento del coche pasando a 1 milímetro de nuestro cuerpo. Así que, si llamamos r al riesgo que estamos dispuestos a asumir, sólo cruzaremos la calle si se comprueba que: | |p-q|/v - |p-d|/z |>r.
Esta decisión, que realizaremos en función de los cálculos precedentes, la podemos representar algorítmicamente con el siguiente fragmento de pseudocódigo:
Sin embargo, no sólo los ingenieros podemos cruzar las calles de la ciudad. Todas las personas lo hacen a diario, porque el cerebro humano tiene la capacidad de realizar estas operaciones matemáticas en una milésima de segundo.
Pero hay algo más: cruzamos. ¿Qué significa esto? Todos comprendemos el significado de esta expresión porque tenemos capacidad de abstracción. Pero si nos detenemos a pensar qué implica cruzar veremos que también requiere una serie de acciones. Se trata de un algoritmo en sí mismo.
Cruzar implica:
Aún hay más: dar un paso también es un algoritmo en sí mismo, que implica:
Razonando así, podemos entrar en detalle tanto como queramos. Sin embargo, esto no es necesario porque nuestra capacidad de abstracción nos permite comprender qué representa un único término y qué acciones están involucradas.
El desafío consiste en diseñar y describir (o programar) algoritmos para que sean ejecutados por un ordenador, que no tiene nuestra capacidad de abstracción.
1.1.2. Lenguaje algorítmico
Para documentar un algoritmo se utiliza un lenguaje algorítmico. Existen diversos lenguajes algorítmicos, pero los más utilizados son:
1. Diagramas.
2. Pseudocódigo.
3. Lenguajes de programación.
En este curso utilizaremos los tres, pero principalmente trabajaremos con el lenguaje de programación C++.
1.1.3. Recursos de programación
1.1.3.1. El ordenador
El ordenador sólo puede realizar operaciones aritméticas y lógicas, y tiene mucha memoria. Pero al no tener nuestra capacidad de abstracción tendremos que indicarle, hasta el menor detalle, cómo debe hacer cada una de las cosas que queremos que haga.
1.1.3.2. Operaciones aritméticas y expresiones lógicas
Una operación aritmética consiste en un cálculo matemático primario: suma, resta, multiplicación, división y módulo (o valor residual). Todos los lenguajes de programación proveen estos operadores matemáticos.
Una expresión lógica es un enunciado susceptible de ser verdadero o falso. “2 es mayor que 5” es una expresión lógica cuyo valor de verdad es falso.
Más adelante, veremos que existen operadores lógicos, que usaremos para realizar operaciones entre expresiones lógicas, obteniendo como resultado una nueva expresión lógica con su correspondiente valor de verdad.
1.1.3.3. Lenguaje de programación
Para que un ordenador pueda entender y ejecutar un algoritmo debemos escribirlo en algún lenguaje de programación. En este curso utilizaremos el lenguaje C++.
Los lenguajes de programación están compuestos por un conjunto de palabras en inglés y un conjunto de reglas sintácticas. La acción de escribir un algoritmo en C++ (o en cualquier otro lenguaje) se llama codificar. El algoritmo codificado se llama código fuente o simplemente programa.
1.1.3.4. Programa
Un programa es un algoritmo codificado en algún lenguaje de programación. También podríamos decir que el algoritmo es la lógica de un programa de ordenador.
Por ejemplo, el siguiente algoritmo nos permite preguntarle a una persona cómo se llama, y luego saludarla por su nombre:
Si el pseudocódigo del algoritmo anterior lo codificamos en C++, lo convertiremos en un programa informático:
Las líneas que comienzan con // (doble barra) son comentarios o acotaciones que nos ayudarán a comprender qué hace la siguiente línea de código.
Las instrucciones cout y cin, que significan console out y console in, permiten respectivamente mostrar un mensaje (salida) e introducir un dato (entrada).
Para introducir un dato y recordarlo posteriormente, debemos almacenarlo en la memoria del ordenador. Esto requiere que anticipadamente dispongamos de un espacio de memoria, que en este caso usaremos para guardar una cadena de caracteres: el conjunto de caracteres que componen el nombre del usuario.
La línea que dice string nom reserva dicho espacio de memoria identificándolo con la palabra nom. En adelante, dentro del programa, usaremos nom para tener acceso al dato que introdujo el usuario.
Por el momento no analizaremos las palabras main y return.
1.1.3.5. Variables y tipos de dato
Los identificadores que utilizamos para representar espacios de memoria se llaman variables. Por ejemplo: la variable nom del programa anterior.
Las variables permiten guardar datos en la memoria del ordenador. El espacio de memoria que representa una variable debe estar preparado especialmente en función de cuál sea el tipo de dato que allí queremos guardar.
En el ejemplo anterior, el tipo de dato de la variable nom es string, lo que nos permite guardar valores alfanuméricos (cadenas de caracteres).
Sin embargo, si en el programa le hubiésemos pedido al usuario que introdujera su edad, habríamos necesitado disponer de una variable de tipo numérico entero: int. Y si le hubiéramos preguntado por su altura, probablemente, la variable debiera haber sido de tipo numérico real: double.
Observemos que llamamos nom a la variable, justamente porque la utilizaremos para guardar el nombre de una persona. Podríamos haberla llamado n, x, pepe o theWalrusWasPaul.
No importa cuál sea el nombre de la variable; aunque sí es muy importante escoger un nombre que describa cuál es el dato que la variable va a contener, pues eso nos ayudará a incrementar la legibilidad del código.
Por ejemplo, si en el algoritmo vamos a pedir introducir: nombre, edad y altura, deberíamos declarar tres variables cuyos nombres podrían ser los siguientes:
Tabla 1.1. Nombres de variables
Claramente, la Opción 1 es la más apropiada y la Opción 4 sería la peor elección. Sin embargo, funcionalmente todas son correctas.
Las variables deben comenzar con un carácter alfabético o un guion bajo ('_'). No pueden contener símbolos de puntuación ni operadores de ningún tipo.
Tabla 1.2. Nombres de variables correctos e incorrectos
1.1.3.6. Convención de nombres de variables
Más allá de las diferentes posibilidades que mostramos en la tabla anterior, existe una convención de nombres que restringe y ordena el modo en que debemos llamar a las variables que declaramos en nuestros programas.
Según dicha convención, que aceptaremos y respetaremos a lo largo del curso, las variables deben escribirse en minúscula. Si su nombre está compuesto de dos o más palabras, cada inicial (excepto la primera) debe colocarse en mayúscula.
Por ejemplo:
Por supuesto, lo anterior no impide que utilicemos nombres triviales como i, j, k, p, q y aux para nombrar aquellas variables que resultan poco relevantes. Pero sí debemos nombrarlas con letras minúsculas. Nunca en mayúscula.
1.1.3.7. Consola
Más arriba mencionamos la consola. Simplemente diremos que se trata de un dispositivo de entrada/salida compuesto por el teclado físico del ordenador (entrada) y una ventana terminal (salida), a la que accedemos mediante la siguiente combinación de teclas: WIN + R → CMD (en Windows).
1.1.3.8. Compilador
Para que el ordenador pueda ejecutar un programa debemos convertir su código fuente en lo que llamaremos código de máquina; esto es: unos y ceros. Pues el ordenador sólo comprende y ejecuta instrucciones codificadas de este modo.
Los lenguajes de programación incluyen un programa llamado compilador que realiza esa tarea por nosotros. Tal como se ilustra en la siguiente imagen.
Figura 1.1. Proceso de compilación
El compilador selecciona el código fuente de un programa (que debe estar contenido en un archivo con extensión .cpp), y genera un archivo con extensión .exe conteniendo el código de máquina (unos y ceros) que sí podrá ser ejecutado por el ordenador.
1.1.3.9. Entorno Integrado de desarrollo
El trabajo del programador consiste en diseñar el algoritmo, codificarlo, compilarlo, probarlo y depurarlo.
Descargar Eclipse
Existen herramientas para asistirnos durante todo el proceso de desarrollo, integrando estas tareas y facilitando el trabajo de los programadores. Se denominan Entorno Integrado de Desarrollo o IDE (Integrated Development Enviroment).
Las IDE pueden ser open source, de pago, profesionales o de estudio. La elección de cuál IDE utilizar dependerá de nuestro gusto y/o presupuesto.
Instalar y usar Eclipse
Aquí utilizaremos una versión portable de Eclipse. Esta herramienta es open source, no tiene coste y es de uso profesional. Además, es idéntica a la versión que se utiliza para programar en Java; lo que será una ventaja para el lector cuando decida aprender dicho lenguaje de programación.
1.1.4. Teorema de la programación estructurada
Este teorema asegura que cualquier problema informático puede resolverse mediante un algoritmo compuesto por acciones de tres tipos diferentes.
Los tres tipos de acción a los que el teorema hace referencia son:
1.Acción secuencial, también llamada acción simple.
2.Acción condicional, también llamada acción de decisión.
3.Acción iterativa, también llamada acción de repetición.
Además, todas las acciones deben tener una única entrada y salida. Pero de esto hablaremos más adelante.
Por ejemplo, al plantear el algoritmo que resuelve el problema de cruzar la calle, usamos una acción condicional para determinar si debemos cruzarla o no.
Dicho de otro modo, sólo ejecutaremos las acciones comprendidas en cruzamos si se comprueba que | |p-q|/v - |p-d|/z | es mayor que r.
1.1.4.1. Acción simple
Mostrar un mensaje en la consola, leer un dato por teclado, recordar un valor en la memoria o ejecutar una operación aritmética o lógica son todas acciones simples. De hecho, el programa que analizamos anteriormente está compuesto íntegramente de acciones simples.
Dado que ya vimos su codificación en C++, aquí analizaremos cómo representarlo mediante un diagrama.
Figura 1.2. Comparación entre dos formas de representación algorítmica: diagrama y código fuente C++
El diagrama comienza con una C (de comienzo) y finaliza con una F (de fin). Luego, con un trapecio abierto hacia abajo representamos la salida por consola.
A continuación, en un rectángulo declaramos la variable nom cuyo tipo de dato es string, y con un trapecio abierto hacia arriba representamos la introducción de datos. Finalmente, usamos una salida para mostrar el saludo.
Podemos apreciar que existe una relación directa entre el diagrama y el código fuente del programa.
1.1.4.2. Acción condicional
La acción condicional permite evaluar una expresión lógica y determinar, en función de cuál sea su valor de verdad, qué conjunto de acciones se debe ejecutar.
En el algoritmo de cómo cruzar una calle, usamos una acción condicional para determinar qué hacer: cruzar o esperar.
En el pseudocódigo que describe este algoritmo utilizamos dos acciones condicionales anidadas: si se comprueba que no vienen coches por la derecha, entonces, validamos que no vengan coches por la izquierda. Si también se comprueba esta segunda condición, entonces, cruzamos. En cualquier otro caso: esperamos.
Lo anterior podría simplificarse usando el operador lógico Y (and), así:
Veamos otro ejemplo que requiere usar una acción condicional: un programa para calcular la división entre dos valores numéricos enteros que introducirá el usuario. Debemos validar que el divisor sea diferente de cero, ya que la división por cero no está determinada.
Figura 1.3. Acción condicional: representación mediante diagrama y codificación
En C++, el operador != significa distinto (not equals). Luego, b!=0 debe leerse como b es distinto de cero. Esto puede resultar verdadero o falso dependiendo de qué valor haya introducido el usuario.
La acción condicional se codifica con la palabra if. Y tiene dos partes: if y else. Si la expresión lógica b!=0 resulta verdadera se ejecutarán las acciones que están encerradas dentro de las llaves del if. De lo contrario, se ejecutarán las acciones encerradas dentro de las llaves del else.
En el diagrama, representamos la acción condicional como un triángulo apoyado sobre dos rectángulos. En el triángulo, escribiremos la expresión lógica cuyo valor de verdad debe ser evaluado. Si dicho valor resulta verdadero se ejecutarán las acciones ubicadas en el rectángulo de la izquierda. De lo contrario, se ejecutarán las acciones colocadas en el rectángulo de la derecha.
Cabe aclarar que sólo se ejecutará uno de los dos conjuntos de acciones. El de la izquierda (el if) o el de la derecha (el else). Nunca los dos.
En este caso, el algoritmo que resuelve el problema está compuesto de varias acciones simples y una acción condicional. Incluso, dentro del if hay dos acciones simples. Dentro del else hay una única acción simple.
Analicemos otro ejemplo que requiere acciones condicionales. Se trata de una calculadora muy sencilla, donde el usuario introducirá dos valores (operandos) y un operador aritmético; el programa le mostrará el resultado de la operación.
Observemos el código del programa, luego lo analizaremos.
El programa es bastante simple, aunque el hecho de anidar acciones condicionales (un if dentro de otro if) lo puede tornar algo engorroso.
La lógica es la siguiente: comenzamos leyendo una expresión compuesta por un operando (a), un operador (op) y otro operando (b). Luego determinamos cuál es el operador en cuestión. Para esto utilizamos un if, para preguntar si se trata de la suma; en tal caso asignamos a+b a la variable resultado.
Si el operador no fue +, entonces (por else) preguntamos si fue – (resta). De ser así asignamos a-b a la variable resultado. Continuamos el proceso para determinar si el operador fue * (producto) o / (división). En este último caso, debemos comprobar que b (el segundo operando) no sea 0 (cero), ya que la división por cero no está determinada. Si no hubo error mostramos el resultado de la operación.
Utilizamos la variable error para contener sólo dos valores: 0 para indicar que no hubo error y 1 para reflejar sí lo hubo. Podríamos interpretar que 0 es falso(false) y 1 es verdadero(true). Más adelante veremos que existe el tipo de dato bool preparado, justamente, para contener estos dos valores posibles.
1.1.4.3. Acción iterativa
La acción iterativa permite repetir un conjunto de acciones mientras se compruebe una determinada expresión lógica.
Volviendo al problema de cruzar la calle, habíamos llegado a la conclusión de que cruzar implicaba bajar el borde, dar pasos hasta llegar al borde de la acera de enfrente y subir el borde.
Podríamos reformular dar pasos hasta llegar al borde de la acera de enfrente por: mientras no lleguemos al borde de la acera de enfrente, dar pasos. Así, el pseudocódigo del algoritmo lucirá del siguiente modo:
Como ejemplo de uso de la acción iterativa, analizaremos un programa que muestra por consola los primeros n números naturales (incluyendo el cero), donde n es un valor que introducirá el usuario.
Figura 1.4. Acción iterativa: representación mediante diagrama y codificación
En los diagramas omitiremos poner los mensajes (salidas) destinados al usuario, pues su objetivo es reflejar la lógica del algoritmo. La amigabilidad del programa no forma parte de su lógica.
