Diagramas de flujo Métodos de la burbuja-Métodos de búsqueda (página 2)
Explique cada
uno de los símbolos que se usan en la solución
de problemas con
diagramas de
flujo.
Inicio y/o fin del diagrama de
flujo.
Ejercicios.
Realizar el diagrama de
flujo que calcule el área de un triangulo.
Realizar el diagrama de flujo que dado un número
entero positivo determine si es par o impar.
Defina y
explique de forma clara y sencilla, el método de
ordenación por burbuja. Cite sus ventajas y
desventajas.
Este método consiste en acomodar el vector
moviendo el mayor hasta la última casilla comenzando desde
la casilla cero del vector hasta haber acomodado el número
más grande el la última posición, una vez
acomodado el más grande, prosigue a encontrar y
acomodar el siguiente más grande comparando de nuevo los
números desde el inicio del vector, y así sigue
hasta ordenar todo los elementos el arreglo. Este algoritmo es
muy deficiente ya que al ir comparando las casillas para buscar
el siguiente más grande, éste vuelve a comparar las
ya ordenadas. A pesar de ser el algoritmo de ordenamiento
más deficiente que hay, éste es el más usado
en todos los lenguajes de
programación.
Entonces:
Dado un vector a1, a2,
a3, … an
1) Comparar a1 con a2 e
intercambiarlos si a1>a2 (o
a12)
2) Seguir hasta que todo se haya comparado
an-1 con an
3) Repetir el proceso
anterior n-1 veces
Algoritmo Basico.
Repetir desde (i:=0 hasta i < n-1; i++)
Repetir desde (j:=0 hasta j < n-1; j++)
Si (vec[j] > vec[j+1])
Inicio
Aux:= vec[j];
vec[j] := vec[j+1];
vec [j+1]= aux;
Fin
Fin_Si
Fin_Repetir
Fin_Repetir
El procedimiento de
la burbuja es el siguiente:
- Ir comparando desde la casilla 0 numero tras
número hasta encontrar uno mayor, si este es
realmente el mayor de todo el vector se llevará
hasta la última casilla, si no es así,
será reemplazado por uno mayor que
él. - Este procedimiento seguirá así hasta
que halla ordenado todas las casillas del vector. - Una de las deficiencias del algoritmo es que ya
cuando a ordenado parte del vector vuelve a compararlo cuando
esto ya no es necesario.
Ventajas del método de ordenación por
burbuja:
- Es bastante sencillo
- En un código reducido se realiza el
ordenamiento - Eficaz
Desventajas del método de ordenación
por burbuja:
Ejemplo:
Variables | Vector | |||||||||||
pos | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
i | j | a[j] | a[j+1] | inicio | 44 | 55 | 12 | 42 | 94 | 18 | 6 | 67 |
0 | 1 | 55 | 12 | cambio | 44 | 12 | 55 | 42 | 94 | 18 | 6 | 67 |
0 | 2 | 55 | 42 | cambio | 44 | 12 | 42 | 55 | 94 | 18 | 6 | 67 |
0 | 4 | 94 | 18 | cambio | 44 | 12 | 42 | 55 | 18 | 94 | 6 | 67 |
0 | 5 | 94 | 6 | cambio | 44 | 12 | 42 | 55 | 18 | 6 | 94 | 67 |
0 | 6 | 94 | 67 | cambio | 44 | 12 | 42 | 55 | 18 | 6 | 67 | 94 |
1 | 0 | 44 | 12 | cambio | 12 | 44 | 42 | 55 | 18 | 6 | 67 | 94 |
1 | 1 | 44 | 42 | cambio | 12 | 42 | 44 | 55 | 18 | 6 | 67 | 94 |
1 | 3 | 55 | 18 | cambio | 2 | 42 | 44 | 18 | 55 | 6 | 67 | 94 |
1 | 4 | 55 | 6 | cambio | 12 | 42 | 44 | 18 | 6 | 55 | 67 | 94 |
2 | 2 | 44 | 18 | cambio | 12 | 42 | 18 | 44 | 6 | 55 | 67 | 94 |
2 | 3 | 44 | 6 | cambio | 12 | 42 | 18 | 6 | 44 | 55 | 67 | 94 |
3 | 1 | 42 | 18 | cambio | 12 | 18 | 42 | 6 | 44 | 55 | 67 | 94 |
3 | 2 | 42 | 6 | cambio | 12 | 18 | 6 | 42 | 44 | 55 | 67 | 94 |
4 | 1 | 18 | 6 | cambio | 12 | 6 | 18 | 42 | 44 | 55 | 67 | 94 |
5 | 0 | 12 | 6 | ordenado | 6 | 12 | 18 | 42 | 44 | 55 | 67 | 94 |
Defina y explique de forma clara y sencilla, el
método de búsqueda secuencial y binaria.
Diferencias fundamentales, ventajas y desventajas entre
ambos.
Métodos de Búsqueda:
La recuperación de información como ya se ha comentado, es una
de las aplicaciones más importantes de la
computadora.
La búsqueda (searching) de información
esta relacionada con la tablas para consultas (lookup). Estas
tablas contienen una cantidad de información que se
almacena en forma de listas de parejas de datos. Por
ejemplo, un diccionario
con una lista de palabras y definiciones; un catálogo con
una lista de libros de
informática; una lista de estudiantes y sus
notas; un índice con títulos y contenidos de los
artículo publicados en una determinada revista, etc.
En todos estos casos es necesario con frecuencia buscar un
elemento en una lista.
Una vez que se encuentra el elemento, la
identificación de su información correspondiente es
un problema menor. Por consiguiente, nos centraremos en el
proceso de búsqueda. Supongamos que se desea buscar
el vector X [1]… X [n], que tiene componentes
numéricos, para ver si contiene o no un número dado
de T.
Si en vez de tratar sobre vectores, se
desea buscar información en un archivo; debe
realizarse la búsqueda a partir de un determinado campo de
información denominado campos claves. Así en el
caso de archivos de
empleados de una empresa, el
campo clave puede ser el número de DNI o los
apellidos.
La búsqueda por claves para localizar registros es, con
frecuencia, una de las acciones de
mayor consumo de
tiempo conlleva y, por consiguiente, el modo en que los registros
están dispuestos y la elección del modo utilizado
para la búsqueda pueden redundar en una diferencia
sustancial en el rendimiento del programa.
El problema de búsqueda cae naturalmente de los
casos típicos ya tratados. Si
existen muchos registros, pueden ser necesario almacenarlo en
archivos de discos o cintas, externo a la memoria de
la computadora. Este caso se llama Búsqueda Externa. En el
otro caso los registros que se buscan se almacenan por completo
dentro de la memoria de la computadora, este caso se llama
Búsqueda Interna.
En la práctica, la búsqueda se refiere a
la operación de encontrar la posición de un
elemento entre un conjunto de elementos dados: lista, tabla o
fichero.
Ejemplos típicos de búsquedas
son:
Localizar nombre y apellido de un alumno, localizar
número de teléfono de una agenda, etc.
Existen diferentes algoritmos de
búsqueda. El algoritmo elegido depende de la forma en que
se encuentren organizados los datos.
La operación de búsqueda de un elemento N
en un conjunto de elementos consiste en:
Determinar si N pertenece al conjunto y en ese caso
indicar su posición en el.
Determinar si N no pertenece al conjunto.
Los métodos
usuales de búsqueda son:
Método de Búsqueda
Secuencial:
Supongamos que una lista de elementos almacenados en un
vector (array unidimensional). El método sencillo de
buscar un elemento en un vector es explorar secuencialmente el
vector, o dicho entre otras palabras recorrer el vector desde el
primer elemento hasta el último. Si se encuentra el
elemento buscado visualizar un mensaje similar a ‘fin de
búsqueda’, en caso contrario visualizar un mensaje
similar a ‘elemento no existe en la
lista’.
En otras palabras, la búsqueda secuencial compara
cada elemento del vector con el valor deseado,
hasta que este se encuentra o se termina de leer el vector
completo. La búsqueda secuencial no requiere ningún
requisito por parte del vector y, por consiguiente, no necesita
estar ordenado. El recorrido del vector se realizará
normalmente con estructuras
repetitivas.
Método de Búsqueda
Binaria:
En una búsqueda secuencial se comienza con el
primer elemento del vector y se busca en el hasta que se
encuentra el elemento deseado o sea alcanza el final del
vector.
Aunque este puede ser un método adecuado para
pocos datos, se necesita una técnica más eficaz
para conjuntos
grandes de datos.
Si el número de elementos del vector es grande,
el algoritmo de búsqueda lineal se ralentizaría en
tiempo de un modo considerable. Por ejemplo, si tuviéramos
que consultar un nombre en la guía telefónica de
una gran ciudad, como Madrid, con
una cifra aproximada de un millón de abonados, el tiempo
de búsqueda, según el nombre se podría
eternizar naturalmente, las personas que viven en esa gran ciudad
nunca utilizarán un método de búsqueda
secuencial, sino un método que se basa en la
división sucesiva del espacio ocupado por el vector en
sucesivas mitades hasta encontrar el elemento buscado.
Si los datos que se buscan están clasificados en
un determinado orden, el método citado anteriormente se
denomina Búsqueda Binaria.
La búsqueda binaria utiliza un método de
‘divide y vencerás’ para localizar el valor
deseado. Con este método se examina primero el elemento
central de la lista; si este es el elemento buscado, entonces la
búsqueda ha terminado. En caso contrario, se determina si
el elemento buscado está en la primera o en la segunda
mitad de la lista y a continuación se repite este proceso,
utilizando el elemento central de esa sublista.
El proceso de búsqueda debe terminar normalmente
conociendo si la búsqueda ha tenido éxito
(se ha encontrado el elemento o bien no ha tenido éxito)
no se ha encontrado el elemento, normalmente se deberá
devolver la posición del elemento buscado dentro del
vector.
Diferencias fundamentales:
Secuencial | Binaria |
El vector debe estar ordenado. | No requiere ningún requisito por parte |
Compara cada elemento del vector con el que se | Divide el espacio ocupado por el vector en |
Se examina el primer vector partiendo del primer | Se examina el vector partiendo desde el elemento |
Consume excesivo tiempo en la | Eficiente con relación al tiempo, si el |
Ventajas y desventajas:
Secuencial | Binaria |
Consumo excesivo de tiempo en la | No es necesario que el vector este |
No es factible para vectores con grandes | Divide el espacio ocupado por el vector en |
Recorre todo el vector, desde el primero hasta | Se examina primero el elemento central de la |
Es necesario que el vector este | Factible para vectores con grandes cantidades de |
Conclusión.
Los diagramas de
flujo son importantes ya que ayudan al usuario a entender el
procedimiento y muestra el
sistema como
una red de
procesos
conectados entre si, por las llamadas tuberías y
depósitos de datos que describe sus movimientos a
través del sistema, a su vez, es importante destacar que
no es indispensables usar un tipo especial de símbolos
para crear diagramas, pero existen algunos ampliamente
utilizados, por lo que es adecuado conocerlos y utilizarlos,
ampliando así las posibilidades de crear flujograma mas
claro y compresible como proceso lógico y con opciones
múltiples o adecuadas.
Los método usuales de búsqueda son:
búsqueda secuencial o lineal, el cual consiste en comparar
cada elemento del vector con el valor deseado hasta que se
encuentra o termine de leer el vector completo, aunque este puede
ser un método adecuado para pocos datos, se necesita una
técnica mas eficaz para conjuntos grandes de datos, en
este caso, se utilizara la búsqueda binaria, que consiste
en examinar primero el elemento central de la lista si este es el
elemento buscado, entonces, la búsqueda a terminado, en
caso contrario se repite el proceso.
De acuerdo y debido a lo antes mencionado se hace
relevante las ventajas y desventajas dentro de cada uno de los
procesos, presentándose diferencias dentro de los mismos
debido a la eficacia de cada
método.
El método de ordenación por burbuja es muy
sencillo ya que esta basado en ordenar los elementos de una lista
con la siguiente, intercambiándolos de posición si
están en orden equivocado como si fueran burbujas,
conocido también como el método de intercambio
directo.
Recomendaciones.
Para la construcción de un diagrama debemos tener
en cuenta algunos pasos fundamentales, para lograr la
resolución exitosa del problema:
Preparación de la construcción del
diagrama
Paso 1: Establecer quiénes deben participar en
su construcción.
Paso 2: Preparar la logística de la sesión de trabajo.
Desarrollo de la construcción
Paso 3: Definir claramente la utilización del
Diagrama de Flujo y el resultado que se espera obtener de la
sesión de trabajo.
Paso 4: Definir los límites
del proceso en estudio.
Paso 5: Esquematizar el proceso en grandes bloques o
áreas de actividades.
Paso 6: Identificar y documentar los pasos del
proceso.
Paso 7: Realizar el trabajo
adecuado para los puntos de decisión o
bifurcación.
Paso 8: Revisar el diagrama completo.
Este proceso aumentara las probabilidades de que la
solución al problema sea aceptable.
A la hora de utilizar el método de intercambio
directo, deberá tener en cuenta otras soluciones mas
sencilla al problema, ya que esta técnica a medida que los
elementos a ordenar sean mayores, gastará mas tiempo en el
computador y
requerirá de mucha lectura y
escritura del
disco.
Por otra parte, si necesita un método de
búsqueda eficaz, lo mas recomendado cuando se manejan
grandes magnitudes de elementos, será utilizar el
método de búsqueda binario, si por el contrario, el
conjunto de los elementos es menor, podrá seleccionar
entre el ya antes mencionado y el método de
búsqueda secuencia, ya que en pequeñas cantidades
de información la diferencia de eficacia entre estos
métodos no se hace tan notoria.
Referencias informativas.
http://es.wikipedia.org/wiki/Diagrama_de_flujo
http://www.mis-algoritmos.com/ejemplos/diagramas-flujo.html
http://www.monografias.com/trabajos14/flujograma/flujograma.shtml
http://www.elprisma.com/apuntes/ingenieria_industrial/diagramasdeflujo/
http://www.fundibeq.org/metodologias/herramientas/diagrama_de_flujo.pdf
http://www.estructuradedatos.galeon.com/burbujatext.htm
Bachilleres:
Karolann Solís
Marielis Malave
José Paredes
Karla Teresa Martínez Pinto
Republica Bolivariana de Venezuela.
Ministerio de Educación
Superior.
Universidad Nacional Experimental de Guayana.
Vicerrectorado Académico
Ingeniería en Informática
Introducción a la Informática.
Facilitador:
William Mercado
Puerto Ordaz, Enero de 2008
Página anterior | Volver al principio del trabajo | Página siguiente |