Ver esquema

Tema 25. Diseño de algoritmos. Técnicas descriptivas.

Temario oficial estatal de referencia — especialidad Sistemas y Aplicaciones Informáticas (código 227), Cuerpo de Profesores Técnicos de Formación Profesional · Índice oficial del Orden de 1 de febrero de 1996 por la que se aprueban los temarios que han de regir en los procedimientos de ingreso, adquisición de nuevas especialidades y movilidad para determinadas especialidades de los Cuerpos de Profesores de Enseñanza Secundaria y de Profesores Técnicos de Formación Profesional (BOE núm. 38, de 13 de febrero de 1996, BOE-A-1996-3102) — Anexo correspondiente al Cuerpo de Profesores Técnicos de Formación Profesional (0591), especialidad Sistemas y Aplicaciones Informáticas (código 227). Este temario de 1996 sigue vigente hoy como temario de referencia estatal: las convocatorias autonómicas actuales (2023-2026) de esta especialidad remiten expresamente a él como Anexo de contenidos, sin que haya sido derogado ni sustituido por una lista de temas distinta..

Este temario corresponde en exclusiva a la especialidad 'Sistemas y Aplicaciones Informáticas' (código 227) del Cuerpo de Profesores Técnicos de Formación Profesional (Cuerpo 0591), y es la única entrada de esta especialidad en el catálogo de OpositaGratis, con id 'profesor-fp-informatica'. No debe confundirse con la especialidad 'Informática' (código 107) del Cuerpo de Profesores de Enseñanza Secundaria (Cuerpo 0590, grupo A, exige otro temario propio y distinto requisito de titulación), ni con otras especialidades de FP con contenido parcialmente afín como 'Sistemas Electrónicos' o 'Equipos Electrónicos', que tampoco comparten este temario. Los 65 temas oficiales de 1996 versan sobre fundamentos de hardware y arquitectura de computadores, representación y organización de datos, sistemas operativos, programación (algoritmia, estructurada, modular, orientada a objetos, C y ensamblador), bases de datos relacionales y aplicaciones de gestión, diseño de interfaces gráficas y sistemas multimedia, y redes de ordenadores. Dado que el temario data de 1996, el contenido técnico de cada tema se ha actualizado a la práctica y la tecnología vigentes en 2026 (arquitecturas de 64 bits y multinúcleo, SSD/NVMe, sistemas operativos y lenguajes de programación actuales, redes Wi-Fi 6/7 y computación en la nube, entre otros) sin alterar el enunciado oficial de ningún tema, siguiendo el mismo criterio aplicado en el resto de temarios de Profesores Técnicos de FP ya publicados en este catálogo (p. ej. src/data/temarios/profesor-fp.json, especialidad Procesos Sanitarios).

Un algoritmo es una secuencia finita, ordenada y no ambigua de pasos que resuelve un problema o realiza una tarea determinada, independiente del lenguaje de programación en que finalmente se implemente. Este tema estudia las propiedades que debe cumplir todo buen algoritmo, las técnicas descriptivas para representarlo antes de codificarlo -pseudocódigo, diagramas de flujo y diagramas de Nassi-Shneiderman-, las principales estrategias de diseño (divide y vencerás, algoritmos voraces, programación dinámica y vuelta atrás), las técnicas básicas de verificación manual y los criterios para analizar su eficiencia mediante la notación asintótica.

← Ver el índice completo del temario

Propiedades de un algoritmo

Debe ser finito (termina tras un número finito de pasos), definido (cada paso está especificado sin ambigüedad), tener entradas (cero o más datos iniciales), salidas (uno o más resultados relacionados con las entradas) y ser efectivo (cada paso debe poder realizarse en un tiempo finito con los recursos disponibles, es decir, debe ser suficientemente básico como para ejecutarse). A estas cinco propiedades clásicas conviene añadir la generalidad: un buen algoritmo resuelve toda una clase de problemas (p. ej. «ordenar cualquier lista de números»), no un único caso particular con valores fijos.

Pseudocódigo

Es una descripción del algoritmo en lenguaje semiformal, cercano al natural pero con estructuras de control explícitas (si-entonces-sino, mientras, para, hacer-mientras) y sin la sintaxis estricta de un lenguaje de programación concreto; facilita diseñar la lógica del algoritmo antes de comprometerse con un lenguaje específico y es independiente de la implementación final. No existe un estándar único de pseudocódigo: cada autor o institución fija sus propias convenciones de palabras clave y sangrado, por lo que lo esencial es la claridad y la coherencia interna del texto, no ajustarse a una norma concreta.

Diagramas de flujo (flowcharts)

Representación gráfica del algoritmo mediante símbolos normalizados: óvalo (inicio/fin), rectángulo (proceso/acción), rombo (decisión, con dos o más salidas), paralelogramo (entrada/salida de datos) y flechas que indican el flujo de control entre los distintos pasos. Son especialmente útiles para visualizar la lógica de control, aunque para algoritmos complejos pueden volverse difíciles de mantener frente al pseudocódigo, y su mayor inconveniente es que permiten dibujar saltos arbitrarios entre cualquier par de símbolos, lo que puede dar lugar a diagramas con un flujo de control tan enredado como el del código espagueti que la programación estructurada trata de evitar.

Diagramas de Nassi-Shneiderman

Son una alternativa a los diagramas de flujo clásicos, propuesta en los años setenta, que representa el algoritmo mediante cajas anidadas unas dentro de otras, sin ninguna flecha: la secuencia se dibuja como cajas apiladas verticalmente, la selección como una caja dividida en dos o más ramas, y la iteración como una caja envolvente que contiene el cuerpo del bucle. Al no existir flechas, resulta estructuralmente imposible representar un salto incondicional (goto) o un flujo de control desordenado, por lo que estos diagramas obligan por construcción a ceñirse a las reglas de la programación estructurada (secuencia, selección e iteración), a costa de ser menos flexibles para describir casos muy irregulares.

Estructuras de control básicas

Secuencial (los pasos se ejecutan uno tras otro en el orden escrito), condicional o selectiva (bifurca el flujo según se cumpla o no una condición: si-entonces, si-entonces-sino, según-casos/switch) y repetitiva o iterativa (repite un bloque de instrucciones mientras se cumpla una condición: mientras/while, hacer-mientras/do-while, para/for). El teorema del programa estructurado demuestra que cualquier algoritmo puede expresarse combinando únicamente estas tres estructuras, sin necesidad de saltos incondicionales (goto).

Estrategias de diseño de algoritmos

Divide y vencerás descompone el problema en subproblemas más pequeños del mismo tipo, los resuelve (recursivamente, hasta un caso trivial) y combina sus soluciones para obtener la solución global (ejemplos: búsqueda binaria, mergesort, quicksort). Los algoritmos voraces (greedy) construyen la solución tomando en cada paso la decisión que parece localmente óptima, sin reconsiderarla después, lo que es eficiente pero solo garantiza la solución óptima global en problemas con la propiedad de elección voraz (ejemplo: el algoritmo de Dijkstra de caminos mínimos, o la codificación de Huffman). La programación dinámica resuelve problemas con subproblemas solapados almacenando (memoizando) los resultados intermedios ya calculados para no repetir trabajo, siendo útil cuando el problema cumple el principio de optimalidad de Bellman. La vuelta atrás (backtracking) explora sistemáticamente un espacio de soluciones candidatas, abandonando (podando) una rama en cuanto se comprueba que no puede llevar a una solución válida, típica en problemas combinatorios como el de las n-reinas o el laberinto.

Verificación manual de algoritmos: prueba de mesa e invariantes

La prueba de mesa (desk-check) consiste en ejecutar el algoritmo a mano, sobre papel, anotando en una tabla el valor de cada variable tras cada paso o iteración, para comprobar que el comportamiento observado coincide con el esperado antes de programarlo; es la técnica de verificación más elemental y la primera línea de defensa frente a errores de lógica. Un invariante de bucle es una condición o propiedad que es verdadera antes de la primera iteración, se mantiene verdadera tras cada iteración y, combinada con la condición de salida, permite demostrar formalmente que el bucle produce el resultado correcto al terminar; es la base del razonamiento riguroso sobre la corrección de algoritmos iterativos, análogo al principio de inducción matemática aplicado paso a paso.

Análisis de eficiencia: notación asintótica

La notación Big O (O grande) describe el crecimiento del tiempo de ejecución o del espacio de memoria de un algoritmo en función del tamaño de la entrada (n), habitualmente en el peor caso, cuando n tiende a infinito; las clases de complejidad más habituales, de menor a mayor coste, son O(1) constante, O(log n) logarítmica, O(n) lineal, O(n log n) lineal-logarítmica, O(n²) cuadrática, O(2^n) exponencial y O(n!) factorial. Junto a Big O (cota superior) existen también la notación Ω (omega, cota inferior, mejor caso) y Θ (theta, cota ajustada cuando la cota superior e inferior coinciden en orden de crecimiento), aunque en la práctica de oposición y de ingeniería del software se emplea casi siempre Big O por ser la más relevante para anticipar el comportamiento en el caso más desfavorable.

Ideas clave para el examen — memoriza esto

  • Un algoritmo debe ser finito: debe terminar tras un número finito de pasos, no puede ejecutarse indefinidamente.
  • Un algoritmo debe ser definido: cada paso debe estar especificado de forma precisa y sin ambigüedad, interpretable de una única manera.
  • Un algoritmo puede tener cero o más entradas, pero debe producir al menos una salida relacionada con ellas.
  • La propiedad de efectividad exige que cada paso del algoritmo sea lo bastante básico como para poder ejecutarse en un tiempo finito con los recursos disponibles.
  • La generalidad es la propiedad por la cual un algoritmo resuelve toda una clase de problemas, no un único caso concreto con valores fijos.
  • El pseudocódigo describe la lógica del algoritmo en lenguaje semiformal, independiente de la sintaxis de cualquier lenguaje de programación concreto, sin que exista un estándar único obligatorio.
  • Los diagramas de flujo usan símbolos normalizados: óvalo para inicio/fin, rectángulo para proceso, rombo para decisión, paralelogramo para entrada/salida.
  • El rombo de decisión en un diagrama de flujo tiene siempre al menos dos flechas de salida, correspondientes a las distintas ramas posibles de la condición evaluada.
  • Los diagramas de Nassi-Shneiderman representan el algoritmo mediante cajas anidadas sin ninguna flecha, lo que impide por construcción representar saltos incondicionales (goto).
  • En un diagrama de Nassi-Shneiderman, la iteración se dibuja como una caja envolvente que contiene el cuerpo del bucle, y la selección como una caja dividida en ramas.
  • Las tres estructuras de control básicas son: secuencial, condicional (selectiva) y repetitiva (iterativa).
  • El teorema del programa estructurado demuestra que cualquier algoritmo puede expresarse combinando solo secuencia, selección e iteración, sin necesidad de saltos incondicionales (goto).
  • La estructura while (mientras) evalúa la condición ANTES de ejecutar el bloque, por lo que puede no ejecutarse ninguna vez si la condición es falsa desde el inicio.
  • La estructura do-while (hacer-mientras) evalúa la condición DESPUÉS de ejecutar el bloque, garantizando que este se ejecuta al menos una vez.
  • Divide y vencerás descompone un problema en subproblemas más pequeños del mismo tipo, los resuelve por separado y combina sus soluciones; la búsqueda binaria y el mergesort son ejemplos clásicos.
  • Un algoritmo voraz (greedy) toma en cada paso la decisión localmente óptima sin reconsiderarla, lo que no garantiza la solución globalmente óptima salvo en problemas con la propiedad de elección voraz.
  • La programación dinámica evita recalcular subproblemas solapados almacenando (memoizando) sus resultados intermedios, aplicable cuando el problema cumple el principio de optimalidad de Bellman.
  • La vuelta atrás (backtracking) explora un espacio de soluciones candidatas podando las ramas que no pueden llevar a una solución válida, típica en problemas combinatorios como las n-reinas.
  • La prueba de mesa (desk-check) consiste en ejecutar el algoritmo a mano anotando el valor de cada variable tras cada paso, como primera verificación antes de programarlo.
  • Un invariante de bucle es una propiedad verdadera antes de la primera iteración y que se mantiene verdadera tras cada iteración, usada para demostrar formalmente la corrección de un bucle.
  • La notación Big O describe el crecimiento del tiempo de ejecución o del espacio de memoria en función del tamaño de la entrada, típicamente en el peor caso.
  • O(1) indica tiempo constante, independiente del tamaño de la entrada (ej. acceso a un elemento de un array por índice).
  • O(log n) indica crecimiento logarítmico, típico de algoritmos que descartan la mitad de los datos en cada paso (ej. búsqueda binaria).
  • O(n) indica crecimiento lineal, proporcional al tamaño de la entrada (ej. recorrer un array completo una vez).
  • O(n log n) es la complejidad típica de los algoritmos de ordenación eficientes basados en comparación (ej. mergesort, quicksort en caso promedio).
  • O(n²) indica crecimiento cuadrático, típico de algoritmos con bucles anidados que recorren la misma entrada dos veces (ej. bubble sort en el peor caso).
  • O(2^n) y O(n!) son complejidades exponenciales y factoriales, típicas de algoritmos de fuerza bruta sobre problemas combinatorios, inviables para entradas grandes.
  • La notación Ω (omega) expresa una cota inferior de crecimiento (mejor caso) y Θ (theta) una cota ajustada cuando la cota superior e inferior coinciden en orden; en la práctica se usa sobre todo Big O.
  • El análisis de la complejidad en el mejor, peor y caso medio puede diferir sustancialmente para un mismo algoritmo (p. ej. quicksort es O(n log n) en caso medio pero O(n²) en el peor caso).
Ver el esquema con tus propios subrayados →

Ponte a prueba

10 preguntas sobre este tema, en orden aleatorio. Sin registro, sin límite de intentos.

Pregunta 1 de 100 aciertos

¿Qué técnica de diseño de algoritmos se basa en almacenar los resultados de subproblemas solapados para no recalcularlos?

Preguntas frecuentes

¿De qué trata el Tema 25 de Profesor FP Informática?

Un algoritmo es una secuencia finita, ordenada y no ambigua de pasos que resuelve un problema o realiza una tarea determinada, independiente del lenguaje de programación en que finalmente se implemente. Este tema estudia las propiedades que debe cumplir todo buen algoritmo, las técnicas descriptivas para representarlo antes de codificarlo -pseudocódigo, diagramas de flujo y diagramas de Nassi-Shneiderman-, las principales estrategias de diseño (divide y vencerás, algoritmos voraces, programación dinámica y vuelta atrás), las técnicas básicas de verificación manual y los criterios para analizar su eficiencia mediante la notación asintótica.

¿Qué hay que memorizar del Tema 25 para el examen?

Un algoritmo debe ser finito: debe terminar tras un número finito de pasos, no puede ejecutarse indefinidamente. Un algoritmo debe ser definido: cada paso debe estar especificado de forma precisa y sin ambigüedad, interpretable de una única manera. Un algoritmo puede tener cero o más entradas, pero debe producir al menos una salida relacionada con ellas. La propiedad de efectividad exige que cada paso del algoritmo sea lo bastante básico como para poder ejecutarse en un tiempo finito con los recursos disponibles. La generalidad es la propiedad por la cual un algoritmo resuelve toda una clase de problemas, no un único caso concreto con valores fijos. El pseudocódigo describe la lógica del algoritmo en lenguaje semiformal, independiente de la sintaxis de cualquier lenguaje de programación concreto, sin que exista un estándar único obligatorio. Los diagramas de flujo usan símbolos normalizados: óvalo para inicio/fin, rectángulo para proceso, rombo para decisión, paralelogramo para entrada/salida. El rombo de decisión en un diagrama de flujo tiene siempre al menos dos flechas de salida, correspondientes a las distintas ramas posibles de la condición evaluada. Los diagramas de Nassi-Shneiderman representan el algoritmo mediante cajas anidadas sin ninguna flecha, lo que impide por construcción representar saltos incondicionales (goto). En un diagrama de Nassi-Shneiderman, la iteración se dibuja como una caja envolvente que contiene el cuerpo del bucle, y la selección como una caja dividida en ramas. Las tres estructuras de control básicas son: secuencial, condicional (selectiva) y repetitiva (iterativa). El teorema del programa estructurado demuestra que cualquier algoritmo puede expresarse combinando solo secuencia, selección e iteración, sin necesidad de saltos incondicionales (goto). La estructura while (mientras) evalúa la condición ANTES de ejecutar el bloque, por lo que puede no ejecutarse ninguna vez si la condición es falsa desde el inicio. La estructura do-while (hacer-mientras) evalúa la condición DESPUÉS de ejecutar el bloque, garantizando que este se ejecuta al menos una vez. Divide y vencerás descompone un problema en subproblemas más pequeños del mismo tipo, los resuelve por separado y combina sus soluciones; la búsqueda binaria y el mergesort son ejemplos clásicos. Un algoritmo voraz (greedy) toma en cada paso la decisión localmente óptima sin reconsiderarla, lo que no garantiza la solución globalmente óptima salvo en problemas con la propiedad de elección voraz. La programación dinámica evita recalcular subproblemas solapados almacenando (memoizando) sus resultados intermedios, aplicable cuando el problema cumple el principio de optimalidad de Bellman. La vuelta atrás (backtracking) explora un espacio de soluciones candidatas podando las ramas que no pueden llevar a una solución válida, típica en problemas combinatorios como las n-reinas. La prueba de mesa (desk-check) consiste en ejecutar el algoritmo a mano anotando el valor de cada variable tras cada paso, como primera verificación antes de programarlo. Un invariante de bucle es una propiedad verdadera antes de la primera iteración y que se mantiene verdadera tras cada iteración, usada para demostrar formalmente la corrección de un bucle. La notación Big O describe el crecimiento del tiempo de ejecución o del espacio de memoria en función del tamaño de la entrada, típicamente en el peor caso. O(1) indica tiempo constante, independiente del tamaño de la entrada (ej. acceso a un elemento de un array por índice). O(log n) indica crecimiento logarítmico, típico de algoritmos que descartan la mitad de los datos en cada paso (ej. búsqueda binaria). O(n) indica crecimiento lineal, proporcional al tamaño de la entrada (ej. recorrer un array completo una vez). O(n log n) es la complejidad típica de los algoritmos de ordenación eficientes basados en comparación (ej. mergesort, quicksort en caso promedio). O(n²) indica crecimiento cuadrático, típico de algoritmos con bucles anidados que recorren la misma entrada dos veces (ej. bubble sort en el peor caso). O(2^n) y O(n!) son complejidades exponenciales y factoriales, típicas de algoritmos de fuerza bruta sobre problemas combinatorios, inviables para entradas grandes. La notación Ω (omega) expresa una cota inferior de crecimiento (mejor caso) y Θ (theta) una cota ajustada cuando la cota superior e inferior coinciden en orden; en la práctica se usa sobre todo Big O. El análisis de la complejidad en el mejor, peor y caso medio puede diferir sustancialmente para un mismo algoritmo (p. ej. quicksort es O(n log n) en caso medio pero O(n²) en el peor caso).

¿Hay preguntas de test de este tema exacto?

Sí, 10 preguntas tipo test sobre este tema, en el apartado "Ponte a prueba" de esta misma página. Sin registro y sin límite de intentos.

¿De dónde sale el temario de este tema?

Del índice oficial de Orden de 1 de febrero de 1996 por la que se aprueban los temarios que han de regir en los procedimientos de ingreso, adquisición de nuevas especialidades y movilidad para determinadas especialidades de los Cuerpos de Profesores de Enseñanza Secundaria y de Profesores Técnicos de Formación Profesional (BOE núm. 38, de 13 de febrero de 1996, BOE-A-1996-3102) — Anexo correspondiente al Cuerpo de Profesores Técnicos de Formación Profesional (0591), especialidad Sistemas y Aplicaciones Informáticas (código 227). Este temario de 1996 sigue vigente hoy como temario de referencia estatal: las convocatorias autonómicas actuales (2023-2026) de esta especialidad remiten expresamente a él como Anexo de contenidos, sin que haya sido derogado ni sustituido por una lista de temas distinta. (Temario oficial estatal de referencia — especialidad Sistemas y Aplicaciones Informáticas (código 227), Cuerpo de Profesores Técnicos de Formación Profesional).

Mientras tanto, practica con tests gratis de Profesor FP Informática.

Empieza gratis ahora