fundamentos de programacion 2014

SAVE OFFLINE

 

 

Facultad de Informática  Universidad Complutense        Apuntes de clase de la asignatura 

Fundamentos de la programación 

1º curso  Grado en Ingeniería en Informática  Grado en Ingeniería del Software  Grado en Ingeniería de Computadores 

2013‐2014      Luis Hernández Yáñez       

 

Licencia Creative Commons:  Reconocimiento, No comercial y Compartir igual.  http://creativecommons.org/licenses/by‐nc‐sa/3.0/ 

      Esta publicación contiene los apuntes de clase de la asignatura  Fundamentos de la programación, asignatura de 1º curso de los grados  que se imparten en la Facultad de Informática de la UCM.    Durante los tres primeros cursos en los que se ha impartido la asignatura,  este material ha sido sometido a continuas revisiones y contribuciones  por parte de los profesores que han impartido los distintos grupos  de la asignatura. Aunque el trabajo ha quedado bastante consolidado,  estoy seguro de que todavía contiene muchas erratas. Si encuentras alguna,  no dudes, por favor, en hacérmelo saber y conseguir así  que la siguiente versión esté mejor depurada.    Quiero agradecer a todos los profesores que han impartido la asignatura  su contribución en el desarrollo del material, destacando especialmente  la labor de Pablo Moreno Ger y Carlos Cervigón Rückauer.    Luis Hernández Yáñez  Profesor de la Facultad de Informática de la UCM 

Fundamentos de la programación

TC Grado en Ingeniería Informática Grado en Ingeniería del Software Grado en Ingeniería de Computadores Luis Hernández Yáñez

Facultad de Informática Universidad Complutense

Luis Hernández Yáñez

Tema 1 Tema 2

Computadoras y programación Tipos e instrucciones I Anexo: Detalles técnicos de los tipos Tema 3 Tipos e instrucciones II Anexo I: El operador ternario ? Anexo II: Ejemplos de secuencias Tema 4 La abstracción procedimental Anexo: Más sobre subprogramas Tema 5 Tipos de datos estructurados Anexo: Cadenas al estilo de C Tema 6 Recorrido y búsqueda en arrays Tema 7 Algoritmos de ordenación Anexo: Más sobre ordenación Tema 8 Programación modular Anexo: Ejemplo de modularización Tema 9 Punteros y memoria dinámica Anexo: Punteros y memoria dinámica Tema 10 Introducción a la recursión Apéndice: Archivos binarios Fundamentos de la programación

1 48 212 225 398 402 425 496 512 580 588 649 742 755 832 847 938 981 1049

3 12 15 19 24 27 30 35 39 45

Luis Hernández Yáñez

Informática, computadoras y programación Lenguaje máquina y ensamblador Lenguajes de programación de alto nivel Un poco de historia Programación e Ingeniería del Software El lenguaje de programación C++ Sintaxis de los lenguajes de programación  Un primer programa en C++ Herramientas de desarrollo C++: Un mejor C

Luis Hernández Yáñez

Fundamentos de la programación

Un ejemplo de programación El primer programa en C++ Las líneas de código del programa Cálculos en los programas Variables Expresiones Lectura de datos desde el teclado Resolución de problemas Los datos de los programas Identificadores Tipos de datos Declaración y uso de variables Instrucciones de asignación Operadores Más sobre expresiones Constantes La biblioteca cmath Operaciones con caracteres

Fundamentos de la programación

50 64 80 86 92 98 108 119 127 129 133 142 147 152 160 167 171 174

Operadores relacionales Toma de decisiones (if) Bloques de código Bucles (while) Entrada/salida por consola Funciones definidas por el programador

177 180 183 186 190 199

214 216 217 218 220 221 222 223

Luis Hernández Yáñez

int float Notación científica double char bool string Literales con especificación de tipo

Luis Hernández Yáñez

Fundamentos de la programación

Tipos, valores y variables Conversión de tipos Tipos declarados por el usuario Tipos enumerados Entrada/Salida con archivos de texto Lectura de archivos de texto Escritura en archivos de texto Flujo de ejecución Selección simple Operadores lógicos Anidamiento de if Condiciones Selección múltiple La escala if‐else‐if La instrucción switch Repetición El bucle while

Fundamentos de la programación

227 232 236 238 248 253 266 272 276 282 286 290 293 295 302 313 316

El bucle for Bucles anidados Ámbito y visibilidad Secuencias Recorrido de secuencias Secuencias calculadas Búsqueda en secuencias Arrays de datos simples Uso de variables arrays Recorrido de arrays Búsqueda en arrays Arrays no completos

321 331 339 349 355 363 370 374 379 382 387 393

399

Recorridos Un aparcamiento ¿Paréntesis bien emparejados? ¿Dos secuencias iguales? Números primos menores que N Búsquedas Búsqueda de un número en un archivo Búsquedas en secuencias ordenadas

404 405 409 412 413 417 419 420

Luis Hernández Yáñez

El operador ternario ?

Fundamentos de la programación

Luis Hernández Yáñez

Diseño descendente: Tareas y subtareas  Subprogramas Subprogramas y datos Parámetros Argumentos Resultado de la función Prototipos Ejemplos completos Funciones de operador Diseño descendente (un ejemplo) Precondiciones y postcondiciones

Fundamentos de la programación

427 434 441 446 451 467 473 475 477 480 490

498 501 504 508

Luis Hernández Yáñez

Archivos como parámetros La función main() Argumentos implícitos Sobrecarga de subprogramas

Luis Hernández Yáñez

Fundamentos de la programación: La abstracción procedimental (Anexo)

Tipos de datos Arrays de nuevo Arrays y bucles for Más sobre arrays Inicialización de arrays Enumerados como índices Paso de arrays a subprogramas Implementación de listas Cadenas de caracteres Cadenas de caracteres de tipo string Entrada/salida con string Operaciones con string Estructuras Estructuras dentro de estructuras Arrays de estructuras Arrays dentro de estructuras Listas de longitud variable Un ejemplo completo El bucle do..while Fundamentos de la programación

514 517 520 522 523 524 525 528 531 535 539 541 543 549 550 551 552 558 562

582 583 584 585

Luis Hernández Yáñez

Cadenas al estilo de C E/S con cadenas al estilo de C La biblioteca cstring Ejemplo

Luis Hernández Yáñez

Fundamentos de la programación

Recorrido de arrays Arrays completos Arrays no completos con centinela Arrays no completos con contador Ejemplos Generación de números aleatorios Búsquedas en arrays Arrays completos Arrays no completos con centinela Arrays no completos con contador Ejemplo Recorridos y búsquedas en cadenas Más ejemplos de manejo de arrays Arrays multidimensionales Inicialización de arrays multidimensionales Recorrido de un array bidimensional Recorrido de un array N‐dimensional Búsqueda en un array multidimensional

Fundamentos de la programación

590 593 594 595 597 601 604 606 607 608 610 614 617 630 638 641 644 647

651 654 665 672 680 688 692 694 701 716 722 729 731

Luis Hernández Yáñez

Algoritmos de ordenación Algoritmo de ordenación por inserción Ordenación de arrays por inserción Algoritmo de ordenación por inserción con intercambios Claves de ordenación Estabilidad de la ordenación Complejidad y eficiencia Ordenaciones naturales Ordenación por selección directa Método de la burbuja Listas ordenadas Búsquedas en listas ordenadas Búsqueda binaria

Fundamentos de la programación

Luis Hernández Yáñez

Ordenación por intercambio Mezcla de dos listas ordenadas

Fundamentos de la programación

744 747

Luis Hernández Yáñez

Programas multiarchivo y compilación separada  Interfaz frente a implementación Uso de módulos de biblioteca Ejemplo: Gestión de una lista ordenada I Compilación de programas multiarchivo El preprocesador Cada cosa en su módulo Ejemplo: Gestión de una lista ordenada II El problema de las inclusiones múltiples Compilación condicional Protección frente a inclusiones múltiples Ejemplo: Gestión de una lista ordenada III Implementaciones alternativas Espacios de nombres Implementaciones alternativas Calidad y reutilización del software

757 762 768 770 778 780 782 784 789 794 795 796 804 808 817 827

Fundamentos de la programación

Luis Hernández Yáñez

Modularización de  un programa

Fundamentos de la programación

833

Luis Hernández Yáñez

Direcciones de memoria y punteros Operadores de punteros Punteros y direcciones válidas Punteros no inicializados Un valor seguro: NULL Copia y comparación de punteros Tipos puntero Punteros a estructuras Punteros a constantes y punteros constantes Punteros y paso de parámetros Punteros y arrays Memoria y datos del programa Memoria dinámica Punteros y datos dinámicos Gestión de la memoria Errores comunes Arrays de datos dinámicos Arrays dinámicos

849 854 864 866 867 868 873 875 877 879 883 886 891 895 907 911 916 928

Fundamentos de la programación

Luis Hernández Yáñez

Aritmética de punteros Recorrido de arrays con punteros Referencias Listas enlazadas

Fundamentos de la programación

940 953 962 964

Luis Hernández Yáñez

Concepto de recursión Algoritmos recursivos Funciones recursivas Diseño de funciones recursivas Modelo de ejecución La pila del sistema La pila y las llamadas a función Ejecución de la función factorial() Tipos de recursión Recursión simple Recursión múltiple Recursión anidada Recursión cruzada Código del subprograma recursivo Parámetros y recursión Ejemplos de algoritmos recursivos Búsqueda binaria Torres de Hanoi Recursión frente a iteración Estructuras de datos recursivas

983 986 987 989 990 992 994 1005 1018 1019 1020 1022 1026 1027 1032 1034 1035 1038 1043 1045

Fundamentos de la programación

Luis Hernández Yáñez

Flujos Archivos binarios Tamaño de los datos: El operador sizeof() Apertura de archivos binarios Lectura de archivos binarios (acceso secuencial) Escritura en archivos binarios (acceso secuencial) Acceso directo o aleatorio Ejemplos de uso de archivos binarios Ordenación de los registros del archivo Búsqueda binaria Inserción en un archivo binario ordenado Carga de los registro de un archivo en una tabla Almacenamiento de una tabla en un archivo

Fundamentos de la programación

1051 1054 1056 1059 1061 1066 1070 1078 1079 1085 1088 1092 1093

Fundamentos de la programación

RB Grado en Ingeniería Informática Grado en Ingeniería del Software Grado en Ingeniería de Computadores Luis Hernández Yáñez

Facultad de Informática Universidad Complutense

 Programming. Principles and Practice Using C++ B. Stroustrup. Pearson Education, 2009  C++: An Introduction to Computing (2ª edición) J. Adams, S. Leestma, L. Nyhoff. Prentice Hall, 1998  El lenguaje de programación C++ (Edición especial) B. Stroustrup. Addison‐Wesley, 2002

Luis Hernández Yáñez

 Programación y resolución de problemas con C++ N. Dale, C. Weems. McGraw‐Hill Interamericana, 2007  Problem Solving, Abstraction, Design Using C++ (3ª edición) F.L. Friedman, E.B. Koffman. Addison‐Wesley, 2000.  Programación en C++ para ingenieros F. Xhafa et al. Thomson, 2006 Fundamentos de la programación

Programming. Principles and Practice Using C++ Del autor del lenguaje C++, un amplio tutorial que enseña a programar en C++; hace un uso temprano de conceptos de orientación a objetos y de la STL, que quedan fuera del temario de este curso

C++: An Introduction to Computing (2ª edición) Buena introducción a la programación en C++; buena organización de los contenidos, bien desarrollado y con secciones prácticas

Luis Hernández Yáñez

El lenguaje de programación C++ (Edición especial) Del autor del lenguaje C++, la referencia absoluta sobre el lenguaje C++ en la que consultar dudas y detalles técnicos sobre los elementos del lenguaje

Fundamentos de la programación

Programación y resolución de problemas con C++ Un enfoque práctico al desarrollo de programas con C++ con numerosos ejemplos

Problem Solving, Abstraction, Design Using C++ (3ª edición) Introducción a la programación en C++ con un enfoque de desarrollo de software y numerosos casos de estudio

Programación en C++ para ingenieros

Luis Hernández Yáñez

Introducción a la programación en C++ con explicaciones sencillas y una organización clara

Fundamentos de la programación

Fundamentos de la programación

1 Grado en Ingeniería Informática Grado en Ingeniería del Software Grado en Ingeniería de Computadores Luis Hernández Yáñez

Facultad de Informática Universidad Complutense

Luis Hernández Yáñez

Informática, computadoras y programación Lenguaje máquina y ensamblador Lenguajes de programación de alto nivel Un poco de historia Programación e Ingeniería del Software El lenguaje de programación C++ Sintaxis de los lenguajes de programación  Un primer programa en C++ Herramientas de desarrollo C++: Un mejor C

Fundamentos de la programación: Computadoras y programación

3 12 15 19 24 27 30 35 39 45

Luis Hernández Yáñez

Fundamentos de la programación: Computadoras y programación

Página 3

Informática (Ciencia de la computación) Conjunto de conocimientos científicos y técnicas que hacen posible el tratamiento automático de la información por medio de ordenadores

Luis Hernández Yáñez

Computadora Máquina electrónica, analógica o digital, dotada de una memoria de gran capacidad y de métodos de tratamiento de la información, capaz de resolver problemas matemáticos y lógicos mediante la ejecución de programas informáticos

Fundamentos de la programación: Computadoras y programación

Página 4

Luis Hernández Yáñez

En todas partes y con muchas formas

Fundamentos de la programación: Computadoras y programación

Página 5

Hardware Componentes que integran la parte material de una computadora

Luis Hernández Yáñez

Software Programas, instrucciones y reglas informáticas para ejecutar tareas en una computadora

Fundamentos de la programación: Computadoras y programación

Página 6

Programar Indicar a la computadora qué es lo que tiene que hacer

Programa

Luis Hernández Yáñez

 Secuencia de instrucciones  Instrucciones que entiende la computadora  Y que persiguen un objetivo: ¡resolver un problema!

Fundamentos de la programación: Computadoras y programación

Luis Hernández Yáñez

Parque Jurásico

Fundamentos de la programación: Computadoras y programación

Página 7

Trabajo en equipo Múltiples roles...  Gestores  Analistas  Diseñadores  Programadores  Probadores  Administradores de sistemas ...

Página 8

Esquema general Memoria temporal Unidad Central de Proceso Central Processor Unit

Luis Hernández Yáñez

Dispositivos de entrada Teclado Ratón Escáner Táctil …

Dispositivos de salida

C.P.U.

Almacenamiento permanente

Fundamentos de la programación: Computadoras y programación

Monitor Impresora Altavoz …

Página 9

La arquitectura de Von Neumann Dispositivos de E/S

Una ALU de 2 bits (Wikipedia)

C.P.U. (Procesador)

Luis Hernández Yáñez

A.L.U. Unidad Aritmético‐Lógica

Memoria

Unidad de Control

Fundamentos de la programación: Computadoras y programación

Página 10

La memoria Memoria

Cada celda en una dirección

01

Celdas de 8 / 16 / 32 / 64 bits

02

Información volátil

03 04

Bus  de  datos

05 06 07 08

Dirección

210 = 1024  1000

Fundamentos de la programación: Computadoras y programación

Página 11

Fundamentos de la programación: Computadoras y programación

Página 12

Luis Hernández Yáñez

Luis Hernández Yáñez

. . .

1 Bit = 0 / 1 1 Byte = 8 bits = 1 carácter 1 Kilobyte (KB) = 1024 Bytes 1 Megabyte (MB) = 1024 KB 1 Gigabyte (GB) = 1024 MB 1 Terabyte (TB) = 1024 GB 1 Petabyte (PB) = 1024 TB

Los procesadores trabajan con ceros y unos (bits) Unidad de memoria básica: Byte (8 bits) (2 dígitos hexadecimales: 01011011  0101 1011  5B)

Lenguaje máquina Códigos hexadecimales que representan instrucciones, registros de la CPU, direcciones de memoria o datos Lenguaje de bajo nivel

Luis Hernández Yáñez

Instrucción Significado A0 2F 3E 01 A0 30 3E 02 1D B3 31

Acceder a la celda de memoria 2F Dependiente de la máquina Programación difícil Copiarlo el registro 1 de la ALU Acceder a la celda de memoria 30 Copiarlo en el registro 2 de la ALU Sumar Guardar el resultado en la celda de memoria 31

Fundamentos de la programación: Computadoras y programación

Página 13

Nemotécnicos para los códigos hexadecimales: A0  READ   3E  REG   1D  ADD   … Mayor legibilidad: READ 2F REG 01  READ 30 REG 02  ADD    WRITE 31 Luis Hernández Yáñez

Lenguaje de nivel medio

Código fuente (lenguaje ensamblador) Programa ensamblador

Código objeto (lenguaje máquina)

Fundamentos de la programación: Computadoras y programación

Página 14

Luis Hernández Yáñez

Fundamentos de la programación: Computadoras y programación

Página 15

Luis Hernández Yáñez

 Más cercanos a los lenguajes natural y matemático resultado = dato1 + dato2;  Mayor legibilidad, mayor facilidad de codificación  Estructuración de datos / abstracción procedimental

Fundamentos de la programación: Computadoras y programación

Página 16

Traducción

#include  using namespace std;

Código fuente

int main() { cout