Algoritmos Computacionlaes0123

ALGORITMOS COMPUTACIONALES
M.I.I. Raquel Martínez

índice
Fase 1 Fase 2
Fase 3
Algoritmos simples y Algoritmos
Algoritmo de recorrido PIA
Fundamentos de la complejidad Recursivos ,Ordenamiento y
computacional Búsqueda Analizar, diseñar e Realizar un diseño de
implementar algoritmospara solución, representación
Identificar , formular y desarrollar Diseñar e implementar
los problemas de búsqueda y y análisis de métodos de
algoritmos simples utilizando soluciones a los problemas del
recorrido en el que se tengan solución en términos
pseudocodigo declarativo o entorno mediante diseño de
que tomar decisiones que computacionales,
diagramas de flujo haciendo uso algoritmos recursivos,
dependan del estado del presentado su posible
de las herramientas gráficas que utilizando estructuras
sistema, haciendo uso de implementación
permitan comprender la lineales , como lo son pilas,
estructuras de datos no
naturaleza de los problemas y colas, listas y búsqueda de
lineales.
resolverlos eficientemente. información ordenada.

Temario
• Introducción a los algoritmos.
• Análisis de algoritmos computacionales elementales.
• Recursividad.
• Pilas
• Colas
• Listas.
• Algoritmos de ordenamiento, búsqueda y tablas hash.
• Recorridos y búsquedas por profundidad y por anchura.
• Árboles y grafos
• Aplicación de Actualidad
índice M.I.I. Raquel Martínez
INTRODUCCIÓN
• La tecnología de los algoritmos computacionales es uno de los campos de
mayor investigación dentro de las matemáticas, la informática, la lógica y todas
las ramas de las ciencias de la computación. No son más que instrucciones bien
definidas y que no poseen ambigüedades, las cuales permiten un número
ordenado de acciones por parte de los softwares ante cualquier problema.
• De esta manera, ante un problema de cualquier tipo el software puede seguir

una serie de decisiones ya definidas mediante un diagrama de flujo. Estos
diagramas de flujo pueden simplificarse para los usuarios como instrucciones
escritas, por ejemplo, “Para abrir una puerta, ¿está cerrada con seguro? ¿Si?,
¿no?”, entonces dependiendo de la respuesta a la pregunta los algoritmos
computacionales detallarán una acción en base a la situación.

Algoritmos
• Algoritmo
Se puede definir como una secuencia de instrucciones que representan un
modelo de solución para un determinado problema. O de otra forma, son un
conjunto de instrucciones que conducen a la solución de un problema.
Los algoritmos son independientes al lenguaje de programación. En un
problema, el algoritmo puede escribirse y ejecutarse en un sinfín de
lenguajes de programación, dado que el algoritmo es mas la infraestructura.
Un algoritmo puede ser cualitativo o cuantitativo
Es cualitativo cuando sus instrucciones no involucran cálculos numéricos,
cosa que sucede con los cuantitativos

INTRODUCCIÓN
• En este sentido, los algoritmos computacionales pueden entenderse de una manera
detallada y escrita entre las personas. Pero en el caso de los computadores, es
necesario desarrollar dichos algoritmos en lenguaje matemático. Este lenguaje
se conoce como seudocódigo o pseudocódigo.
• Los pseudocódigos son un tipo de lenguaje complejo y abstracto que puede ser
escrito y leído con independencia del lenguaje de programación del software que
haga uso del algoritmo computacional. Se usa para poder expresar de manera
detallada las instrucciones del algoritmo computacional y a su vez sean
entendidas sin modificaciones luego de su traducción al lenguaje de
programación.

Algoritmo
Es un conjunto de instrucciones o
reglas definidas y no-ambiguas,
ordenadas y finitas que permite,
típicamente, solucionar un
problema, realizar un cómputo,
procesar datos y llevar a cabo
otras tareas o actividades.
Dados un estado inicial y una
entrada, siguiendo los pasos
sucesivos se llega a un estado final
y se obtiene una solución. Los
algoritmos son el objeto de estudio
de la algoritmia.
Algoritmo
Un algoritmo es cualquier
cosa que funcione paso a paso,
donde cada paso se pueda
describir sin ambigüedad y sin
hacer referencia a una
computadora en particular, y
además tiene un límite fijo en
cuanto a la cantidad de datos
que se pueden leer/escribir en
un solo paso..

Algoritmo
• En la vida cotidiana, se emplean
algoritmos frecuentemente para resolver
problemas determinados. Algunos ejemplos son
los manuales de usuario, que muestran
algoritmos para usar un aparato, o las
instrucciones que recibe un trabajador de
su patrón.
• Algunos ejemplos
en matemática son el algoritmo de
multiplicación, para calcular el producto, el
algoritmo de la división para calcular el cociente
de dos números, el algoritmo de Euclides para
obtener el máximo común divisor de
dos enteros positivos, o el método de Gauss para
resolver un sistema de ecuaciones lineales.
• En términos de programación, un algoritmo
es una secuencia de pasos lógicos que
permiten solucionar un problema.
PARTES DE UN
ALGORTIMO

Características de los algoritmos.

Etapas para la solución de un problema

¿Cómo se hace un
algoritmo ?
• Aunque realizar un algoritmo computacional puede resultar una ardua tarea, si no se
tienen conocimientos previos de pseudocódigos, programación o ciencias de la
computación. Sin embargo, es posible escribir sencillos algoritmos cualitativos que
sirvan de base o ejemplo para un algoritmo computacional.
• De esta manera, los pasos que se deben seguir para hacer un algoritmo son:
• Paso 1:
• Aquí se debe analizar y describir todo el problema a abordar, para así luego reducirlo a
porciones que serán procesadas dentro del algoritmo.
• Paso 2:
• Una vez analizado y desglosado el problema por partes, se ordena cada una de estas y se
añaden todas las derivaciones posibles (“si”, “no”, etc).

Plataformas que lo utilizan
• YouTube
• La plataforma de streaming y red social YouTube, usa una serie de complejos algoritmos
computacionales los cuales son capaces de analizar los datos de sus usuarios, deduciendo
con ello gustos y desagrados, lo cual es aprovechado para recomendar videos y publicidad
dirigida.
• ORION
• Este es el enorme algoritmo, de más de 1000 páginas de codificación, de la empresa de
mensajería y transporte de paquetes UPS está especialmente diseñado para encontrar las
rutas de entrega más eficientes entre millones de posibilidades.
• Facebook
• La red social Facebook, configura su feed de noticias mediante algoritmos los cuales están
diseñados para medir las relaciones de sus usuarios con las páginas y publicaciones. Con lo
que puede encontrar patrones de gustos, gracias a esto, Facebook organiza las noticias en
nuestro muro en base a lo que más nos pueda agradar.
Técnicas de representación
Para la representación de un algoritmo se utilizan algunos métodos de

representación escrita, grafica o matemática. Los mas conocidos son:
• Diagrama de flujo
• Pseudocodigo
• Lenguaje natural
• Formulas matemáticas

Diagramas de flujo
• Los diagramas de flujo son descripciones
gráficas de algoritmos; usan símbolos
conectados con flechas para indicar la
secuencia de instrucciones y están regidos
por ISO.
• Los diagramas de flujo son usados para
representar algoritmos pequeños, ya que
abarcan mucho espacio y su construcción es
laboriosa. Por su facilidad de lectura son
usados como introducción a los algoritmos,
descripción de un lenguaje y descripción de
procesos a personas ajenas a la computación.

Pseudocódigo
• Es la representación
narrativa (No hay reglas
sintácticas estrictas) de un
algoritmo, escrita en
leguaje natural utilizando
las estructuras de control
típicas de algún lenguaje
de programación y algunos
símbolos algebraicos

Diagramas de flujo

Pseudocódigo

Pseudocódigo

Respuesta

Pseudocodigo
Es la técnica que expresa la solución mediante un algoritmo escrito en
palabras normales de un idioma. No hay un léxico para el
pseudocodigo, pero con el uso frecuente se han establecido algunos
estándares. Un ejemplo de pseudocodigo es el siguiente:

Estructuras
• Es aquella en la que una acción sigue a la otra en el orden en el que
están escritas Existen de tres tipos que son
•Secuencial
•Condicional simple
•Condicional múltiple
•Ciclos o Repetitivos
•
Estructura condicional doble
IF-ELSE
Permite implementar condicionales en los que hay dos acciones
alternas:
Si se verifica una determinad condición, ejecutar una serie de
instrucciones. Si la condición no se verifica, ejecutar otra serie de
instrucciones.

Estructura secuencial
Es la más sencilla , también se le

conoce como estructura lineal. Se
compone de instrucciones que
deben ejecutarse de forma
consecutiva, una tras otra, siguiendo
una y solo una línea de flujo. Las
operaciones se suceden de tal modo
que la salida de una es la entrada
de la siguiente y así sucesivamente
hasta el fin del proceso.
Son problemas muy sencillos.

Estructura repetitiva
FOR
Permite implementar la repetición de un cierto conjunto de
instrucciones en un determinado numero de veces.

Estructura condicional simple IF
Sirve para implementar acciones condicionales del siguiente tipo:
Si se verifica una condición, ejecutar una serie de instrucciones y luego
seguir adelante. Si la condición no se cumple, no se ejecutan las
instrucciones y se sigue adelante.

• Estructura repetitiva condicional WHILE
Permite la repetición de un numero de instrucciones mientras que se
verifique una determinada condición.

• Estructura de elección entre varios casos SWITCH
Permite decidir entre un numero de opciones

A la hora de elaborar un programa es necesario usar unos datos, y para
ello es imprescindible en muchos casos grabar esos datos en memoria
para trabajar con ellos mas adelante. Para grabar dichos datos en la
RAM, es posible hacerlo con dos elementos, las variables y constantes.
• Variables: elementos de almacenamiento de datos que pueden variar
en el proceso del programa.
Cuando se define una variable, no se le introduce ningún valor, sino que
se le esta indicando que tipo de valor va almacenar mas adelante.

Tipos de datos
Es la propiedad de un valor que determina los valores que puede
tomar, las operaciones que se les puede aplicar y como se representa
en la computadora. algunos de estos son:
Números enteros. Permiten representar números enteros (-2,-
3,0,1,2)
Números reales. Representan números reales
Valores lógicos. Pueden tomar uno de dos valores, true o false
Texto. A estos valores se les llama string y representan las palabras

Tipos de datos

Unidad 2: fundamentos
de la complejidad
computacional

Análisis de problemas
La primera fase en la solución de un problema relacionado con
computadoras es el análisis del problema. Esta fase requiere de una
clara definición donde se muestre lo que debe hacer el programa y el
resultado que se desea.

Para una buena definición del problema es
conveniente responder las siguientes
preguntas:
• ¿Qué entradas se requieren? (tipo y cantidad)
• ¿Cuál es la salida deseada? (tipo y cantidad)
• ¿Qué método produce la salida deseada?

En la etapa de análisis del proceso se determina lo que hace el programa
para la tarea solicitada. Los métodos mas eficaces para el proceso de diseño
se basan en la división de problemas en sub problemas y después dividir
estos en otros de nivel mas bajo. Este método se conoce como diseño
descendente o modular.
Cualquier programa bien diseñado consta de un programa principal (el

modulo de nivel mas alto) que llama a subprogramas (módulos de nivel mas
bajo) que a su vez llama a otros subprogramas. Los programas estructurados
de esta forma se les conoce como diseño modular, y el método de usar
módulos mas pequeños se conoce como programación modular.
El proceso implica los siguientes pasos:
1. Programar un modulo
2. Comprobar el modulo
3. Depurar el modulo de ser necesario
4. Combinar el modulo con módulos anteriores.

• Notación asintótica
Manera de simplificar el tiempo de ejecución de un algoritmo.
Como se quiere conocer la eficiencia de un algoritmo, y la eficiencia
solo se puede conocer en un momento donde el tamaño de las
entradas es grande, entonces se usara un análisis asintótico.
Un análisis asintótico permite saber como se comporta un algoritmo
cuando el tamaño de la entrada es lo suficientemente grande. Permite
ignorar términos de orden menor y eliminar coeficientes constantes.
Solo se usaran los términos de mayor orden

En análisis de algoritmos, los términos caso peor, caso mejor y caso
promedio tienen los siguientes significados:
• Caso mejor: es la situación inicial de los datos que se genera al
ejecutar un algoritmo con una menor complejidad computacional
• Caso peor: es la situación inicial de los datos que genera la ejecución
del algoritmo con una complejidad computacional mayor
• Caso promedio: la situación inicial de los datos no sigue ningún patrón
preestablecido que aporte ventajas o desventajas. Por lo tanto se le
puede ver como la situación típica de ejecución del algoritmo.

• O-grande
Comúnmente escrito como O, es una notación asintótica para el peor
caso, o el techo de crecimiento para una función determinada. si f(n) es
el tiempo de ejecución del algoritmo, y g(n) es un tiempo de
complejidad arbitraria que relaciona con el algoritmo, entonces f(n) es
O(g(n)), si por cualquier constante real c(c>0), f(n)<=c g(n) para cada
tamaño de entrada n(n>0).
En el siguiente video se da otra
explicación de la O-grande (
https://www.youtube.com/watc
h?v=dyw0SohyEkw&t=216s
) Duración 5:28
índice
( M.I.I. Raquel Martínez
UNIDAD 3:
ALGORITMOS
RECURSIVOS

Recursividad
Así se le llama al proceso en el que una función se llama a si misma de
forma repetida, hasta que se satisface alguna condición determinada. el
proceso se utiliza para computaciones repetidas en las que cada acción
se determina un resultado anterior.

dentro de una función recursiva suelen distinguirse dos partes:
• Los casos base. Son aquellos que para su solución no requieren
utilizar la función que se esta definiendo
• Los casos recursivos. Aquellos que si requieren utilizar la función que
se esta definiendo
Las definiciones recursivas funcionan solo cuando las llamadas
recursivas se realicen de forma que en un momento se llegue a los
casos base.
Una función es recursiva final cuando ya no hay que realizar ningún
proceso adicional después de la llamada recursiva
¿Por qué escribir programas recursivos?
• Son mas cercanos a la descripción matemática
• Mas fáciles de analizar
• Mejor adaptación a las estructuras de datos recursivas
• Los algoritmos recursivos ofrecen soluciones estructuradas,
modulares y simples

Factible de utilizar recursividad:
• Simplificación de código
• Cuando la estructura de datos es recursiva. Por ejemplo los arboles
No factible usar recursividad:

• Cuando los métodos usen arreglos largos
• Cuando el método cambia los campos de manera impredecible
• Cuando las iteraciones sean la mejor opción
En este video se muestra como funciona una función recursiva en un
lenguaje de programación (
índice https://www.youtube.com/watch?v=i9roxX8z7tk)
Listas
Es una sucesión de nodos en la que a partir de un nodo se puede
acceder al que ocupa la siguiente posición en la lista.
Los diferentes tipos de listas son: enlazadas, no enlazadas, ordenadas y
no ordenadas.
Las listas enlazadas usan punteros, cosa que las listas no enlazadas no
utilizan. Estos últimos son arreglos simples que ocupan memoria, a
diferencia de las listas enlazadas que son un conjunto de nodos que no
ocupan posición contigua de memoria

Las operaciones que una lista enlazada puede hacer son:
• Insertar: inserta un nodo con dato en la lista. Esta inserción puede ser
al principio o al final o bien en orden
• Eliminar: elimina un nodo de la lista, ya sea por la posición o por el
dato
• Buscar: busca un elemento en la lista
• Localizar: obtiene la posición del nodo en la lista
• Vaciar: borra todos los elementos de la lista
Tipos de listas enlazadas
• Listas simplemente enlazadas o listas simples
Solo cuentan con un puntero indicando el siguiente elemento.

• Listas circulares
Es una lista lineal en la que el ultimo nodo apunta al primero

• Listas doblemente enlazadas
Es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo
siguiente y otro al anterior.

Pilas
Estructura lineal de datos compuesta por una serie de datos en las que
las operaciones solo se pueden hacer en uno de sus extremos llamado
cima (tope o top). Dicha estructura es de tipo LIFO (Last In-First Out) y
se utiliza para buscar elementos en orden inverso a como entran.

Las operaciones básicas de una pila
• Insertar (push). La inserción se realiza en la cima de la pila, siendo la
cima el ultimo elemento que se inserto.
• Eliminar (pop). Cuando un dato es eliminado, el elemento que se

borra es el que esta ubicado en la cima de la pila, el que menos
tiempo lleva en la estructura

Aplicaciones en informática
• Evaluación de tipos de expresiones
• Cuadros de dialogo, pantallas y menús desplegables por la acción de
abrirse un cuadro encima de otro, y al cerrarse uno, el cuadro activo
es el ultimo que se ha abierto
• Simulación de recursividad

Colas
Es una estructura de datos compuesta por un conjunto de datos, los
cuales su inserción se hará por un extremo, final (rear) y la salida de los
mismos por el principio (front).
Es una estructura tipo FIFO (First In-First Out). Esto significa que el
primer elemento que entra es el primero en salir

Las colas se clasifican en: colas simples, circulares, con prioridad y
bicolas.
• Colas simples. El elemento se inserta por el final y se saca por el inicio
de la cola.
• Colas circulares. Colas cuyo ultimo elemento esta unido con el
primero

• Colas con prioridad. Los datos se atienden según el orden que se le
indico por una prioridad.
• Bicolas. Sus nodos pueden insertarse y eliminarse por ambos
extremos. Este tipo se clasifica en bicolas de entrada restringida y
bicolas de salida restringida
En el video se muestra como se trabaja con las

pilas y colas (
https://www.youtube.com/watch?v=DFuE0BgSPW
índice 0 M.I.I. Raquel Martínez
) duración 11:09
Bibliografía
http://decsai.ugr.es/~jfv/ed1/c/cdrom/cap6/cap66.htm
http://antares.sip.ucm.es/~fernando/pf/temas/recursion.html
https://www.uv.mx/personal/ocastillo/files/2011/04/Recursividad.pdf
http://www.colimbo.net/documentos/documentacion/113/FPII03_Estr
ucturas_lineales_de_datos.pdf
https://es.wikipedia.org/wiki/Cola_(inform%C3%A1tica)#Tipos_de_cola
s

UNIDAD 4:
ALGORITMOS DE
ORDENAMIENTO Y
BUSQUEDA

Búsqueda
La búsqueda es el proceso algorítmico de encontrar un elemento en un
conjunto de elementos. Normalmente regresa verdadero o falso
dependiendo si el elemento este o no presente.
• Búsqueda secuencial
Cuando los elementos se almacenan en una colección se dice que
tienen una relación lineal o secuencial. Cada elemento se almacena en
una posición relativa a los demás. Estas posiciones son los valores de
los índices de los datos individuales, y como estos índices están
ordenados, es posible buscarlos en secuencia.
En el video se explica como hacer una
índice búsqueda secuencial M.I.I. Raquel
( Martínez
https://www.youtube.com/watch?v=g4n2
• Búsqueda binaria
Esta búsqueda comienza examinando el elemento central. Si el
elemento seleccionado es el que se busca, entonces se ha terminado.
De lo contrario, se eliminara la mitad de los datos que sobran.
Si el elemento que se busca es mayor al elemento central, la mitad
inferior de la lista y el elemento central se pueden ignorar; dejando el
elemento buscado en la mitad superior en caso de que exista en la lista.
Se continua como empezó, escogiendo un elemento central y
dividiendo la lista en caso de no ser el elemento deseado.
En el video se explica como hacer una

índice búsqueda binaria M.I.I.
( Raquel Martínez
Ordenamiento
Es el proceso de ubicar elementos de una colección en un orden en
particular.
Del mismo modo que la búsqueda, la eficiencia de un algoritmo radica
en el numero de elementos que se esta procesando.

• Ordenamiento burbuja
Hace múltiples recorridos a lo largo de una lista. Compara los
elementos adyacentes e intercambia los que no están en orden. Cada
pasada en la lista ubica el siguiente elemento mas grande en su lugar
apropiado.
Este método se considera como el mas ineficiente debido a que debe
intercambiar elementos antes de que se conozca su ubicación final. Sin
embargo, puede servir en listas que requieran pocas pasadas para
saber si dicha lista ya esta ordenada
A continuación se explicara con detalle como
funciona el ordenamiento burbuja (
https://www.youtube.com/watch?v=uiiss0hP8xM)
índice duración 4:26 M.I.I. Raquel Martínez
• Ordenamiento por selección
Mejora el ordenamiento burbuja haciendo un único intercambio por
cada pasada a través de la lista. Para hacerlo, el ordenamiento por
selección busca el elemento con menor valor a medida que hace un
recorrido y, después de terminarla, lo acomoda en el lugar correcto.
En el video se muestra como es el
ordenamiento por selección (
https://www.youtube.com/watch?v=ZM
O3Fow05tg
) duración 6:00

• Ordenamiento por inserción
Siempre conserva una sublista ordenada en las posiciones inferiores de
la lista. Cada elemento nuevo se inserta de regreso en la sublista previa
de manera que la sublista ordenada sea un elemento mas larga.
A continuación se explicara como se

realiza el método (
https://www.youtube.com/watch?v=lY
NyL0HuWSg
) duración 9:34

• Ordenamiento por Shell
Nombrado así por el ingeniero y matemático estadounidense Donald
Shell que lo propuso en 1959.
Este método usa una segmentación entre los elementos. Compara
elementos que están distantes; dicha distancia decrece conforme el
algoritmo se ejecuta hasta la ultima fase, en la cual se comparan los
elementos adyacentes
En el siguiente video se explica como usar el método de

ordenamiento Shell (
https://www.youtube.com/watch?v=bv8rxkcZ_-o) duración
7:11
Tablas hash
Es una colección de elementos que se guarda para que sean mas fáciles
de encontrar mas adelante. Cada posición de la tabla puede contener
un elemento y se llama por un valor entero comenzando en 0
Las entradas de estas tablas están compuestas por dos componentes: la
clave y la información que se almacena

Las tablas hash están conformadas por un arreglo de entrada y por una
función de dispersión que ayuda a asociar una clave con una posición
en la tabla y hacer una mejor búsqueda de elementos

• Funciones hash
Asocia una clave con una posición en la tabla hash. Esta función es una
aplicación entre el conjunto domino de las claves X y el conjunto
dominio de direcciones D de la estructura. H: X-> D

Una función hash debe tener las siguientes propiedades:
• Los valores se deben repartir equiprobablemente
• La función se debe calcular de forma eficiente, para así evitar que el
calculo de h(x) sea lo que determine la complejidad de la búsqueda
• Los cambios de la clave deben tener un impacto en la función

Búsqueda por transformación de claves (hashing)
Hasting se basa en una transformación matemática con una función
que da la posición en que se almacenara o buscara una clave

• Plegamiento
Consiste en dividir la clave en distintas partes, para después
combinarlas ya sea con sumas o multiplicación para obtener el índice.
Ejemplo:
Vector de 100 posiciones
Clave: 28312405
Procedimiento:
H(clave)=283+124+05
H(clave)=412 (resultado que sobrepasa el limite del
vector, por lo tanto se truncara) 4|12 = 12
La clave se guardara en la posición 12

• Aritmética modular
Consiste en convertir la clave en entero dividiéndolo por el tamaño del
vector. El residuo de la división es la posición del vector donde se
almacenara
Ejemplo:
Clave:12325
Procedimiento:
H(clave) = 12325 MOD 100
H(clave) =25
La clave se guardara en la posición
25

• Función medio de cuadrados
Eleva al cuadrado la clave y toma los dígitos centrales como la
dirección.
La formula que define la función es: H(K)=dígitos centrales (K^2)+1.
Ejemplo:

Clave: 562
Procedimiento:
H(clave)=562^2
H(clave)=315844
la clave será guardada en la
posición 58
• Truncamiento
Consiste en tomar un numero de dígitos de la clave y formar una
posición en un arreglo. Se ignora parte de la clave para con el resto
formar un índice
La idea se basa en tener un listado de números, seleccionar cualquier

posición, como el 2,4 y 6; para así tener una posición en donde insertar
la clave. Ejemplo:
5700931  703
3498610  481
0056241 064
9134720  142
índice 5174829  142 M.I.I. Raquel Martínez
Bibliografía
https://runestone.academy/runestone/static/pythoned/SortSearch/toc
tree.html
https://es.slideshare.net/analivecastrovargas/funcion-hash-metodos-de
-divisi
https://es.slideshare.net/lutzhooo/algoritmos-de-busqueda-33624661

UNIDAD 5:
ALGORITMOS DE
RECORRIDO

Árbol
Es un conjunto de nodos y líneas. Un nodo es un elemento de
información que se encuentra en el árbol. Una línea es un par de nodos
ordenados, y a la secuencia de líneas se le llama ruta.

Características de un árbol
1.Un nodo indica un elemento de información
2.Todo árbol que no es vacío tiene un único nodo raíz
3.Un nodo X es descendiente directo de un nodo Y, si el nodo X es
apuntado por el nodo Y. X es hijo de Y
4.Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al
nodo Y. X es padre de Y

5.Los nodos que son descendientes directos (hijos) de un mismo nodo
(padre) son considerados hermanos.
6.Los nodos que no tienen hijos, se les conoce como terminal u hoja
7.Todo nodo que no es raíz, ni terminal u hoja se conoce como interior
8.El grado es el numero de descendientes directos de un determinado
nodo. Grado del árbol es el máximo grado de todos los nodos del árbol
9.Nivel es el numero de arcos que deben ser recorridos para llegar a un
destino
10.Altura del árbol es el máximo numero de niveles de todos los nodos

• A es la raíz del árbol
• B es hijo de A
• A es padre de B
• B y C son hermanos
• I, E, J, K, G, L son hojas
• B,D,F,C,H son nodos interiores
• El grado de nodo A es 2
• Nivel del nodo A es 1
• Nivel B es 2
• Altura del árbol 4

Árbol binario
Un árbol binario tiene como máximo dos subárboles en cada nodo; y siempre es necesario
distinguir entre el subárbol izquierdo y el derecho.

Clasificación de arboles binarios
Existen 4 tipos:
• A.B.Distinto
• A.B.similares
• A.B.Equivalentes
• A.B.Completos

 A.B.Similares
Son similares cuando sus
estructuras son idénticas, pero
• A.B.Distinto es diferente la información de
sus nodos
Si dos arboles binarios son distintos cuando sus estructuras son
diferentes, se dice que es un árbol binario distinto.

 A.B.Completos
Aquellos arboles cuyos
nodos excepto los del ultimo
• A.B. Equivalentes nivel tienen 2 hijos; el
subárbol izquierdo y el
Son los arboles que son similares y que la información en sus nodos es
derecho
la misma

Recorrido de un árbol binario
Existen tres formas de recorrer un árbol: en inorden, preorden y posorden.
Preorden En el video se explican las 3 formas
• Visitar la raíz de recorrer un árbol (
• Recorrer subárbol izquierdo https://www.youtube.com/watch?v=
• Recorrer subárbol derecho 95CgVIsOxLA&t=2s
)
Inorden
Duración 6:27
• Recorrer subárbol izquierdo
• Visitar la raíz
• Recorrer el subárbol derecho
Postorden
• Recorrer subárbol izquierdo
• Recorrer subárbol derecho
• Visitar raíz
Arboles binarios de búsqueda
La ventaja de utilizar un árbol es que se facilita la búsqueda.
Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda
de cualquier nodo tiene un valor mas pequeño que el nodo padre, y el
hijo de la derecha contiene un valor mas grande que el padre.

Grafo
Consiste en un conjunto finito cuyos miembros se les llaman vértices y
una familia finita de pares no ordenados de vértices cuyos elementos
se denominan aristas o arcos.

Componentes de un grafo
• Aristas. Relación entre dos vértices (nodos) de un grafo
• Aristas adyacentes. 2 aristas que se dirigen al mismo vértice y se
juntan en el
• Aristas paralelas. El vértice inicial y final son uno mismo.
• Cruce. Aristas que cruzan en un punto

• Grado o valencia de vértice. Numero de aristas que inciden sobre un
vértice
• Lazo. Es una arista cuales extremos se juntan sobre el mismo vértice
• Vértice. Nodos que conforman los grafos
• Vértice adyacente. Vértices están unidos con una arista

• Vértice aislado. Vértice de grado cero
• Vértice terminal. Vértice de grado 1

Tipos de grafos
• Grafo aciclico. Grafo que no contiene ningún ciclo
• Grafo cíclico. Tiene algún ciclo simple
• Grafo bipartito. Grafo con vértices que se pueden dividir en dos

conjuntos sin aristas

• Grafo completo
Cada vértice tiene un grado igual a n-1 y sus vértices son adyacentes
con otros vértices
• Grafo conexo
Si se puede formar un camino desde cualquier vértice a cualquier otro

• Grafo denso. El numero de aristas esta cerca al numero máximo de
aristas
• Grafo dirigido. Para cada arista perteneciente al conjunto de aristas

se asocia con 2 vértices
• Grafo no dirigido. Los lados no están orientados

• Grafo nulo. Grafo cuyos conjuntos de aristas y de vértices son vacíos
• Grafo plano. Es posible dibujar en el plano sin que se crucen aristas
• Grafo ponderado. Asocia un valor o peso a cada arista

Algoritmo de recorrido y búsqueda a lo ancho
Es un procedimiento para recorrer todas las vértices de un grafo. Es
practico para problemas de optimización, que es donde se debe
escoger la mejor solución entre las disponibles.
Explora sistemáticamente las aristas de forma que primero se visiten
los vértices mas cercanos al que se esta explorando.

Algoritmos de recorrido y búsqueda en profundidad
Recorre las ramas o aristas del grafo de manera que primero se ven los
nodos adyacentes a los visitados mas recientemente. Así se va alejando
del nodo inicial.
Búsqueda en profundidad
1.Empieza en el vértice inicial, marcándose como vértice activo
2.Hasta que todos los vértices hayan sido visitados, en cada paso se
avanza al vecino con el menor índice siempre que se pueda
3.Luego de visitar a todos los vecinos, se retrocede al vértice X desde el
que se alcanzo alexplican
En el video se vértice activo
ambos y toma su lugar.
algoritmos
índice (
https://www.youtube.com/watch?v=LGl
Bibliografía
https://es.slideshare.net/AlexisChavez1/rboles-y-grafos
estructuradedatos192.wordpress.com/acerca-de/
https://sites.google.com/site/matematicasmoralesgalindo/6-1-element
os-y-caracteristicas-de-los-grafos/6-1-1-componentes-de-un-grafo-verti
ces-aristas-lazos-valencia
https://sites.google.com/site/matematicasmoralesgalindo/6-1-element
os-y-caracteristicas-de-los-grafos/6-1-2-tipos-de-grafos-simples-comple
tos-bipartidos-planos-conexos-ponderados

Algoritmos Computacionlaes0123

Cargado por

Copyright:

Formatos disponibles

Algoritmos Computacionlaes0123

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmos Computacionlaes0123

Cargado por

Copyright:

Formatos disponibles

ALGORITMOS COMPUTACIONALES

M.I.I. Raquel Martínez

M.I.I. Raquel Martínez

• De esta manera, ante un problema de cualquier tipo el software puede seguir

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

Para la representación de un algoritmo se utilizan algunos métodos de

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

Es la más sencilla , también se le

Son problemas muy sencillos.

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

Cualquier programa bien diseñado consta de un programa principal (el

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

No factible usar recursividad:

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

• Eliminar (pop). Cuando un dato es eliminado, el elemento que se

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

En el video se muestra como se trabaja con las

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

En el video se explica como hacer una

índice M.I.I. Raquel Martínez

índice M.I.I. Raquel Martínez

A continuación se explicara como se