Sección de repaso
1. ¿Qué es un algoritmo?
Un algoritmo es un conjunto finito de instrucciones precisas y ordenadas que, a partir de unos
datos de entrada, permiten resolver un problema y producir un resultado.
2. Propiedades de un algoritmo
• Entrada: Datos que recibe el algoritmo para iniciar su ejecución.
• Salida: Resultado que produce después de procesar la entrada.
• Precisión: Cada instrucción debe estar claramente definida, sin ambigüedades.
• Determinismo: Con la misma entrada, siempre produce la misma salida siguiendo los
mismos pasos.
• Carácter finito: Debe terminar después de un número finito de pasos.
• Corrección: Produce la respuesta correcta para todas las entradas válidas.
• Generalidad: Resuelve cualquier caso del problema, no solo ejemplos particulares.
3. ¿Qué es el seguimiento (rastreo) de un algoritmo?
Es el proceso de ejecutar el algoritmo paso a paso, registrando cómo cambian las variables para
verificar que funciona correctamente.
4. ¿Cuáles son las ventajas del seudocódigo sobre el texto común?
• Organiza las instrucciones de forma lógica.
• Elimina ambigüedades del lenguaje natural.
• Es fácil de entender sin depender de un lenguaje de programación.
• Facilita convertir el algoritmo a código.
5. ¿Cómo se relacionan los algoritmos con las funciones del seudocódigo?
El algoritmo describe la solución de un problema. Las funciones del seudocódigo son bloques
reutilizables que realizan tareas específicas dentro de ese algoritmo, haciendo la solución más
organizada, modular y fácil de mantener.
Sección de repaso
1. ¿Qué es un algoritmo?
Un algoritmo es un conjunto finito de instrucciones precisas y ordenadas que, a partir de unos
datos de entrada, permiten resolver un problema y producir un resultado.
2. Propiedades de un algoritmo
• Entrada: Datos que recibe el algoritmo para iniciar su ejecución.
• Salida: Resultado que produce después de procesar la entrada.
• Precisión: Cada instrucción debe estar claramente definida, sin ambigüedades.
• Determinismo: Con la misma entrada, siempre produce la misma salida siguiendo los
mismos pasos.
• Carácter finito: Debe terminar después de un número finito de pasos.
• Corrección: Produce la respuesta correcta para todas las entradas válidas.
• Generalidad: Resuelve cualquier caso del problema, no solo ejemplos particulares.
3. ¿Qué es el seguimiento (rastreo) de un algoritmo?
Es el proceso de ejecutar el algoritmo paso a paso, registrando cómo cambian las variables para
verificar que funciona correctamente.
4. ¿Cuáles son las ventajas del seudocódigo sobre el texto común?
• Organiza las instrucciones de forma lógica.
• Elimina ambigüedades del lenguaje natural.
• Es fácil de entender sin depender de un lenguaje de programación.
• Facilita convertir el algoritmo a código.
5. ¿Cómo se relacionan los algoritmos con las funciones del seudocódigo?
El algoritmo describe la solución de un problema. Las funciones del seudocódigo son bloques
reutilizables que realizan tareas específicas dentro de ese algoritmo, haciendo la solución más
organizada, modular y fácil de mantener.
Ejercicios
1. Instrucciones para llamadas de larga distancia
Supongamos unas instrucciones como:
1. Marque el código de salida.
2. Marque el código del país.
3. Marque el código de área.
4. Marque el número telefónico.
Propiedades presentes
• ✅ Entrada: número telefónico, país, ciudad.
• ✅ Salida: llamada realizada.
• ✅ Precisión: los pasos están definidos.
• ✅ Determinismo: siguiendo los pasos siempre ocurre lo mismo.
• ✅ Carácter finito: termina al marcar el número.
• ✅ Generalidad: sirve para cualquier llamada internacional.
Propiedad que puede faltar
• ❌ Corrección, si las instrucciones están desactualizadas o algún país cambió su prefijo.
2. Conjetura de Goldbach
Algoritmo:
n ← 4
Mientras verdadero
Si n no es suma de dos primos
escribir "NO"
terminar
n ← n+2
Propiedades
❌
Propiedad ¿La tiene?
✅
Entrada No recibe datos.
✅
Salida Sí ("Sí" o "No").
✅
Precisión Sí.
Determinismo Sí.
❌
Propiedad ¿La tiene?
Carácter finito No necesariamente.
❌
Corrección Depende.
Generalidad Solo verifica Goldbach.
¿Qué depende de que Goldbach sea verdadera?
• Corrección.
• Carácter finito.
Si Goldbach es verdadera, nunca encontrará un contraejemplo y el algoritmo jamás termina.
Si es falsa, termina cuando encuentre el primer contraejemplo.
3. Menor entre a, b y c
Paso a paso
Inicialmente suponemos que el menor es a.
menor ← a
Si b < menor
menor ← b
Si c < menor
menor ← c
Escribir menor
4. Segundo menor entre a, b y c
Como todos son diferentes.
Si a<b y a<c
Si b<c
segundo ← b
Sino
segundo ← c
Sino si b<a y b<c
Si a<c
segundo ← a
Sino
segundo ← c
Sino
Si a<b
segundo ← a
Sino
segundo ← b
Escribir segundo
5. Menor de una sucesión
Supongamos
s1 s2 ... sn
Paso a paso
Tomamos el primero como mínimo.
menor ← s1
Para i=2 hasta n
Si si < menor
menor ← si
Escribir menor
Complejidad: O(n).
6. Mayor y segundo mayor
Inicialización
mayor ← s1
segundo ← s2
Si segundo>mayor
intercambiar
Luego
Para i=3 hasta n
Si si>mayor
segundo ← mayor
mayor ← si
Sino si si>segundo
segundo ← si
Escribir mayor
Escribir segundo
7. Menor y segundo menor
Análogo al anterior.
menor ← s1
segundo ← s2
Si segundo<menor
intercambiar
Luego
Para i=3 hasta n
Si si<menor
segundo ← menor
menor ← si
Sino si si<segundo
segundo ← si
9. Primera posición del mayor
Ejemplo
6.2 8.9 4.2 8.9
Debe regresar 2.
mayor ← s1
indice ←1
Para i=2 hasta n
Si si>mayor
mayor ← si
indice ← i
Escribir indice
Observa que solo actualiza cuando es mayor, no cuando es igual.
10. Última posición del mayor
Aquí sí actualizamos cuando es igual.
mayor ← s1
indice ←1
Para i=2 hasta n
Si si>=mayor
mayor ← si
indice ← i
Con
6.2 8.9 4.2 8.9
devuelve 4.
11. Suma de una sucesión
suma ←0
Para i=1 hasta n
suma ← suma+si
Escribir suma
12. Primer elemento menor que su predecesor
Ejemplo
AMY
BRUNO
ELIE
DAN
ZEKE
Comparaciones
AMY<-
BRUNO>AMY
ELIE>BRUNO
DAN<ELIE
Entonces devuelve 4.
Algoritmo
Para i=2 hasta n
Si si < s(i-1)
Escribir i
Terminar
Escribir 0
15. Suma de dos enteros (como en primaria)
Ejemplo
348
+679
----
1027
Algoritmo
1. Alinear cifras.
2. Empezar por la derecha.
3. Sumar las cifras.
4. Si el resultado es mayor que 9, guardar el acarreo.
5. Escribir el dígito correspondiente.
6. Continuar hacia la izquierda.
7. Si queda acarreo, escribirlo al inicio.
16. Transpuesta de una matriz
Para cada elemento
AT[j][i]=A[i][j]
Pseudocódigo
Para i=1 hasta n
Para j=1 hasta n
AT[j][i]=A[i][j]
17. Verificar si una relación es reflexiva
Debe cumplirse
A[i][i]=1
para toda la diagonal.
Para i=1 hasta n
Si A[i][i]=0
escribir "No"
terminar
Escribir "Sí"
18. Verificar si es simétrica
Debe cumplirse
A[i][j]=A[j][i]
Para i=1 hasta n
Para j=1 hasta n
Si A[i][j]≠A[j][i]
escribir "No"
terminar
Escribir "Sí"
19. Verificar si es transitiva
Debe cumplirse
Si
(i,j)=1
(j,k)=1
entonces
(i,k)=1
Algoritmo
Para i
Para j
Para k
Si A[i][j]=1 y A[j][k]=1 y A[i][k]=0
escribir "No"
terminar
Escribir "Sí"
Complejidad
O(n³).
20. Verificar si es antisimétrica
Debe cumplirse
Si
A[i][j]=1
A[j][i]=1
entonces
i=j
Pseudocódigo
Para i
Para j
Si i≠j y A[i][j]=1 y A[j][i]=1
escribir "No"
terminar
Escribir "Sí"
21. Verificar si una relación es función
Cada fila debe contener exactamente un 1.
Para cada fila
contar←0
Para cada columna
Si hay un 1
contar++
Si contar≠1
escribir "No"
terminar
Escribir "Sí"
22. Relación inversa
La matriz inversa se obtiene intercambiando filas por columnas.
R⁻¹[j][i]=R[i][j]
Es exactamente la transpuesta.
Para i
Para j
RI[j][i]=R[i][j]
23. Composición de relaciones
Para obtener
[
R_1\circ R_2
]
se verifica si existe algún elemento intermedio (k):
Para i
Para j
C[i][j]=0
Para k
Si R1[i][k]=1 y R2[k][j]=1
C[i][j]=1
salir del ciclo k
La matriz C representa la composición de las relaciones.
Complejidad: O(n³).
Sección de ejercicios de repaso
1. Proporcione ejemplos de problemas de búsqueda.
Algunos ejemplos son:
• Buscar un nombre en una agenda telefónica.
• Buscar un estudiante por su matrícula.
• Buscar una palabra dentro de un documento.
• Buscar un archivo en una computadora.
• Buscar el mayor o el menor elemento de una lista.
2. ¿Qué es búsqueda de texto?
La búsqueda de texto consiste en localizar una palabra, frase o patrón dentro de un texto,
indicando si existe y, en muchos casos, su posición.
3. Describa en palabras un algoritmo que resuelva el problema
de búsqueda de texto.
Paso a paso
1. Leer el texto completo.
2. Leer la palabra que se desea buscar.
3. Comenzar desde el primer carácter del texto.
4. Comparar los caracteres consecutivos con la palabra buscada.
5. Si coinciden todos los caracteres, reportar la posición encontrada.
6. Si no coinciden, avanzar una posición y repetir.
7. Si se llega al final del texto sin encontrarla, indicar que no existe.
4. ¿Qué significa ordenar una sucesión?
Es reorganizar los elementos de una sucesión siguiendo un criterio, generalmente de menor a
mayor o de mayor a menor.
5. Dé un ejemplo que ilustre por qué es deseable ordenar una
sucesión.
Suponga la lista
25 7 18 40 12
Ordenada queda
7 12 18 25 40
Ahora es mucho más sencillo:
• encontrar el mayor y el menor,
• buscar un elemento mediante búsqueda binaria,
• calcular medianas,
• detectar valores repetidos.
6. Describa la inserción por orden en palabras.
Paso a paso
1. Se considera que el primer elemento ya está ordenado.
2. Se toma el siguiente elemento.
3. Se compara con los elementos anteriores.
4. Mientras sea menor, los elementos mayores se desplazan una posición a la derecha.
5. Cuando encuentra su posición correcta, se inserta.
6. Se repite hasta ordenar todos los elementos.
7. ¿Qué quiere decir tiempo y espacio requeridos por un
algoritmo?
• Tiempo requerido: cantidad de operaciones o tiempo que tarda el algoritmo en ejecutarse.
• Espacio requerido: cantidad de memoria que necesita para funcionar.
8. ¿Por qué es útil conocer o estimar el tiempo y espacio
requeridos?
Porque permite:
• comparar algoritmos,
• elegir el más eficiente,
• estimar recursos necesarios,
• saber si podrá ejecutarse con grandes cantidades de datos.
9. ¿Por qué a veces es necesario relajar los requerimientos
establecidos para un algoritmo?
Porque algunos problemas no pueden resolverse exactamente en un tiempo razonable. En esos casos
se aceptan soluciones aproximadas, probabilísticas o más rápidas para hacer el algoritmo práctico.
10. ¿Qué es un algoritmo aleatorizado?
Es un algoritmo que utiliza números aleatorios durante su ejecución, por lo que con la misma
entrada puede seguir caminos distintos o producir resultados diferentes.
11. ¿Cuáles de los requerimientos de un algoritmo viola un
algoritmo aleatorizado?
Principalmente el determinismo, ya que con la misma entrada puede producir ejecuciones o
resultados distintos debido al uso del azar.
12. Describa en palabras el algoritmo para desordenar.
Paso a paso (Algoritmo de Fisher-Yates)
1. Comenzar desde el último elemento de la lista.
2. Elegir aleatoriamente una posición entre el primero y el elemento actual.
3. Intercambiar ambos elementos.
4. Retroceder una posición.
5. Repetir hasta llegar al segundo elemento.
6. La lista queda completamente desordenada de forma uniforme.
Ejemplo
Lista inicial
A B C D E
Suponga:
• intercambia E con B
A E C D B
Luego:
• intercambia D con A
D E C A B
Luego:
• intercambia C consigo mismo
D E C A B
Luego:
• intercambia E con D
E D C A B
Resultado: una permutación aleatoria.
13. Dé una aplicación del algoritmo para desordenar.
Algunas aplicaciones son:
• Barajar cartas en juegos de póker o blackjack.
• Mezclar preguntas de un examen en línea.
• Reproducir canciones en modo aleatorio.
• Asignar turnos de manera imparcial.
• Simular experimentos estadísticos o de Monte Carlo.