Programacion Iii
Páginas: 83 (20562 palabras)
Publicado: 6 de febrero de 2013
Asignatura: Programación III Curso 2º de Ingeniería Técnica Informática (Sistemas). Pedro Pérez Ostiz Tudela.- Septiembre 2002.
Programación III
2
Pedro Pérez Ostiz.- Tudela
Índice
1..................................................... 1.- PRELIMINARES .................................................... 5
1.1 Introducción..................................................................... 5 1.2 ¿Qué es un algoritmo?. ................................................... 5 1.3 Notación para los programas .......................................... 6 1.4 Notación matemática ....................................................... 6 1.5 Técnica de demostración 1: CONTRADICCIÓN.............. 6 1.6 Técnica de demostración 2: INDUCCIÓN MATEMÁTICA6 1.7Recordatorios................................................................... 7
5.................................. 5.- ESTRUCTURAS DE DATOS ................................. 21
5.1 Matrices (Arrays), Pilas y Colas. ................................... 21 5.2 Registros y punteros (apuntadores). ............................ 22 5.3 Listas.............................................................................. 22 5.4 Grafos ............................................................................. 23 5.5 Árboles............................................................................ 24 5.6 Tablas asociativas.......................................................... 25 5.7 Montículos (heaps)......................................................... 26 5.8 Montículosbinominales................................................. 28 5.9 Estructuras de conjuntos disjuntos (partición)............ 28
2..................................... 2.- ALGORITMIA ELEMENTAL .................................... 8
2.1 Introducción. .................................................................... 8 2.2 Problemas y ejemplares. ................................................. 8 2.3La eficiencia de los algoritmos........................................ 8 2.4 Análisis de “caso medio” y “caso peor”. ....................... 9 2.5 ¿Qué es una operación elemental?................................. 9 2.6 ¿Por qué hay que buscar la eficiencia?........................ 10 2.7 Ejemplos ......................................................................... 10 2.8 ¿Cuándo quedaespecificado un algoritmo?................ 11
6..................................... 6.- ALGORITMOS VORACES .................................... 29
6.1 Dar la vuelta (1). ............................................................. 29 6.2 Características generales de los algoritmos voraces.. 29 6.3 Grafos: Árboles de recubrimiento mínimo ................... 31 6.4 Grafos: Caminosmínimos............................................. 33 6.5 El problema de la mochila (1). ....................................... 34 6.6 Planificación ................................................................... 35
3.ASINTÓTICA................................ ..................................... 3.- NOTACIÓN ASINTÓTICA..................................... 12
3.1 Introducción................................................................... 12 3.2 Una notación para “EL ORDEN DE”.............................. 12 3.3 Otra notación asintótica ................................................ 13 3.4 Notación asintótica condicional.................................... 14 3.5 Notación asintótica con varios parámetros.................. 14 3.6 Operaciones sobre notaciónasintótica........................ 14
7.......................................... 7.- DIVIDE Y VENCERÁS. ......................................... 37
7.1 Introducción: Multiplicación de enteros muy grandes 37 7.2 El caso general............................................................... 37 7.3 Búsqueda binaria. .......................................................... 39 7.4 Ordenación...
Programación III
2
Pedro Pérez Ostiz.- Tudela
Índice
1..................................................... 1.- PRELIMINARES .................................................... 5
1.1 Introducción..................................................................... 5 1.2 ¿Qué es un algoritmo?. ................................................... 5 1.3 Notación para los programas .......................................... 6 1.4 Notación matemática ....................................................... 6 1.5 Técnica de demostración 1: CONTRADICCIÓN.............. 6 1.6 Técnica de demostración 2: INDUCCIÓN MATEMÁTICA6 1.7Recordatorios................................................................... 7
5.................................. 5.- ESTRUCTURAS DE DATOS ................................. 21
5.1 Matrices (Arrays), Pilas y Colas. ................................... 21 5.2 Registros y punteros (apuntadores). ............................ 22 5.3 Listas.............................................................................. 22 5.4 Grafos ............................................................................. 23 5.5 Árboles............................................................................ 24 5.6 Tablas asociativas.......................................................... 25 5.7 Montículos (heaps)......................................................... 26 5.8 Montículosbinominales................................................. 28 5.9 Estructuras de conjuntos disjuntos (partición)............ 28
2..................................... 2.- ALGORITMIA ELEMENTAL .................................... 8
2.1 Introducción. .................................................................... 8 2.2 Problemas y ejemplares. ................................................. 8 2.3La eficiencia de los algoritmos........................................ 8 2.4 Análisis de “caso medio” y “caso peor”. ....................... 9 2.5 ¿Qué es una operación elemental?................................. 9 2.6 ¿Por qué hay que buscar la eficiencia?........................ 10 2.7 Ejemplos ......................................................................... 10 2.8 ¿Cuándo quedaespecificado un algoritmo?................ 11
6..................................... 6.- ALGORITMOS VORACES .................................... 29
6.1 Dar la vuelta (1). ............................................................. 29 6.2 Características generales de los algoritmos voraces.. 29 6.3 Grafos: Árboles de recubrimiento mínimo ................... 31 6.4 Grafos: Caminosmínimos............................................. 33 6.5 El problema de la mochila (1). ....................................... 34 6.6 Planificación ................................................................... 35
3.ASINTÓTICA................................ ..................................... 3.- NOTACIÓN ASINTÓTICA..................................... 12
3.1 Introducción................................................................... 12 3.2 Una notación para “EL ORDEN DE”.............................. 12 3.3 Otra notación asintótica ................................................ 13 3.4 Notación asintótica condicional.................................... 14 3.5 Notación asintótica con varios parámetros.................. 14 3.6 Operaciones sobre notaciónasintótica........................ 14
7.......................................... 7.- DIVIDE Y VENCERÁS. ......................................... 37
7.1 Introducción: Multiplicación de enteros muy grandes 37 7.2 El caso general............................................................... 37 7.3 Búsqueda binaria. .......................................................... 39 7.4 Ordenación...
Leer documento completo
Regístrate para leer el documento completo.