Archivos y Registros

Registros
Es una estructura heterogénea denominados campos y a los que accedemos por su nombre. al igual que otro dato, debemos declarar el tipo registro antes de utilizar.

De las operaciones que podemos realizar con los registros de encuentra la lectura y la asignación, tambien puede ser utilizado como parametro en los metodos.

Archivos
Es una estructura homogénea de datos consistentes en una secuencia de datos llamada registros, tambien se le denomina ficheros a lo archivos, es una colección de datos relacionados entre si, localizada y almacena como una unidad en alguna parte del computador.

Los archivos pueden ser constrastados con arrays y registros, los archivos no tienen un tamaño fijo por lo que se pueden hacer archivos grandes o pequeños segun se necesiten.

con los archivos al igual que con otras estructuras podemos realizar varias operaciones entre las que encontramos Read (lectura del registro actual), Write (escritura sobre registro actual), Close (cerrar el archivo), etc.

Bibliografia

• Registros y Archivos, consulta [4 de junio de 2010], http://www.terra.es/personal2/cesar.zm/diez.htm
• Achivos de registros, consulta [3 de junio de 2010], http://www.hospedajeydominios.com/mambo/documentacion-manual_rh9cg-pagina-ch_logfiles.html
• Creacion de un archivo en java, consulta [4 de junio de 2010], http://todojava.awardspace.com/ejemplos-java.html?desc=CrearArchivoAleatorio
• Archivos, consulta [4 de junio de 2010], http://www.monografias.com/trabajos7/arch/arch.shtml
• Registros, consulta [5 de junio de 2010], http://www.monografias.com/trabajos7/regi/regi.shtml
  

Pilas y Colas

Esta clase fue interesante, se nos explico la estructura de las pilas y colas con ejemplos relacionados con la vida real. Estas estructuras se pueden complementar utilizando las listas de la cuales hablamos anteriormente.

Pilas

Estas estructuras son muy utilizadas como herramientas de programacion de tipo L.I.F.O "last in- first out"lo cual significa ultimo en entrar primero en salir, en esta estructura solo se puede ingresar por un solo extremo de la misma, por lo que sus operaciones se llevan a cabo por ese lado. Entre sus operaciones encontramos apilar (agregar) y desempilar (quitar).

Colas
Estas estructuras son de tipo F.I.F.O "first in- first out" lo cual traduce primero en entrar primero en salir, estas simulan colas en la vida real como la de un banco, son herramientas de programacion como las pilas, pero una de sus diferencias es que sus operaciones no se llevan a cabo solo por un extremos de la cola. entre sus operaciones encontramos encolar el cual agrega un nuevo dato al final de cola, y Atender el cual elimina un dato del principio de la cola.

Las pilas y colas son eficientes ya que el tiempo de ejecucion no depende de su tamaño y sus metodos se realizan en tiempo constante, sin necesidad de comparaciones.

Bibliografia

• Estructuras de datos: Listas enlazadas, Pilas y Colas, consulta[6 de junio de 2010],http://www.calcifer.org/documentos/librognome/glib-lists-queues.html

• Pilas y Colas, consulta [5 de junio de 2010], http://html.rincondelvago.com/pilas-y-colas.html

• Pilas y Colas, consulta [4 de junio de 2010],http://trajano.us.es/clases/programacion/04-05/documentos/practica06.pdf

• Pilas y Colas, consulta [6 de junio de 2010],http://programacion/bppr12/Clases/SegundoCorte/PilasColas.ppt

Listas

Estas clases fue una de las mas dificiles ya que nos toco reforzar la definicion individualmente, pues no tuvimos los aciertos que se esperaban pero de igual forma fue interesante.

Al momento de definir una lista encontramos que es que es una estructura de datos que sirve para complementar otras estructuras. Consiste en una secuencia de nodos en los que guardamos datos (item, nombres..etc) y referencias dependiendo de la lista que utilicemos. Existen varios tipo de listas entre los que encontramos:

Listas enlazadas Simples: Es la lista enlazada basica esta tiene una referencia hacia el nodo siguiente (si existe), pero si se encuentra en el ultimo nodo esa referencia es nula.

Listas enlazadas Dobles: Esta es un poco mas compleja ya que tiene una referencia al siguiente y una referencia al anterior, si es el primer nodo la referencia anterior es nula y si nos encontramos en el ultimo nodo la referencia siguiente es nula.

Listas circulares Simples: Esta es muy parecida a una lista enlazada simple, su diferencia radica en que su referencia al siguiente en el ultimo nodo no es nula, sino que indica hacia el primer nodo utilizado, para recorrer una lista circular simple podemos empezar por cualquier nodo y continuar hasta llegar al nodo original, por eso se le llama las listas sin comienzo ni fin.

Listas circulares Dobles: Sus referencias son como las de una lista doblemente enlazadas, excepto que el ultimo nodo apunta al primero y el prime r nodo apunta al ultimo formando el ciclo, esta tampoco tiene comienzo ni fin.

Estas listas son utilizadas para la realizacion de otras estructuras de datos co m o pilas y colas, y con ellas podemos realizar muchas operaciones como:

• Recorrido: Consiste en visitar cada uno de los nodos de la lista, comenzando por el primero se toma el valor del item y su referencia para pasar al siguiente y asi sucesivamente hatsa que ese valor sea nulo o vuelva a la cabeza, eso significara que acabo un ciclo.

• Inserción: Consiste en agregar un nodo nuevo a la lista, se puede hacer de tres formas: insertando al inicio, insertando al final e insertando en una posición especifica.
  

• Borrado: Consiste en quitar un nodo de la lista, tiene cuatro casos: eliminar primer nodo, elminar ultimo nodo, eliminar nodo con cierta información y eliminar un nodo en cualquier posición.

• Busqueda: Utilizamos el metodo recorrido, pero buscando un nodo en especial o el item que se encuentra en el.

Bibliografia

• Listas, consulta [3 de junio de 2010], http://c.conclase.net/edd/index.php?cap=001
• Listas enlazadas, consulta [4 de junio de 2010], http://www.mygnet.net/articulos/java/listas_enlazadas.76
• Listas simplemente enlazadas, consultas [5 de junio de 2010],http://www.javamexico.org/blogs/pain5610/estructura_de_datos_java_listas_simplemente_enlazadas_primer_aporte
• Java-Lista, consulta [3 de junio de 2010], http://www.scribd.com/doc/11410360/JavaListas
  

Backtracking

Esta clase fue un poco divertida ya que nos abrio camino hacia aquellos problemas o juegos que tanto nos gustan en la vida y para los cuales muchas veces no tenemos solucion clara, ejemplos claros son los problemas del sudoku o las ocho reinas en un tablero.

Bueno enfocándonos un poco mas en el tema encontramos que es una estrategia para hallar soluciones a problemas que presentan ciertas restricciones construyendo posibles soluciones candidatas de manera sistemática para al final dar una solución general, a esta estrategia también se le suele llamar “vuelta atrás” porque al no encontrar una solución satisfactoria deshará esa acción y volverá a que se realizo anteriormente.

El problema de las ocho reinas.

En este problema consiste en colocar 8 reinas en un tablero de ajedrez de tal manera que ninguna quede atacando a otra.

En este caso colamos la primera ficha y avanzamos horizontalmente uno por uno hasta encontrar un lugar donde colocar la nueva reina sin que se mate con la anterior, si terminamos una fila pasamos a la siguiente.

Si al final no encontramos lugar para colocar otra de las fichas lo que hacemos es devolvernos y mover esa ficha un puesto adelante y asi sucesivamente hasta encontrar una solucion al problema.

Collection

Traducido al español como colección y es la representación de un conjunto de objetos todos del mismo tipo, conocido comos sus elementos, algunos estan ordenadas y otras no, al igual ahi colecciones que permiten elementos duplicados y otras no.
Cada elemento cuenta con un subindice unico que determina la posicion del mismo en la colección, las colecciones pueden tener solo una dimensión, las colecciones tambien se pueden pasar como parametros

Encoding

Su significado en español es codificar, es el proceso por el cual la información de una fuente es convertida en simbolos para ser comunicada, el proceso contrario es decoding.
Lo que hace es transformar un conjunto de caracteres Unicode en una secuencia de bytes.

Bibliografia

• Collection, consulta [4 de junio de 2010] ,http://download.oracle.com/docs/cd/B19306_01/appdev.102/b14261/collection_definition.htm
• Encoding, consulta [4 de junio de 2010], http://msdn.microsoft.com/es-es/library/system.text.asciiencoding%28v=VS.80%29.aspx
  

Algoritmo de ordenamientos recursivos

Bueno este fue un tema que quise dejar despues de la explicación de ordenamientos y de recursividad por que es una mezcla de los dos, es un algoritmo de ordenamiento recursivo.

Este tema se ve muy interesante, espero que en la practica sea de mucho agrado para todos ya que puede llegar a ser una gran fuente de ayuda.

El dia de hoy trataremos 2 de estos algoritmos:

• Quicsort
• Mergesort

Quicsort

Este algoritmo actualemente es el mas eficiente y veloz, su funcionamiento es de la siguiente manera:

• tomamos un valor 'a' del arreglo.
• buscamos la posición correcta del dato de tal forma que todos los que se encuentran a su izquierda seas menores o iguales que el y los de la derecha sean mayores o iguales a el.
• nos damos cuenta que el valor 'a' ya se encuentra en la posición correcta, el problema si divide en dos (se basa en la tecnica de divide y venceras, muy utilizado en programación orientado a objetos), al final reunimos los resultados en un vector.
  
• y repetimos el procedimiento inicial (usamos recursividad)
• el proceso finaliza cuando cada dato encuentra su posición correcta.

Este metodo recibe un vector de enteros, el dato en la posición inicial y el ultimo dato valido del array(n-1). la elelección del pivote se puede decir que la promedio ya se suba el dato inicial mas dato final entre dos, es una manera de asegurarse que sea el valor medio.
Hasta que i sea menor que el ultimo valor que es j, se realizaran los while que hacen referencia a:

• Mientras que el valor que se encuentre en la posición sea menor al que escogimos de pivote, se sumara a la posición mientras encontremos un valor igual o mayor al que se encuentre en el pivote.
• En este caso es muy parecido solo con la diferencia que el valor que se encuentre en la posición es mayor mientras encontremos un valor que sea igual o menos al del pivote.

Dentro del if se hace el intercambio de valores dependiendo la situación, por ultimo en los dos if finales el metodo se vuelve recursivo pero en un lado actualiza el valor maximo, mientras que en el otro if se actualiza el valor inicial.

Mergesort

Es un algoritmo de ordenación tambien denominado ordenamiento por mezcla, se basa en la tecnica de divide y venceras; funciona de la siguiente manera:

• Si el largo de un array es de 0 ó 1, entonces ya está ordenado.
• Dividir el array desordenado en dos subarrays de aproximadamente la mitad del tamaño.
• Ordenamos cada subarray recursivamente aplicando el ordenamiento por mezcla.
• Mezclamos los dos subarrays en una solo array ordenado.
  

El algoritmo mergesort incorpora una idea principal para mejorar su tiempo de ejecución:

Siempre es mejor pequeños problemas que uno grande, es bueno aplicar la tecnica de divide y venceras. ya que es mas facil enlazar dos arrays previamente ordenados que desordenados.

Bibliografia

• Ordenamiento por mezcla, consultado [18 de abril 2010], http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla
• Quicsort, consultado [17 de abril 2010], http://es.wikipedia.org/wiki/Quicksort
• Quicsort, consultado [17 de abril 2010], http://www.angelfire.com/wy2/est_info/quicksort.html
• Mergesort implementation in Java, consultado [18 de abril 2010], http://www.java-tips.org/java-se-tips/java.lang/merge-sort-implementation-in-java.html
  

Recursividad

Hasta ahora todas las clases que hemos tenido son geniales, aprendimos cosas interesantes en cada una y el ingeniero le pone mucho entusiasmo al enseñarnos, la verdad es que hemos asimilado mucho en esa clase. Pero definitivamente de todas esta fue la que mas me gusto.

Es una función que se llama a si misma, pero esta función no es necesaria utilizarla en todos los algoritmos, puede simplemente hacer que el consumo de recursos sea mayor que el algoritmo normal, puede llegar a ser eficiente o no. Ademas puede llegar a crear una función que no llegue a retornar un valor definitivo, este tipo de recursividad hace que se cree un bucle infinito.

A continuación un ejemplo de recursividad fue el primer ejercicio sobre el tema:

Recibimos un número entero, como sabemos tanto el factorial de 0 y 1 es igual a 1, por eso la condición. El factorial de un número es igual al factorial de el número anterior a el por el número base.

n!= (n-1)!*n

Ejemplo: 6!= 5!*6

Explicación grafica del algoritmo recursivo de un factorial

Bibliografia

• Programación en Java, consultado [17 de abril 2010], http://elvex.ugr.es/decsai/java/

• Algoritmo recursivo, consultado [17 de abril 2010], http://es.wikipedia.org/wiki/Algoritmo_recursivo

• Recursividad, consultado [17 de abril 2010], http://www.freenetpages.co.uk/hp/alan.gauld/spanish/tutrecur.htm

Algoritmos de ordenamiento

Algoritmo burbuja

Es un sencillo algoritmo de ordenamiento, este algoritmo compara cada uno de los elementos del array, lo compara con el siguiente y si el orden esta equivocado lo cambia y asi sucesivamente hasta que el array no necesite mas intercambios se dice que esta arreglado.

Algoritmo de Inserción

Es un metodo de ordenación, este toma cada dato del arreglo y lo compara con los que se encuentran en posiciones anteriores. Si resulta que el dato con el que se esta comparando es mayor que el dato base, se corre hacia la siguiente posición. Si por el contrario, resulta que el dato con el que se esta comparando es menor, se detiene el proceso de comparación ya que se encontró que esta ordenado y se coloca en su posición.
Es un algoritmo lento, pero puede ser de utilidad para listas semiordenada, pues en ese caso se realizan pocos desplazamientos.

Algoritmo de shell

Es un algoritmo de ordenamiento, se dice que es la generalización del metodo de inserción ya que el metodo de inserción es eficiente si el arreglo esta semiordenado, pero tambien ineficiente porque mueve un dato cada vez.




Este algoritmo es un simple ordenamiento por inserción, solo que este garantiza que los datos del vector estaran casi ordenados, ya que compara elementos separados por espacios de varias posiciones, esto que permite que sea mas rapido hacia la posición adecuada.

Bibliografia

• Ordenamiento shell, consultado [17 de abril 2010], modificado [22 de marzo 2010], http://es.wikipedia.org/wiki/Ordenamiento_Shell

• Ordenamiento por inserción, consultado [17 de abril 2010], modificado [16 de abril 2010], http://es.wikipedia.org/wiki/Ordenamiento_por_inserci%C3%B3n

• Algoritmos de Ordenamiento, consultado [17 de abril 2010], http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf

• Ordenación por el metodo de burbuja, consultado [17 de abril 2010], http://www.estructuradedatos.galeon.com/burbujatext.htm

• Algoritmos de ordenamiento, consultado [17 de abril 2010], http://www.monografias.com/trabajos/algordenam/algordenam.shtml

Ordenamientos

Entramos ahora en un tema un poco complejo para algunos pero de mucha ayuda en la solución de problemas complejos.

Empezemos con la pregunta basica.

¿Que es un ordenamiento?

Es la acción de arreglar los datos de un array en un orden secuencial de acuerdo a un criterio. El ordenamiento se lleva a cabo teniendo en cuenta algún campo en los datos y se hace con el fin de permitir una búsqueda fácil de datos.

El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético, de una manera ascendente o descendente.

Ejemplo:

¿Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Existen diferentes algoritmos de ordenamiento entre los que encontramos:

• Burbuja
• Shell
• Inserción
• Quicsort
• Mergesort

Bibliografia

• Algoritmo de ordenamiento, consulta [17 de abril 2010], modificada [15 de abril 2010], http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

• Algoritmos de ordenamiento, consulta [17 de abril 2010], http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf

Arrays

Retomamos el tema visto de forma teorica hace mucho tiempo en una clase de algoritmica II, en aquella ocasión donde los problemas eran mas dificiles, estabamos empezando a conocer todo lo referente al mundo de los algoritmos y la programación. Espero que en la parte practica se nos haga mas divertido el aprendizaje y que asimilemos todo lo referente al tema para un futuro, tengo mucha expectativa en esta clase, ya que en cierto tiempo muchos no fuimos muy buenos en el tema. Pero yo se que cada dia todos pondremos de nuestra parte para que la clase sea la mas agradable y entendible.

Bueno ya entrando un poco en el tema, un Array es una estructura de datos que nos permite almacenar variables de un mismo tipo, nos permite tener un manejo mas organizado ya que la variable tiene una distinción numérica, el 0 es el índice del primer elemento mientras que n-1 es el del ultimo.

Los arrays pueden ser de cualquier tipo de dato incluyendo objetos, ya que a su vez, ese tipo de dato es un objeto, las variables de tipo arrays se declaran utilizando [].
Existen dos tipos de arrays:

• Unidimensional (vectores)
• Multidimensional (matrices)

En programación los arrays deben declararse, crearse, inicializarse para que podamos usarlos y realizar operaciones con ellos.

Unidimensional (vectores)

tipo_dato[] nombre_array; //declarar

nombre_array= new tipo_dato[tamaño];
// crear (asi reservamos un espacio en la memoria para los datos)

nombre_array[numero_elemento]= valor;
//inicialización(tambien se puede hacer por medio de un for)

for (int i=0; i<(numero_elemento); i++)
{
nombre_array[i]=s.nexttipo_dato();

}

variable= nombre_array[numero_elemento] //asignación

veamos un ejemplo:

int [] vector;
vector = new int [4];
vector[2]=3;
k= vector [2];

un arreglo llamando vector, tiene cuatro elementos de tipo entero, y a k le asignamos el valor del tercer elemento.

Multidimensional (matrices)

tipo_dato[][] nombre_array; //declarar

nombre_array= new tipo_dato[tamaño][tamaño];
// crear (asi reservamos un espacio en la memoria para los datos)

nombre_array[numero_elemento][numero_elemento1]= valor;
//inicialización (tambien se puede hacer por medio de un for)
el valor del numero_elemento1 es opcional solo cuando toda la matriz tiene el mismo tamaño, tenemos el ejemplo cuando es cuadrada, en caso contrario se deja vacio el espacio.

variable= nombre_array[numero_elemento][numero elemento1] //asignación

veamos un ejemplo:

double[][] matrizUnidad;

matrizUnidad= new double [4][4];
for (int i=0; i<4;i++)
{
for (int j=0; j<4;j++)
{

if (i==j)
matrizUnidad[i][j]=1.0;
else
matrizUnidad[i][j]=0.0;

}
}


ejemplo tomado de: http://www.sc.ehu.es/sbweb/fisica/cursoJava/fundamentos/clases1/arays.htm



int[][] matriz;
matriz= new int [4][ ];
matriz[2][0]=3;
k= matriz [2][0];





Bibliografia

• Los arrays, consultado[4 abril 2010]; http://www.sc.ehu.es/sbweb/fisica/cursoJava/fundamentos/clases1/arays.htm

• Arrays en Java, consultado [2 de abril de 2010]; http://www.webtaller.com/construccion/lenguajes/java/lecciones/arrays_java.php

• Arrays en Java, consultado [2 de abril de 2010]; http://www.dtic.upf.edu/~vlopez/docencia/castellano/todoshtml/PIIt2cas/node4.html

• Class arrays, consultado [4 de abril 2010]; http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html