Agregar a favoritos      Ayuda      Português      Ingles     
 Página anterior Volver al principio del trabajoPágina siguiente 

Diagramas de flujo Métodos de la burbuja-Métodos de búsqueda (página 2)




Partes: 1, 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:

  • Consume bastante tiempo de computadora
  • Requiere muchas lecturas/escrituras en memoria.

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 del vector.

Compara cada elemento del vector con el que se desea encontrar.

Divide el espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento deseado.

Se examina el primer vector partiendo del primer elemento hasta llegar al último.

Se examina el vector partiendo desde el elemento central de la lista.

Consume excesivo tiempo en la localización del elemento designado, por ello es recomendable para vectores de pocos datos.

Eficiente con relación al tiempo, si el vector esta ordenado por ello, por ello es recomendable para conjunto de grandes datos.

Ventajas y desventajas:

Secuencial

Binaria

Consumo excesivo de tiempo en la localización del elemento a encontrar si el vector contiene grandes cantidades de elementos, ya que recorre todo el vector.

No es necesario que el vector este ordenado.

No es factible para vectores con grandes números de elementos.

Divide el espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Recorre todo el vector, desde el primero hasta el último elemento.

Se examina primero el elemento central de la lista o sublista.

Es necesario que el vector este ordenado.

Factible para vectores con grandes cantidades de elementos.

 

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


Partes: 1, 2


 Página anterior Volver al principio del trabajoPágina siguiente 

Comentarios


Trabajos relacionados

Ver mas trabajos de General

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.