Mapa mental pilas y colas

Read More

Cola circular, bicolas y recursividad

Cola circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. son un poco mas claras que las colas normales ya que esta permite que los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida y de esta forma se haría mas fácil la eliminación y la adición de un dato. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

En esta, las instrucciones son diferentes, ejemplo: cuando esta llena: (frente==0 &&fin==max-1)

Bicolas:

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola. Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera:



Recursividad:

Propiedad de las funciones (metodos) de auto llamarse, son una alternativa de los procesos iterativos. "Todo lo que se haga iterativamente tambien puede hacerse recursivamente"

"Todo lo que se haga con: "For- while- do while" son procesos iterativos"
La recursividad es util cuando el proceso iterativo es muy complejo.
-Recorrido de estructuras no lineales, solucion de formulas matematicas complejas-
- Recursividad vs Iteracion: Primero que todo, la recursividad se aplica en metodos, la iteracion se aplica con for, while, do-while.
-La recursividad tiene reduccion de codigo, la logica es simple, mientras que la iteracion no reduce el codigo.

Aunque si usted no ha comprendido bien la recursividad, la logica no le parecera simple, con respecto a la iteracion, la solucion (logica) depende del problema, y esta puede que sea muy compleja.
Aparentemente, la recursividad es mejor que las iteraciones, asi como ellas, esta tambien tiene us desventajas, como lo es el consumo considerable de memoria, ya que por cada autollamado se hace una copia de la funcion, que es guardada por el sistema operativo en una pila( llamado a subprogramas), Los procesos iterativos tienen un bajo nivel de consumo de memoria, por eso no se han desaparecido, ni creo que desapareceran, tienen un bajo nivel de consumo y son eficientes en sus procesos pequeños, ya que si toca, por ejemplo, imprimir 10 numeros con un "for", el solamente realiza 10 vueltas y los imprime, en cambio si usamos recursividad para imprimir los mismos 10 numeros, los imprimiria, pero esta duplicaria hasta 10 veces la cantidad de memoria por funciones.

Implementacion:
Igual que toda funcion, tiene una parte de acceso, para tener un modificador, puede tener un tipo, una clase, un nombre, y unos parametros( igual tiene sus variables, puede tener variables locales), expresado de la siguiente forma.

Acceso modificador/ clase nombre(parametros){
           //Variables locales
              //if(Condicion de parada){
                     Instrucciones
            }
 Instrucciones                              ---- Autollamado, Nombre(parametros actuales)




Consiste en, colocar el nombre del metodo con parametros actuales, es decir el mismo nombre del metodo se simula como un auto llamado, ella misma dentro de sus instrucciones se llama
-Los libros colocan como ejemplo los factoriales, aunque no creo que sea conveniente usar un proceso recursivo siendo este un proceso iterativo, pero bueno, recursivamente seria asi:

Si sabemos que n! = n*(n-1)!
entonces tenemos que:
5!=5*4!/24=120
4!=4*3!/6=24
3!=3*2!/2=6
2!=2*1!/1=2
1!=1*0!/1=1
0!=1
Vemos que "n" va disminuyendo entonces estoy seguro que (n==0) retorna un 1, pero si no  otra cosa, en codigo seria asi n*factorial (n-1)

public static long factorial(int n){
if(n==0){
return 1;
}else{
return n*factorial(n-1);
}
}
Cuando llegue hasta 0, una funcion iterativa normalmente no tiene funciones iterativas, solo tiene instrucciones condicionales que haran que en algun momento pare.

Read More

Quiz 2

Este fue el segundo quiz realizado

las respuestas son las siguientes:

Perfecto! :)

Expresion aritmetica:        (a+b)*c^1/2

                   -------        ab+*c^1/2

                   ------         ab+*c1^/2

                   ------         ab+c1^*/2

Respuesta:       -----    ab+c1^*2/

Read More

Colas

"¿Por que estas bloqueado?  - Por que tienes un solo cerebro y mientras estas pensando en muchas cosas dejaste la pregunta que te hice al final, es decir, en una COLA"


Definicion:  Es una regla que se aplica a una estructura lineal (arreglos y listas enlazadas) para que tengan un comportamieno FIFO( First in- First out) Primero en entrar - primero en salir, es decir primer elemento en almacenarse, primero en procesarse.

Una cola puede almacenar lo que nosotros queramos, números, personas, documentos, cualquier cosa. Esta estructura de datos tiene muchas aplicaciones en la informática al igual que la pila, por ejemplo cuando mandan a imprimir varios documentos a una impresora (Ejemplo puesto por el mismo profesor Juan Jose Puello), manda uno en word, manda otro en excel, manda otro en power point, para esto, existe una cola de impresión que sigue la filosofía, se imprimen los primeros documentos y si quiero imprimir un nuevo documento se adiciona al final de todos los documentos que están esperando a imprimirse.

Una vez comprendido en concepto ahora veamos como se implementa esto en un lenguaje de programación, por ahora lo implementaremos en Java. Java en sus librerías ya tiene la forma de implementar Colas (queue), nosotros ahora haremos como si no existiera, es decir crearemos nuestra versión, que es lo que generalmente se hace cuando se aprende colas en la universidad. Pues bien existen dos formas de implementar para que la cola sea o bien estática (reservamos un espacio fijo en memoria) o bien dinámica (el tamaño en memoria va creciendo según se requiere), se implementa con vectores o con listas enlazadas respectivamente. Nosotros implementaremos haciendo de un array bidimensional es decir de modo estático y al decir estático estamos diciendo que tendrá un limite para almacenar datos en la cola.

Para manipular elementos en el vector de la cola son necesarias variables que me digan en donde empiezan los elementos y otra en donde terminan, como tal vez estés pensando ¿porque no solo una? (una que me diga en donde termina asumiendo que siempre se empieza desde la posición 0 del vector), pues se puede implementar con solo una de estas variables pero presenta muchas desventajas pues si eliminamos un elemento de nuestra cola, (el primero justamente) tendríamos que recorrer todos los siguientes elementos una posición adelante y esta manera seria muy lenta de implementar pues que pasa si son 1000 elementos, eso es mucho tiempo perdido, entonces es por eso que usamos dos variables que me digan donde empieza y donde terminan los elementos de la cola, dos variables enteras que llamaremos inicio y fin, estas variables funcionan de la siguiente manera:

Colocar por un extremo, quitar por el otro

Por donde entra se colocaria la variable (Inicio) y por donde sale la variable( Fin), ahora, si consideramos que nuestro vector tiene 5 posiciones y deseamos ingresar un dato o, algo, primero debemos comprobar si esta llena la pila, o si esta vacia, ¿como lo hacemos? creando un metodo PUBLICO llamado "vacia" y otro llamado "llena", de la siguiente manera.

public boolean vacia() {retorna verdadero si la cola esta vacía es decir no tiene ningún elemento, para esto solo se pregunta si inicio es igual a fin.

public boolean llena(){ retorna verdad si es que la cola esta llena, pasa cuando se ha llenado todo el vector, la cantidad de elemento que permite la cola lo determina la variable Max.

poner() {adiciona un nuevo elemento a la cola, para esto solo se incrementa la variable fin y se coloca el elemento en esa posición.

quitar(){ extrae el primer elemento de la cola, para esto se retorna la posición inicio + 1 del vector y se incrementa inicio en 1.

Con todos estos métodos básicos se puede realizar cualquier operación que necesitemos

UTILIDAD: SIEMPRE QUE LOS RECURSOS DE PROCESAMIENTO SEAN MENORES A LAS DEMANDAS DE SU USO.

APLICACIONES: COLA DE PROCESOS, COLA DE IMPRESIÓN, SIMULACION

OPERACIONES: PONER Y QUITAR.

IMPLEMENTACION: VECTORES, LISTAS ENLAZADAS

coloquemos como ejemplo una variable que trabaje como un semáforo y los procesos como los carros. Los procesos pueden ser cooperativos o independientes. Dos o más procesos pueden cooperar mediante señales de forma que uno obliga a detenerse a los otros hasta que reciban una señal para continuar.
Se usa una variable de tipo semáforo, es decir,  para sincronizar los procesos.
Si un proceso está esperando una señal, se suspende hasta que la señal se envíe.
Se mantiene una cola de procesos en espera en el semáforo.
La forma de elegir los procesos de la cola en espera es mediante una política first in first out.
Asi como los procesos que hacemos que realice el sistema operativo de nuestro pc. igual.

Read More

Expresiones Aritmeticas: Evaluar sin parentesis y orden de prioridades

En informática y lenguajes de programación, se entiende por expresión aritmética a aquella donde los operadores que intervienen en ella son numéricos, el resultado es un número y los operadores son aritméticos. Los operadores aritméticos más comúnmente utilizados son: + , - , * , / y %.

Operadores: Símbolo que indica al compilador que ejecute determinadas operaciones con los elementos sobre los que opera (aritméticos, lógicos, de cadena y de comparación).

Operandos: constantes, variables u otras expresiones.

infija: 1+2*3                :  Operadores en medio ( la unica que tendra parentesis)   : 7
prefija: +1*23              : Operadores antes (orden de prioridades)                       :
posfija: 123*+             : Operadores despues (orden de prioridades)                   : 7        
( El primero que sacamos va a la derecha y el segundo a la izquierda, entre el signo)

REGLAS:
1. La evaluación de las operadores con la misma prioridad se realiza de izquierda a derecha.
2.Se toman los dos primeros operadores, si son de igual jerarquía, se realiza el más a la izquierda.
3.Se toman los dos primeros operadores, si son de diferente jerarquía, se mira el tercer operador y se realiza el de mayor jerarquía que esté más a la izquierda.
4.Los paréntesis se resuelven completamente antes de realizar cualquier operación fuera de ellos, siguiendo las reglas dadas.
5. Los paréntesis más internos se resuelven primero, siguiendo las reglas dadas.

Read More