viernes, 7 de noviembre de 2008

Estructura de Datos

Una estructura de datos es: un cojunto de elementos ordenados y sistematizados.
estructura de control nos permite tomar decisiones tipo boleano (verdadero o falso) (if, if then, if then else, case, switch) estructuras iterativas tambien llamadas en iteración (repetición) while for: son los arreglos Do while: punteros son: variables tipos flotantes dentro de un vector busqueda acendente y decendente

Estructura de control.- un conjunto de parametro o relgas para el ordaneamiento de datosNos pèrmiten tomar decisiones boleanos (verdaderas o falso ):-- if-- ifthen-- ifelse
Son if aninadados:-- case-- swithEstructuras iteractivas (repeticion)Son aciones repetitivas que se vuelven a repetir en ejecucionWhileFordowhilePunteros son variables que se mueven dentro de un vector o indices.


Actividad de la clase.-

ejercicio 1.- declarar una matris 3 * 3 que corra de manera horizontal

ejercicio 2.- declarar una matris de 2*2 Multiplicar una matris x 2

ejercicio 3.- Hacer un arreglo y ver en que posición este un dato de 3*3 en la posición 2,1

Algoritmo ejercicio 1
int a [1.3]; int x,y
for x=1 hasta y=3
for y=1 hasta y=3
a[x.y]= a[x.y]= mas 1;
imprimir a [x,y]

Algoritmo del ejercicio 2
int a [1.3]; int x,y

for x=1 hasta y=3
for y=1 hasta y=3a[x.y]=
a[x.y]= mas 1;
imprimir a [x,y] + 2

Algorito del ejercicio 3
int A [1.3] [1.3]
int b [1.3] [1.3]
for x=1 hasta x=3
for y=1 hasta y=3
a [w.y] = a[w.y] mas 1
imprimir x,y

Definición de Métodos de Ordenación

Las estructuras de datos son utilizadas para almacenar información, para poder recuperarla de manera eficiente es deseable que esté ordenada. Existen varios métodos para ordenar la información, los cuales tienen como finalidad organizar los datos en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética, etc.). Atendiendo al tipo de elemento que se quiera ordenar la ordenación puede ser:

  • Ordenación interna: Los datos se encuentran en memoria (ya sean arreglos, listas, etc.), y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores).
  • Ordenación externa: Los datos están en un dispositivo de almacenamiento externo (archivos), y su ordenación es más lenta que la interna.

Métodos de Búsqueda ( secuencial, binaria, indexado, hashing)

Búsqueda Secuencial:

La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.

Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. Y así poder encontrar el dato requerido.

Búsqueda Binaria:

La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Este método se puede aplicar tanto a datos en listas lineales como en
árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:
La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.
Debe conocerse el número de elementos.
Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y vencerás:
1.-Se divide el elemento en dos partes.
2.-Se determina la parte que debe contener la clave buscada.
3.-Se repite el proceso en esa parte.

Búsqueda Indexada:
En este modo de organización, al fichero le acompaña un fichero de índice que tiene la función de permitir el acceso directo a los registros del fichero de datos.El índice se puede organizar de diversas formas, las más típicas son: secuencial, multinivel y árbol.A través del índice podremos procesar un fichero de forma secuencial o de forma directa según la clave de indexación, y esto independientemente de como esté organizado el fichero por sí mismo.El índice debe estar organizado en función de alguno de los campos de los registros de datos. Se pueden tener tantos índices como se quiera variando la clave (o campo) que se emplee. El índice está formado por registros (entradas) que contienen:
Clave de organización.
Puntero(s) al fichero de datos, en concreto al registro que corresponda.

Búsqueda Hashing:
En este método se requiere que los elementos estén ordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar.

miércoles, 22 de octubre de 2008

Metodo de la burbuja

El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.


Visual Basic for Applications
Sub ORDENAR()
Dim X As Integer
Dim I As Integer
Dim y As Double
Dim j As Integer

X = 1
For I = 1 To 10
Cells(I, 1) = Rnd
Next I

For I = 1 To 9
For j = I + 1 To 10
If Cells(I, 1) < Cells(j, 1) Then
y = Cells(j, 1)
Cells(j, 1) = Cells(I, 1)
Cells(I, 1) = y
End If

Next j
Next I

End Sub


Visual Basic .NET
Module Burbuja

" Con Este algoritmo podras ordenar un conjunto de numeros que esten dentro de un vector de menor a mayor e imprimirlos al final "
( Es una aplicacion de consola como veran )

Sub Main()
Dim i, v(10), j, aux As Integer

'''Se dimencionan las variables i y j para los siclos repetitivos ( for)
y el vector v con que va a contener 10 posiciones V(10) y la variable aux que nos servira como auxiliar para el intercambio de valores '.''


For i = 1 To 10
Console.WriteLine(" Digite Un numero para la casilla " & i & " del vector :")
v(i) = Console.ReadLine

Next

For i = 1 To 10

For j = 1 To 10 - 1

If v(j) > v(j + 1) Then

aux = v(j)
v(j) = v(j + 1)
v(j + 1) = aux


End If
Next

Next

For i = 1 To 10
Console.WriteLine(v(i))
Console.ReadLine()


Next

End Sub

End Module

C
void bubble(int *start, int *end) //Ordena un conjunto de números enteros de menor a mayor
{
short fin;
do
{
fin=0;
for (int *i=start;i!=*end;i++)
{
if (*i>*(i+1))
{
intercambia(i, i+1);
fin=1;
}
}
}while (fin!=1);
}

C (Ejemplo 2)
void bubble(int A[], int tamano_arreglo) //Ordena un arreglo de números enteros de menor a mayor
{
int temp, j, i;
for(i = (tamano_arreglo-1); i >= 0; i--)
{
for(j = 1; j <= i; j++)
{
if(A[j-1] > A[j])
{
/* Intercambio de numeros*/
temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;
}
}
}
}

jueves, 16 de octubre de 2008

Método intercambio directo

Intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el más utilizado por los estudiantes principiantes de computación, por su fácil comprensión y programación.

Definición Breve: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.

El método de intercambio directo puede trabajar de dos maneras diferentes.
llevando los elementos más pequeños hacia la parte izquierda del arreglo.
llevando los elementos más grandes hacia la parte derecha del mismo.
La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados.

Ejemplo: Arreglo {40,21,4,9,10,35}:

Primera pasada:{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.

{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.
Segunda pasada:{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.
{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.

Método de Ordenación

Método de Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.

Método de Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.

Método de Inserción Directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.



Método Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.



Método HeapSort:
El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Ejemplo en:
http://es.wikipedia.org/wiki/Heapsort

Método QuickSort: Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo.Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.

Método MergeSort:

Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.
Conquistar: Se resuelven recursivamente los problemas más chicos.
Combinar: Los problemas mas chicos de combinan para resolver el grande.


Mezcla.
Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.
Ejemplo:
A: 06 09 18 20 35

B: 10 16 25 28 66 82 87

C: 06 09 10 16 18 20 25 28 35 66 82 87

Monticulo:

Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
- Construir un montículo.
-Eliminar la raíza del montículo en forma repetida.

Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".


Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.

La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.

METODO RADIX

El siguiente método que consideramos se denomina ordenamiento de raíz. Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo, el numero 235 es en notación decimal que se escribe con un 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. El mas grande de dos enteros de igual longitud se determina del modo siguiente: empezar en el digito mas significativo y avanzar por los dígitos menos significativos mientras coincidan los dígitos correspondientes en los dos números. El numero con el digito mas grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos. Por supuesto, si coinciden todos los dígitos de ambos números, los números son iguales.

Búsqueda por hash

Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado. La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2) Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.


martes, 30 de septiembre de 2008

Resumen de links

http://www.infovis.net/printMag.php?num=137&lang=1



En este primer link menciona lo que es un grafo y como estan compuestos también habla acerca de un ejemplo de una ciudad que tiene 7 puentes y de como se puede cruzar toda la ciudad por todos los puentes una sola ves pasando por estos, en donde en realidad mencionan que no había una respuesta precisa donde el autro Euler realizó una abstracción del problema representando mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada dos puntos por cada puente buscando una solucion por medio de la herramienta matemática llamada grafos y también así como dan formas o mas bien reglas estáticas que sirven para dibujar un solo grafo y no una sucesión de ellos de forma dinámica.

Reglas básicas

Reglas semánticas

Reglas estructurales

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

En matemáticas y en la computación está teoría es llamada también la teoria de graficas y explica también que es un grafo, así como también viene su histroria, su estructura y cada una de las definiciones de los elementos que conforman un grafo.

en el segundo link nos menciona una breve historia de como inicio la teoria de grafos, concidero que esta pagina es más explicativa he interesante aun que en el primer link nos resume lo que son los grafos y nos lo pone por medio de un ejemplo y en este segundo link es mas como pura teoria interesante pero te dan como se dan los grafos entre otras cosas.

Y pues esto son mis comentarios espero les gusten