3.2- Colas:

Es una estructura de Datos lineal donde las eliminaciones de elementos se realizan por uno de sus extremos denominado FRONT y las inserciones de elementos se realizan por el otro extremo denominado final o Rear.

Las colas son estructuras de datos FIFO(first-in, first-out) porque el primer dato que se inserto sera el primero que saldra de la Cola.

=Operaciones en Una Cola=

1.PUSH.- Es el metodo por el cual se va a agregar un nuevo dato a la cola, tomando en cuenta la capacidad maxima de
almacenar en la estructura y las posiciones del frente y final en la cola.

Algoritmo:

Push(Cola,Frente,Final,Max,Elemento)

si Frente=0 y Final =Max-1 entonces

Imprimir "La Cola Esta Llena", y Salir

si no si Frente =Nulo(-1)  entonces

Frente=0

Final=0

si no

Final=Final+1

Cola[Final]=Elemento

Salir

NOTA:INICIALIZAR AL PRINCIPIO DEL PROGRAMA
*TAMAÑO DE LA COLA
*FRONT=-1
*REAR=-1


2.POP.- Es el Método por el cual se va a sacar el primer dato de la cola tomando en cuenta solo la posicion del frente.

Algoritmo:

Pop(Cola,Frente,Final,Maximo)

si Frente!=-1 entonces

Imprimir "Eliminando Dato", Cola[Frente]

Cola[Frente]=0

Si Frente=Final

Cola[Frente]=0

Final=-1

si no 

Frente=Frente+1

si no

Imprimir "La Cola Esta Vacía"

Salir

3.-Recorrido: Es el Método en el cual se despliega el contenido de la cola, si no hay ni un elemento en ella desplegara el 

mensaje "La Cola Esta Vacía"

Algorítmo:

Recorrido(cola,frente,final,max)

si frente !=-1 entonces

apuntador=frente

repetir mientras apuntador <=final

imprimir "elemento",cola[apuntador],"posicion",apuntador

apuntador=apuntador+1

fin del ciclo

si no

imprimir "La Cola Esta Vacía"

Salir.

4.-Busqueda: Esta metodo utiliza el recorrido para encontrar el elemento deseado y desplegar un mensaje con la posicion 

donde se encuentra siempre y cuando la busqueda sea exitosa si no desplegara el mensaje de que no encontro el elemento. En 

el caso de que no existan elementos en la cola desplegara "La Cola Esta Vacía".

Algrítmo:

Búsqueda(cola,frente,final,max)

si frente!=-1 entonces

apuntador=Frente

repetir mientras apuntador<=final

si elemento=cola[apuntador] entonces

imprimir "dato encontrado",elemento,"posicion",apuntador

y salir

si no

apuntador=apuntador+1

fin del ciclo

imprimir "dato:",elemento,"no esta en la cola"

si no

imprimir "La Cola Esta Vacía"

Salir

Unidad III.- Estructuras Lineales y Dinámicas

3.1- Pilas

*Pila.- Es un conjunto ordenado de elementos en el cual se pueden agregar y eliminar datos por uno de sus extremos

llamado tope de la pila(top). "Siempre empieza con valor -1 (marca el estado vacío de cualquier estructura)". La pila es una estructura de datos LIFO porque el ultimo datos que se inserta es el primero que se elimina (Last in-first out).

=OPERACIONES EN UNA PILA=

1.-Push-> Es el método a traves del cual se va a agregar un dato nuevo a la pila tomando en cuenta la capacidad máxima de almacenar en la estructura.

Algorítmo:

Push(Pila,Top,Max,Elemento)

Si Top !=Max-1 entonces

Top<-Top+1

Pila[Top],_Elemento

Si no

Imprimir "La Pila Esta Llena"

Salir.

2.-Pop-> (Eliminar) Es el método con el cual se va a eliminar el ultimo dato de la pila basandose en la posicion de Top.

Si no esxisten elementos en la pila, desplegara el mensage "La Pila Esta Vacía".

Algorítmo:

Pop(Pila,Top)

Si Top !=Nulo(-1) entonces

Imprimir "Elemento:",Pila[Top],"Será Eliminado"

Pila[Top]<-0

Top,_Top-1

Si no

Imprimir "La Pila Esta Vacía"

Salir.

(Programa 15)

Menu Operaciones en una Pila

1 Insertar Datos en la Pila

2 Eliminar Datos en la Pila

3 Desplegar Datos en la Pila

4 Buscar Datos en la Pila

5 Fin del Programa

Instrucciones:

1.-Inicializar Top=-1

2.-Pedir el Tamaño Máximo de la Pila y enviarlo al constructor para establecer el tamaño máximo de la pila.

3.-Pedir desde el Menu de dato a insertar y enviar como parámetro al método PUSH.

4.-Hacer 2 Programas: Uno que maneje datos de tipo double (número) y otro que maneje datos de tipo string (nombres)

3. Recorrido: 
Es el método a través del cual se hace un recorrido a la pila para desplegar los elementos a partir
de la posicion del tope de la pila y se repite hasta que la variable auxiliar sea igual a nulo(-1).

Algorítmo:
Recorrido (Pila, Top)
si Top!=Nulo(-1) entonces
Apuntador=Top
Repetir mientras apuntador !=Nulo
Imprimir "Elemeno",Pila[Apuntador],"Posicion:",Apuntador
Apuntador=Apuntador-1
Fin del ciclo
si no
Imprimir "La pila esta Vacía"
Salir

4. Busqueda:
Es el método que se utiliza para localizar un elemento en particular en la pila. si esta resulta exitosa desplegara el elemento y la posicion en la que se encuentra, si no desplegara el mensaje de que el elemento no fue encontrado.

Algorítmo:
Busqueda (Pila,Top,Elemento)
si Top!=Nulo(-1)
Apuntador=Top
Repetir mientras Apuntador!=Nulo
Si Pila[Apuntador]=Elemento entonces
Imprimir "El dato",Elemento,"fue encontrado en la posicion",Apuntador
Salir (RETURN)
Si no 
Apuntador=Apuntador-1
Fin del ciclo
Imprimir "El dato",Elemento,"no esta en la Pila"
si no
Imprimir "La pila esta Vacía"
Salir

2.1.2- Manejo de Memoria Dinámica

*Memoria Dinámica:
Las reservas de mamoria dinámica se hacen tiempo de ejecucion despues de leer los datos y de conocer el tamaño eacto del problema a resolver, como consecuancia se adapta mejor a las necesidades de cada caso pero en contrapartida es un poco mas dificil de programar.
Tanto la creación como destruccion de los objetos està en manos del programador a traves de los operadores "new" y "delette", el sitio donde se almacenan los objetos, suelen llamarse heap ò free store, traducido como montículo o memoria libre.
En c# no es necesario considerar la liberaciòn de la memoria dinamica puesto que FrameWork se encarga de liberar todas las referencias que no se esten utilizando y compactar la memoria para mejorar el rendimiento.

En C# todas las clases son tratadas sintacticamente como referencias y no permite elegir como reservar memoria para una instancia en particular, en cambio obliga a que un int sea un tipo valor.

class Program
{
void imprime_binario(int n)
{
if (n>=2)
{
imprime_binario(n/2);
Console.Write("{0}",n%2);
}
else
Console.Write("{0}",n);
}
static void Main (string []args)
{
Console.Write("Alimenta un Número Entero: ");
int numero=Int32.Parse(Console.ReadLine());
Program p=new Program();
Console.Write("\n\tNumero Entero {0} en Código Binario: ", numero); p.imprime_binario(numero);
Console.Write("\n\n\t\tDesea hacer otra Operación S/N: ");
op = char.Parse(Console.ReadLine());
}
while (op == 's' || op == 'S');
}
}

Unidad II.- Manejo de Memoria

Toma arreglos y objetos en general, tiene una duracion determinada en el transcurso de un programa y son creados y destruidos, para su uso despues para que la memoria sea liberada, para que la utilicen otros objetos.

En C# existen 3 formas de usar la memoria para almacenar valores son:
a) Memoria Estatica
Es la utilizada por variables globales y las declaradas de tipo static. Estos objetos tienen asignada la misma direccion de memoria desde el comienzo hasta el final del programa.

b) Memoria Automatica
Es la utilizada por argumentos en una funcion y por las variables locales. Cada entrada en la funcion crea estos objetos y son destruidos al salir de ella.

c) Memoria dinamica
Es tambien llamado almacenamiento libre porque en estos casos el programador es el que solicita memoria para crear los objetos y es el responsable de liberar la memoria cuando ya no la necesita para
ser reutilizada.

La reserva y liberacion para variables globales, estaticas, locales y argumentos son realizadas en forma implicita por el programa, la unica que requiere intervencion del programador es la reserva y liberacion de memoria dinamica.

2.1.1.- Manejo de Memoria Estática

La memoria estatica es la que se reserva en el momento de la compilacion ates de comenzar a ejecutarse el programa. Los objetos son creados en ese momento y destruidos al finalizar el programa. Mantienen la mismalocalizacion en memoria durante todo el transcurso del programa.

Los objetos administrados de este modo son:

• Varialbes Estáticas
  
• Varialbes Globales
  
• Miembros státic de clases
  
• Literales de cualquier tipo
  

Ejemplo1:

class CSimple1 //(PROGRAMA 13)

{

static void Main(string[]args)

{

int []Numeros=new int[]{1,2,3,4,5};

for (int i=0;i<5;i++)

console.Write("{0}",Numeros[i]);

}

}

Ejemplo2:

class CSimple2

{

static int Funcion(int p, int q)

{

return(p+q);

}

static void Main (string[]args)

{

int Resultado=Funcion(7,2);

Console.WriteLine(Resultado);

}

}

En el ejemplo 1 se muestra la declaracion estatica de un arreglo y la declaracion de la variable global de control dentro del for.

En el ejemplo 2 se muestra la declaracion estatica en una funcion la cual es ejecutada al enviarle 2 parametros que son literales numericas.

En resumen el inconveniente de utilizar memoria estatica aunque es mas facil de programar es que la cantidad de memoria se reserva siempre antes de conocer los datos completos del problema lo que aveces lleva a reservar un maximo de memoria que en la mayoria de las veces no se va a necesitar.

1.4- Selección de un Algoritmo

Cuando se resuelve un problema y hay la necesidad de elegir entre varios algoritmos que nos puedan dar un resultado existen 2 objetivos que suelen contradecirse para elegir uno:
a) Que el algoritmo sea fácil de entender, codificar y depurar.

b) Que el algoritmo use eficientemente los recursos de la computadora y se ejecute con la mayor rapidez posible.

El primer punto (a) se debe elegir cuando se escribe un programa que se va a utilizar una o pocas veces ya que el costo del tiempo de programación no será tan relevante ya que solo se utilizara en pocas ocasiones.
El punto b es más importante cuando se presenta un problema cuya solución se va a utilizar muchas veces ya que el costo de ejecución del programa minimizara al costo de escritura.

En conclusión: Siempre será más ventajoso del punto de vista económico realizar un algoritmo complejo siempre y cuando el tiempo de ejecución del programa resulte significativamente menor.

1.3.2.- Complejidad en el Espacio

Complejidad espacial.- Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
Ej. Algoritmo de búsqueda en árboles.

Función búsqueda_arboles(problema)
devuelve solución/fallo
inicializa árbol de búsqueda con estado inicial
ciclo hacer
si no hay cantidades para expandir
entonces devolver “fallo”
en otro caso escoge r nodo para expandir
si el nodo es el objetivo
entonces devolver solución
en otro caso expandir nodo

=Resultados Obtenidos=


NOTAS: factor de ramificación --> 10 nodos sucesores p/cada uno como máximo profundidad del árbol

1.4.- Selección de un Algoritmo
Tarea: Como seleccionar un buen Algoritmo?

1.3 Complejidad

1.3.1 Tiempo de Ejecucion de un Algoritmo.
Como se mide el tiempo de ejecucion de un programa en funcion de N (numero de datos)?
Esta funcion se puede medir fisicamente calculandolo con un reloj o se puede calcular sobre el codigo, contando las instrucciones a ejecutar y multiplicandolo por el tiempo requerido por cada instruccion.

Ejemplo:
Sentencia 1

. Sentencia 2
. entonces
. . T(N)=t1+t2*N
En este ejemplo, siendo t1 el tiempo que lleve ejecutar la sentencia S1 y t2 el tiempo que lleve ejecutar la sentencia S2 un numero de n veces dentro del ciclo "for".

=Reglas Prácticas para calcular la complejidad de un algoritmo=
1.- Sentencia Sencilla: Se refiere a las sentencias de asignación, entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño está relacionado con N(número de datos). Como requiere un tiempo constante de ejecución su complejidad es el orden O(1)
2.-Secuencia de Sentencias: Su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias que se trate tomándose en cuenta el orden mas alto.
3.-Sentencia de Decisión (if): La condición suele ser de orden constante, osea O(1), sumando en la peor rama posible ya sea la del THEN o la de ELSE.
4.-Bucles (Ciclos): en los ciclos con contador explicito existen 2 casos y el tamaño N forme parte de los límites del ciclo o no.
4a) Contador Explicito
Caso 1 For (int i=0;;i++)
{S1;}
Entonces K*O(1)=O(1) Constante
Caso 2 For (int i=0;;i++)
{S1;}
Entonces N*O(1)=O(n) Lineal

4b) Evolución de Variable de Control No Lineal (WHILE): En los ciclos multiplicativos como el WHILE y el DO WHILE el incremento o decremento de la variable de control no es lineal lo que hace incrementar el orden de complejidad como en los ejemplos siguientes:
Ej. c=1;//Incremento
While (c1)
{
S1;
c=c/a
}
Complejidad Logarítmica O(log n)

5.- Llamadas a Procedimientos: La complejidad de llamar a un procedimiento esta dada por la complejidad del contenido del procedimiento en si, es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el cuerpo del procedimiento. En conclusión la complejidad de un procedimiento tiende a complicarse si se trata de procedimientos recursivos.
NOTA: Procedimiento Recursivo: el que se manda llamar a si mismo un a y otra ves.
Ej. Función Factorial (no recursiva) Programa 9
Int factorial (int n) //sentencia entrada O(1)
{
Int fact=1; //sentencia asignación O(1)
For (int i=n;i>0;i--) //ciclo contador explicito O(n)
Fact=fact*I; //sentencia asignacion O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de iteraciones igual a n

ORDENES DE COMPLEJIDAD
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logaritmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(k^n) Exponencial Intratables
O(n!) Factorial Intratables

Notación Asintótica "Omega" Grande

Fórmula.-
Una funcion g(n) pertenece a O{f(n)} si y solo si existen las variables tales que g(n)<=f(n)
*La funció Omega Grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de una función f(n) cuando esta en función de n se usa la notación que se lee: T(n) es omega "símbolo" (g(n)) y significa que existe una constante c tal que t(n)>=c(g(n)) para un número infinito de valores de n.

Ejemplo 1: Programa 6
Verificar la función
Ejemplo 2: Programa 7
Verificar la función
Ejemplo 3: Programa 8
Verificar la función

1.1 Concepto de Complejidad de Algorítmos

TEORIA DE LA COMPLEJIDAD COMPUTACIONAL.- Es la parte de la teoría de la omputación que estudia los recursos necesarios durante el cálculo para resolver un problema.

=Clases de Complejidad=
Los problemas de decisión (aquellos donde la respuesta posible es "si" o "no") se clasifican en conjuntos de complejidad comparable que son llamados clases de complejidad.

a)Clase de complejidad P: Es el conjunto de los problemas de decision que pueden ser resultos en timepo polinomico por una maquina de turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplos:
*Camino Optimo de un cartero
*Saber si un numero entero es primo. Programa 1
*Decidir si una grace pertenece a un conjunto dado de fraces.

a)Clase de complejidad NP: Es el conjunto de los problemas de decision que pueden ser resueltos por una maquina de Turing no determinista en tiempo polinomico. Los problemas de esta clase tienen la propiedad de que su solución puede ser cerificada
Ejemplos:
*El problema del Agente Viajero. Programa 2
*El problema de Satisfactibliidad Boolenana.
a)Clase de complejidad NP: Es el subconjunto de los problemas de decision NP que se destacan por su complejidad en la cual algunos de ellos en la actualidad no han encontrado una solucion satisfactoria.
Ejemplos:
*La suma de subconjuntos dado un "S" de enteros, Existe un conjunto no vacío cuyos elementos sumen 0?
*2 grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando sus vértices?

=Diagrama de la Relación entre las clases de Complejidad=
Problemas de Decisión:

Pregunta: Las clases P y NP son diferentes o No?

El Clay Matematics Institute ofrece $1,000,000 de dlls a quien sea capaz de responder satisfactoriamente a esta pregunta.

1.2 Arítmetica de la notación O

Notación Asintótica O:
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función.
la utilidad de aplicar esta notación a un algoritmo es encontrar el límite superior del tiempo de ejecucion, es decir el peor caso.

Definición: lg(n)|<=|c.f(n)1 para todo n>=n
Esto significa que la función g(n) pertenece o es válida para f(n) si y solo si existen las constantes c y n=0, tales que para n>=, T(n)>=cn. El órden de magnitud de la función sera el órden de términos de la función mas grande respecto de n. Supóngase que:
ejemplo 1:

Realizar operación en un programa ejecutable (consola o visual):
Programa 3:
Programa 4:
Programa 5:
TAREA:
Notación Asintótica Omega Grande:
-Función?
-Fórmula?
-Ejemplos?

Temario y Forma de Evaluación

Materia: Estructura de datos
Serie: 3W2A
Maestra: M.C. Luz Elena Cortez Galván

Temario:
Unidad 1.- Análisis de Algorítmos
Unidad 2.- Manejo de Memoria
Unidad 3.- Estructuras Lineales Estáticas y Dinámicas (Pilas, Colas, Listas)
Unidad 4.- Recursividad
Unidad 5.- Estructuras No Lineales Estáticas y Dinámicas (Arboles)
Unidad 6.- Ordenación Interna (Burbuja, Shell, Quicksort, Radix)
Unidad 7.- Ordenación Externa (Intercalación simple, Cuadrática, Merge)
Unidad 8.- Métodos de Busqueda (Secuencia, Binaria, Hash)

Evaluación:
-80% Examen (Teórico/Práctico)
-15% Programas
-5% Asistencia/Participación
---
100%

Bibliografía:
*Libre: cualquier libro de c# con temas de estructuras de datos, algoritmos de ordenamiento y de busqueda.
También se pueden consultar en línea (Internet) por tema de aplicación.


Tarea:

-Investigar las 3 Clases de complejidad (P, NP, NP-Complejo)
Programas de ejemplo.