Las ideas clave del bloque
Memoria y punteros
Un puntero guarda una dirección.&x da la dirección de x y *p, la variable a la que apunta p. La pila guarda las variables locales; el montón, lo que se pide con malloc hasta que se libera con free.
Recursión
Caso base, caso general que reduce el problema y combinación. Cada llamada ocupa un marco en la pila.Esquemas de diseño
- Divide y vencerás: partir, resolver cada parte y combinar. Su coste se calcula con ecuaciones de recurrencia.
- Backtracking: explorar decisiones una a una y retroceder en cuanto una rama no puede llevar a una solución (poda).
Análisis
El coste de un algoritmo puede depender de los datos: mejor caso, peor caso y caso medio. Se estudia contando la operación crítica para distintas tallas.Orden recomendado
1
Memoria y punteros en C
Programas en C línea a línea con la pila, el montón y a dónde apunta cada puntero.
2
Recursión en C
Potencia, factorial, MCD, Fibonacci y suma de un vector: pila y árbol de llamadas, y su versión iterativa.
3
Divide y vencerás
Máximo, suma, vector creciente y búsqueda binaria en C, con el trozo de cada llamada y su coste.
4
Backtracking
Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima.
5
Mejor y peor caso
Cuenta operaciones en el mejor, el peor y el caso medio para cada talla, con gráfica y tabla.
Temas de este bloque
Memoria y punteros en C
Punteros en C explicados línea a línea: direcciones, operadores & y *, paso por valor y por referencia, aritmética de punteros, la pila y el montón, malloc y free, y errores típicos.
Recursión en C
La recursión explicada paso a paso en C: caso base y caso general, descenso y ascenso, pila y árbol de llamadas, recursión lineal, final y múltiple (Fibonacci) y cómo pasar a iterativa.
Divide y vencerás
El esquema divide y vencerás explicado con vectores en C: caso trivial, dividir, resolver y combinar, árbol de subproblemas, búsqueda binaria y cálculo del coste con ecuaciones de recurrencia.
Backtracking
El esquema de backtracking explicado en C: árbol de búsqueda, decisiones, podas, y las variantes para obtener todas las soluciones, una solución o la óptima, con la mochila 0/1 y la descomposición en sumandos.
Mejor y peor caso
Cómo analizar el coste de un algoritmo: talla de la entrada, operación crítica, mejor caso, peor caso y caso medio, notación O y análisis experimental con gráficas y tablas, con ejemplos en C.
Simuladores de programación en C en Simulab
Memoria y punteros en C
Programas en C línea a línea con la pila, el montón y a dónde apunta cada puntero.
Recursión en C
Potencia, factorial, MCD, Fibonacci y suma de un vector: pila y árbol de llamadas, y su versión iterativa.
Divide y vencerás
Máximo, suma, vector creciente y búsqueda binaria en C, con el trozo de cada llamada y su coste.
Backtracking
Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima.
Mejor y peor caso
Cuenta operaciones en el mejor, el peor y el caso medio para cada talla, con gráfica y tabla.