GRANDES IDEAS DE LA

INFORMÁTICA

ALGORITMOS

Raquel Martínez Unanue

r.martinez@escet.urjc.es
Dpto. ESCET
URJC
Indice

• Concepto de algoritmo
• Refinamiento por pasos
• Estructuras de control
• Complejidad
• Algoritmos de búsqueda
• Algoritmos de ordenación
Indice

• Concepto de algoritmo
• Refinamiento por pasos
• Estructuras de control
• Complejidad
• Algoritmos de búsqueda
• Algoritmos de ordenación
 Concepto de algoritmo

Definición de algoritmo:
descripción de la forma de realizar una
tarea o proceso
 Concepto de algoritmo

Algoritmos cotidianos:
Tarea Algoritmo
preparar un pastel receta

ejecutar una sonata partitura

construcción de una planos de cons.
caseta

hacer un vestido patrón

 Concepto de algoritmo

Algoritmos cotidianos:
Tarea Entrada
preparar un pastel harina, azucar, ...

ejecutar una sonata

construcción de una ladrillos, madera, ...

caseta
hacer un vestido tela, hilos, ...
 Concepto de algoritmo

Algoritmos cotidianos:
Tarea Salida
preparar un pastel pastel

ejecutar una sonata sonido

construcción de una caseta

caseta
hacer un vestido vestido
 Concepto de algoritmo

Requisitos de los algoritmos:

• ACCIONES BIEN DEFINIDAS, no

ambiguas
• SECUENCIA FINITA de operaciones
• acaba en un TIEMPO FINITO
 Concepto de algoritmo
Una receta

• un chorrito de ...
• una pizca de ...
• cuando la carne esté hecha ...
• se revuelve de vez en cuando
...
 Concepto de algoritmo
Una receta

AM
BI
• un chorrito de ...
GU
• una pizca de ...
E
• cuando la carne D
esté hecha ...
AD
• se revuelve de vez en cuando
...
 Concepto de algoritmo

Nº
FI
receta NI
TO
partitura DE
planos de constr. PA
patrón
SO
S
 Concepto de algoritmo

TE
receta
RM
partitura IN
planos de cons.
AN
patrón
 Concepto de algoritmo

Receta:
• puede ser “procesada” por una persona
(intuición, sentido común, ...)

• no podría ser “procesada” por un

ordenador
Indice

• Concepto de algoritmo

• Refinamiento por pasos

• Estructuras de control
• Complejidad
• Algoritmos de búsqueda
• Algoritmos de ordenación
 Refinamiento por pasos

Tarea sencilla algoritmo sencillo

poco esfuerzo de diseño

Tarea compleja algoritmo complejo

enfoque metódico de diseño
REFINAMIENTO POR PASOS
(diseño descendente)
 Refinamiento por pasos
Fundamento:
• Descomposición de un problema en
subproblemas más simples
• Cada subproblema, a su vez, quizá de
pueda descomponer en otros más
simples
• El refinamiento continúa hasta que los
subproblemas son lo suficientemente
simples para resolverlos con un algoritmo
 Refinamiento por pasos

Diseño de un algoritmo para cambiar una

bombilla fundida

Solución 1:
• Quítese la bombilla quemada
• Colóquese una nueva
 Refinamiento por pasos

Solución 2:

¿Cómo se quita la
bombilla quemada?

¿Cómo se coloca una

nueva?
 Refinamiento por pasos

¿Cómo se quita la
bombilla quemada?
• Situar la escalera debajo
de la bombilla
• Subir por la escalera hasta
alcanzar la bombilla
• Girar la bombilla en
sentido antihorario hasta
que esté suelta
 Refinamiento por pasos
¿Cómo se coloca una
nueva bombilla?
• Elegir una bombilla nueva
de la misma potencia
• Ubicarla en el mismo sitio
• Enroscarla en sentido
horario hasta que esté
apretada
• Bajar de la escalera
 Refinamiento por pasos
Solución 2:
• Situar la escalera debajo de la bombilla
• Elegir una nueva de la misma potencia
• Subir a la escalera hasta alcanzar la bombilla
• Girarla en sentido antihorario hasta que esté
suelta
• Ubicarla en el mismo sitio
• Enroscarla en sentido horario hasta que esté
apretada
• Bajar de la escalera
 Refinamiento por pasos

¿Hasta qué nivel de detalle hay que

refinar una acción?
• Depende de quién o qué deba interpretarlo

Ordenador o computadora:
cuando sea fácilmente
trasladable a un lenguaje
de programación
Indice
• Concepto de algoritmo
• Refinamiento por pasos

• Estructuras de control
• Complejidad
• Algoritmos de búsqueda
• Algoritmos de ordenación
 Estructuras de control
Todo algoritmo se puede construir a partir
de las siguientes estructuras de control:

• Composición secuencial
• Selección
• Iteración
 Estructuras de control

Composición secuencial:
• Serie de acciones que se llevarán a cabo
en el orden en el que aparecen
Ejemplo:
• Situar la escalera debajo de la bombilla
• Elegir una nueva de la misma potencia
• Subir a la escalera hasta alcanzar la bombilla
 Estructuras de control

Composición secuencial:
 Estructuras de control

Composición secuencial:

acción 1
acción 2
...
acción n
 Estructuras de control
Selección:
• Elige entre diferentes secuencias de
acciones o instrucciones
Ejemplo: la bombilla no se enciende

SI bombilla fundida ENTONCES

cambio de bombilla
SI NO
revisar instalación
FSI
 Estructuras de control
Selección:
 Estructuras de control
Selección:

SI condición ENTONCES
accionesCondicionCierta
SI NO
accionesCondicionFalsa
FSI
 Estructuras de control
Iteración o repetición:
• Repetición de una serie de acciones
Ejemplo: Subir la escalera hasta alcanzar la
bombilla

MIENTRAS no alcance la bombilla HACER

subir un peldaño
FMIENTRAS
 Estructuras de control
Iteración o repetición:
 Estructuras de control
Iteración o repetición:

MIENTRAS condición HACER

acción/es
FMIENTRAS
 Estructuras de control
Iteración o repetición:

PARA var ← valorIni HASTA valorFin HACER

acción/es
FPARA
Indice
• Concepto de algoritmo
• Refinamiento por pasos
• Estructuras de control

• Complejidad
• Algoritmos de búsqueda
• Algoritmos de ordenación
 Complejidad
¿Cuánta cantidad de recursos necesita
el programa?

Principales recursos:

- tiempo (ejecución)
- espacio (memoria)
- nº procesadores (arquitecturas
paralelas)
 Complejidad
• Un problema se puede resolver con varios
algoritmos
• Esos algoritmos pueden utilizar distintas
cantidades de recursos

determinar el “mejor” algoritmo

“mejor”: el que necesite menos recursos

 Complejidad
• La cantidad de recursos depende del tamaño
de la entrada
• Tamaño de la entrada: número de
componentes sobre los que se ejecuta un
algoritmo
T(n) : complejidad en tiempo para una entrada
de tamaño n
No se mide en unidades de tiempo (sg.)
sino en número de “pasos” (acciones
simples)
 Complejidad

Problema: sumar las componentes de un

vector

- tamaño de la entrada: nº de componentes

n = nº de componentes

- si consideramos que la suma es una

operación simple
T(n) ≈ n
 Complejidad

Supongamos que un algoritmo requiere una

cantidad de recursos
T(n) = 3n2 + 5n

conforme n aumenta: 3n2 5n

término dominante cada vez menos

significativo
comportamiento asintótico
 Complejidad
El comportamiento asintótico es el que
determina si un algoritmo es o no factible

Ejemplos: n, n2, n3, ... , 2n

lineal cn : exponencial
cuadrático
nc : polinomial

polinomial: factible con tamaños razonables de n

exponencial: factible con tamaños pequeños de n
 Complejidad
Universo de problemas
Todos los problemas

Problemas factiblemente
computables

Problemas computables
 Algoritmos de búsqueda
Búsqueda de un elemento en una
colección de elementos del mismo tipo
• Supongamos que los elementos de la
colección se almacenan en:
1 2 3 4 5 6 7 8 9 10 11 12

S[1] S[2] ... S[12]

 Algoritmos de búsqueda

Búsqueda de un elemento en una

colección de elementos del mismo tipo

Tipos de búsqueda:
• lineal o secuencial
• binaria o dicotómica
 Algoritmos de búsqueda

Búsqueda lineal o secuencial

• Se comienza con el 1er elemento de la
colección
• Se compara el elemento que se busca con el de
la colección de forma secuencial hasta:

- encontrar el elemento buscado, o

- llegar al final de la colección
 Algoritmos de búsqueda

Búsqueda lineal o secuencial

3
5 6 7 3 4 9 0 2 1
 Algoritmos de búsqueda

Búsqueda lineal o secuencial

8
5 6 7 3 4 9 0 2 1
 Algoritmos de búsqueda
Búsqueda lineal o secuencial
FUNCION BusqSecuencial (S, elemento buscado)
dev posicion;
posicion ← primera
MIENTRAS (posicion ≤ ultima) Y (S [posicion]
≠ elemento buscado)
posicion ← siguiente(posicion)
FMIENTRAS
SI posicion > ultima ENTONCES
posición ← 0
FSI
 Algoritmos de búsqueda

Complejidad de la Búsqueda lineal

• Un mismo algoritmo requiere diferentes
recursos para diferentes entradas del mismo
tamaño
Caso mejor: cantidad mínima de recursos
Caso promedio: cantidad media de recursos
Caso peor: cantidad de recursos máximos
 Algoritmos de búsqueda

Complejidad de la Búsqueda lineal

Comportamiento asintótico
en el caso peor: n

n: número de componentes de la colección

 Algoritmos de búsqueda

Búsqueda lineal o secuencial en una

colección ordenada
3

0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda lineal o secuencial en una

colección ordenada
4

0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda
Búsqueda lineal o secuencial orden.
FUNCION BusqSecOrden (S, elemento buscado)
dev posicion;
posicion ← primera
MIENTRAS (posicion ≤ ultima) Y (S [posicion]
< elemento buscado)
posicion ← siguiente(posicion)
FMIENTRAS
SI (posicion > ultima) OR (S [posicion] >
elemento buscado)
ENTONCES posición ← 0
FSI
 Algoritmos de búsqueda

Complejidad de la Búsqueda lineal

Comportamiento asintótico
en el caso peor: n

n: número de componentes de la colección

 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

• La colección debe estar ordenada

• Es el método utilizado para buscar en un

diccionario, listín, ...
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

• Divide la colección en dos mitades, determina
en cuál de ellas puede estar el elemento
buscado y la selecciona

• Se continúa dividiendo el espacio de

búsqueda en mitades hasta encontrar el
elemento o determinar que no está
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

2
0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

2
0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

4
0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

0 1 2 3 5 6 7 8 9
 Algoritmos de búsqueda

Búsqueda binaria o dicotómica

0 1 2 3 5 6 7 8 9
FUNCION BusqDicotomica (S, elemento buscado)
dev posicion;
extInf ← Primero; extSup ← Ultimo;
encontrado ← falso
MIENTRAS (NO encontrado) Y (extSup>=extInf)
central ← (extSup + extInf) DIV 2
SI S [central] = elemBuscado ENTONCES
encontrado ← verdadero
SI NO
SI S [central] < elemBuscado ENTONCES
extInf ← central + 1
SI NO extSup ← central – 1
FSI
FSI
FMIENTRAS
 Algoritmos de búsqueda

SI encontrado ENTONCES
posición ← central
SI NO
posición ← 0
FSI
 Algoritmos de búsqueda
Complejidad de la Búsqueda dicotómica
• El peor caso de este algoritmo se da cuando:
el elemento buscado no está en la lista

• En el caso peor, el bucle se ejecuta un número

de veces igual a la parte entera del logaritmo en
base 2 de n

• En cada ejecución del bucle reduce el tamaño

de la lista a la mitad
 Algoritmos de búsqueda

Complejidad de la Búsqueda dicotómica

Comportamiento asintótico
en el caso peor: log n

n: número de componentes de la colección

 Algoritmos de ordenación
• Ordenar los elementos de una
secuencia
• Existen numerosos algoritmos de
ordenación
• Supongamos que los elementos de la
secuencia se almacenan en:
1 2 3 4 5 6 7 8 9 10 11 12

S
 Algoritmos de ordenación

Ordenación por inserción directa

• La idea básica es recorrer la secuencia S

insertando cada elemento S[i] en el lugar
correcto entre los elementos ya ordenados
S[1] ,...,S[i-1]

• Es un método eficiente de ordenación para

conjuntos pequeños de datos
 Algoritmos de ordenación
Ordenación por inserción directa

Paso 1: Se considera S[1] como primer

elemento

Paso 2: Se inserta S[2] en su posición en

relación a S[1] y S[2]
...

Paso n: Se inserta S[n] en su posición en

relación a S[1],...,S[n-1]
 Algoritmos de ordenación
Ordenación por inserción directa

5 6 7 3 4 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa
3
5 6 7 3 4 9 0 2 1
5 6 7 4 9 0 2 1
5 6 7 4 9 0 2 1
5 6 7 4 9 0 2 1
3 5 6 7 4 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa

3 5 6 7 4 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa
4
3 5 6 7 4 9 0 2 1
3 5 6 7 9 0 2 1
3 5 6 7 9 0 2 1
3 5 6 7 9 0 2 1
3 4 5 6 7 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa

3 4 5 6 7 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa

3 4 5 6 7 9 0 2 1
 Algoritmos de ordenación
Ordenación por inserción directa
0
3 4
5 6 7 9 0 2 1
3 4
5 6 7 9 2 1
3 4
5 6 7 9 2 1
3 4
5 6 7 9 2 1
3 4 5 6 7 9 2 1
3 4 5 6 7 9 2 1
3 4 5 6 7 9 2 1
0 3 4 5 6 7 9 2 1
 Algoritmos de ordenación
Ordenación por inserción directa

0 3 4 5 6 7 9 2 1
 Algoritmos de ordenación
Ordenación por inserción directa
2
0 3 4
5 6 7 9 2 1
0 3 4
5 6 7 9 1
0 3 4
5 6 7 9 1
0 3 4
5 6 7 9 1
0 3 4 5 6 7 9 1
0 3 4 5 6 7 9 1
0 3 4 5 6 7 9 1
0 2 3 4 5 6 7 9 1
 Algoritmos de ordenación
Ordenación por inserción directa

0 2 3 4 5 6 7 9 1
 Algoritmos de ordenación
Ordenación por inserción directa
1
0 2 3 4
5 6 7 9 1
0 2 3 4
5 6 7 9
0 2 3 4
5 6 7 9
0 2 3 4
5 6 7 9
0 2 3 4 5 6 7 9
0 2 3 4 5 6 7 9
0 2 3 4 5 6 7 9
0 2 3 4 5 6 7 9
0 1 2 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por inserción directa
PARA i ← 2 HASTA n HACER
elem ← S[ i ]
k ←i-1
MIENTRAS ( k ≥ 1) Y (S[ k ] > elem) HACER
S[ k + 1 ] ← S[ k ]
k ←k-1
FMIENTRAS
S[ k + 1 ] ← elem
FPARA
 Algoritmos de ordenación
Complejidad de la inserción directa

• Para cada valor de i, k ejecuciones del bucle

más interno

i=2,k=1
i = 3, k = 2 T(n) ≈ 1 + 2 + ... + (n-2) +(n-1) =
i = 4, k = 3 = (n -1) n /2
...
i = n, k = n – 1 Comportamiento asintótico:
n2
 Algoritmos de ordenación

Ordenación por intercambio directo

• La idea básica es recorrer la secuencia S
colocando el mayor en S[n], en siguiente
mayor en S[n-1], ... hasta ordenar S

• Para ello, se comparan elementos adyacentes

y se intercambian siempre que no estén
ordenados entre ellos

• Eficiente para conjuntos pequeños de datos

 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 7 3 4 9 0 2 1
 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 3 7 4 9 0 2 1
 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 3 4 7 9 0 2 1
 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 3 4 7 0 9 2 1
 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 3 4 7 0 2 9 1
 Algoritmos de ordenación
Ordenación por intercambio directo
5 6 3 4 7 0 2 1 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 6 4 7 0 2 1 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 4 6 7 0 2 1 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 4 6 0 7 2 1 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 4 6 0 2 7 1 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 4 6 0 2 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
5 3 4 6 0 2 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 5 4 6 0 2 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 6 0 2 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 0 6 2 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 0 2 6 1 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 0 2 1 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 0 2 1 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 5 0 2 1 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 0 5 2 1 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 0 2 5 1 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 0 2 1 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 4 0 2 1 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 0 4 2 1 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 0 2 4 1 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 0 2 1 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
3 0 2 1 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 3 2 1 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 2 3 1 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 2 1 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 2 1 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 1 2 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 1 2 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo
0 1 2 3 4 5 6 7 9
 Algoritmos de ordenación
Ordenación por intercambio directo

PARA i ← 1 hasta n -1 hacer

PARA k← 1 hasta n - i hacer
SI S[ k] > S[ k+1] ENTONCES
intercambio (S[ k], S[ k+1])
FSI
FPARA
FPARA
 Algoritmos de ordenación
Complejidad de la intercambio directo

• Para cada valor de i, k ejecuciones del bucle

más interno

i = 1 , k = n- 1
i = 2, k = n- 2 T(n) ≈ (n-1) + (n-2) + ... + 1 =
i = 3, k = n- 3 = (n -1) n /2
...
i = n-1, k = 1 Comportamiento asintótico:
n2