PDF de programación - Algoritmia

Algoritmia

Índice de contenido
Bloque 1: Principios de programación.................................................................................................3
1.1 Introducción...............................................................................................................................3
1.1.1 Conceptos fundamentales...................................................................................................3
1.1.2 Ingeniería del software.......................................................................................................3
1.2 Abstracción ...............................................................................................................................3
1.3 Resolución de problemas de programación...............................................................................3
1.4 Herramientas para la resolución de problemas..........................................................................4
1.4.1 Diseño descendente............................................................................................................4
1.4.2 Abstracción procedimental.................................................................................................4
1.4.3 Abstracción de datos..........................................................................................................4
1.4.4 Ocultación de la información.............................................................................................5
1.5 Factores de calidad del software ...............................................................................................5
1.6 El ciclo de vida del software .....................................................................................................5
1.6.1 Fases del ciclo de vida del software...................................................................................6
1.7 Conceptos básicos sobre verificación........................................................................................8
1.8 Principios de diseño de sistemas de software............................................................................8
1.8.1 Modularidad mediante diseño descendente.......................................................................8
1.8.2 Abstracción.........................................................................................................................9
1.8.3 Ocultación de la información.............................................................................................9
1.8.4 Modificabilidad..................................................................................................................9
1.8.5 Comprensibilidad y fiabilidad............................................................................................9
1.8.6 Interfaces de usuario. Interfaz Hombre Máquina (IHM).................................................10
1.8.7 Programación segura contra fallos...................................................................................10
1.8.8 Facilidad de uso...............................................................................................................10
1.8.9 Eficiencia..........................................................................................................................11
1.8.10 Estilo de programación...................................................................................................11
1.9 Depuración...............................................................................................................................14
1.10 Diseño de algoritmos.............................................................................................................15
1.11 Resumen.................................................................................................................................15
Bloque 2: Algoritmos. Técnicas de diseño y análisis.........................................................................17
2.1 Introducción.............................................................................................................................17
2.2 Conceptos básicos....................................................................................................................19
2.2.1 Problemas y ejemplares...................................................................................................19
2.2.2 La eficiencia de los algoritmos .......................................................................................20
2.2.3 Operación elemental.........................................................................................................23
2.2.4 Especificación de un algoritmo........................................................................................23
2.3 Notación asintótica..................................................................................................................24
2.3.1 Introducción.....................................................................................................................24
2.3.2 La notación “el orden de”................................................................................................24
2.3.3 La notación Omega..........................................................................................................25
2.3.4 La notación Theta ............................................................................................................26
2.3.5 La notación asintótica condicional...................................................................................26
2.4 Análisis de algoritmos..............................................................................................................27
2.5 Algoritmos de búsqueda...........................................................................................................31
2.5.1 Búsqueda secuencial........................................................................................................31
2.5.2 Búsqueda binaria..............................................................................................................32

Juan Manuel Zamarreño Pérez

Pagina 1 de 81

1º ITIS

2.6 Algoritmos de ordenación........................................................................................................33
2.6.1 Ordenación por burbuja...................................................................................................33
2.6.2 Ordenación por selección.................................................................................................34
2.6.3 Ordenación por inserción.................................................................................................36
2.6.4 Inserción binaria...............................................................................................................38
2.6.5 Algoritmo Shellsort (Donald Shell).................................................................................39
2.6.6 Ordenación rápida o Quick Sort (C. H. Hoare)................................................................40
2.6.7 Ordenación por fusión......................................................................................................43
2.6.8 Algoritmos de ordenación por distribución: Radix Sort..................................................45
2.7 Técnicas recursivas..................................................................................................................49
2.8 Resumen...................................................................................................................................59
Bloque III: Tipos Abstractos de Datos................................................................................................61
3.1 Introducción.............................................................................................................................61
3.2 Listas .......................................................................................................................................67
3.2.1 Nivel Abstracto................................................................................................................67
3.2.2 Nivel de Representación o de Implementación................................................................69
3.3 Pilas..........................................................................................................................................76
3.3.1 Nivel Abstracto................................................................................................................76
3.3.1 Nivel de Representación o de Implementación................................................................77
3.4 Colas .......................................................................................................................................78
3.4.1 Nivel Abstracto................................................................................................................78
3.4.2 Nivel de Representación o de Implementación ...............................................................79
3.4 Resumen...................................................................................................................................80

Pagina 2 de 81

Juan Manuel Zamarreño Pérez

Algoritmia

Bloque 1: Principios de programación

1.1 Introducción

1.1.1 Conceptos fundamentales

– Abstracción
– Modularidad
– Principio de ocultación de la información

1.1.2 Ingeniería del software
– Ciclo de vida del software
– Técnicas de apoyo para las diferentes etapas del ciclo de vida
(análisis, diseño, etc.)
– Documentación:
• Interna
• Externa

1.2 Abstracción

– Proceso de exclusión de detalles no deseados o no significativos al problema que se trata de

resolver .

– Esto se realiza mediante diferentes niveles en los cuales los mas altos contiene mayor

generalización y menor detalle y según ascendemos disminuye la generalización y aumenta