UNIDA TEMATICA 9:Representación y manipulación de estructuras lineales dinámicas

Colas

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.

Un ejemplo cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada.

Bibliografía: http://c.conclase.net/edd/?cap=003
                     http://es.wikipedia.org/wiki/Cola_%28inform%C3%A1tica%29

UNIDA TEMATICA 9:Representación y manipulación de estructuras lineales dinámicas

Pilas

Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído. Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir. El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.un ejemplo cotidiano es una pila de platos donde siemre se agarra el de arriva

Bibliografía: http://c.conclase.net/edd/?cap=003 http://es.wikipedia.org/wiki/Pila_%28inform%C3%A1tica%29

UNIDAD TEMATICA 9:Representación y manipulación de estructuras lineales dinámicas;

AQUI LES DEJO UNA EXPLICACION SOBRE LO IMPORTANTE DE LAS ESTRUCTURAS DINAMICAS DE DATOS: LAS PILAS Y COLAS

QUE SON LAS ESTRUCTURAS DINAMICAS??

Las estructuras dinámicas de datos son estructuras que cuya dimensión puede crecer o disminuir durante la ejecución del programa. Una estructura dinámica de datos es una colección de elementos llamados nodos. Al contrario que un array, que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa.

Las estructuras dinámicas de datos son de gran utilidad para almacenar datos del mundo real, que están cambiando constantemente. Por ejemplo si tenemos almacenados en un array los datos de los alumnos de un curso, los cuales estan ordenados de acuerdo al promedio, para insertar un nuevo alumno seria necesario correr cada elemento un espacio: Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del alumno se pueden insertar fácilmente.

Implementación de listas dinamicas

- son a base de puntero

- Hay que mantener un puntero al primer elemento

- Cada elemento contiene, en adición a su dato, un puntero a  su seguidor

-Al añadir un elemento, se modifica el puntero del elemento  después del cual se está insertando para que apunte al elemento nuevo

-Si hay elementos después del elemento insertado, primero hay que ajustar su puntero a enlazarse con su seguidor

 opciones en enlazado

-En ambas direcciones (enlazado doble)

- Conviene mantener un puntero al último elemento también

-Involucra más mantenimiento de punteros, pero ofrece accesos más rápidos al procesar la lista

- Ramificando para obtener estructuras no lineales

- Estos incluyen árboles, grafos y montículos

Bibliografía: http://c.conclase.net/edd/?cap=003

tipos de ordenamiento

Ordenamiento burbuja

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".

Ordenamiento por inserción

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Ordenamiento por mezcla

Este algoritmo consiste básicamente en dividir en partes iguales la lista de números y luego mezclarlos comparándolos, dejándolos ordenados.

Si se piensa en este algoritmo recursivamente, podemos imaginar que dividirá la lista hasta tener un elemento en cada lista, luego lo compara con el que está a su lado y según corresponda, lo sitúa donde corresponde.

Ordenamiento rápido

Sin duda, este algoritmo es uno de los más eficientes. Este método es el más rápido gracias a sus llamadas recursivas, basándose en la teoría de divide y vencerás.

Lo que hace este algoritmo es dividir recursivamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote (o comodín) que nos permitirá segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros elementos están ordenados.

 

 

Ordenamiento por selección

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1

    minimo = i;

    para j=i+1 hasta n

        si lista[j] < lista[minimo] entonces

            minimo = j /* (!) */

        fin si

    fin para

    intercambiar(lista[i], lista[minimo])

fin para

Arreglos

Arreglos:

Es una zona de almacenamiento continuo, que contiene una serie de elementos del mismo tipo.También puede definirse como una colección ordenada de elementos de un mismo tipo. Ordenada significa que cada elemento tiene una ubicación determinada dentro del arreglo y debemos conocerla para accederlo.

Algoritmos de búsqueda

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos.

Datos de entrada:

  vec: vector en el que se desea buscar el dato

  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

  dato: elemento que se quiere buscar.

Variables

  pos: posición actual en el arreglo

pos = 0

Mientras pos < tam:

 Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:

 pos = pos + 1

Fin (Mientras)

Devolver falso,

 Algoritmos de ordenamiento

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos servirán para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando el código, de cada algoritmo.

AQUI ESTA UN EJEMPLO DE UN PROGRAMA EN DEV C CON RECURSIVIDAD QUE EJECUTA LA SERIE DE FIBONACCI

#include<stdio.h>
int fibonacci(int n)
{
    if (n<2)
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2); //aqui se hase la llamada recursion
}
int main()
{
    int num=0,res=0;
    printf("NUMEROS DE FIBONACCI\n");
    printf("Introduce el numero de numeros: ");
    scanf("%i",&num);
    printf("\t");
    for(int i=0;i<=num-1;i++)
    {
        res = fibonacci(i);
        printf("%i  ", res);
    }
    printf("\n");
    return 0;
}
bibliografia:http://c.conclase.net/edd/

UNIDAD TEMATICA 7:RECURSION COMO HERRAMIENTA EN LA SOLUCION DE PROBLEMAS COMPUTACIONALES

AQUI ESTA UNA BREVE EXPLICACION SOBRE LA RECURSION, LA ITERACION, LA MODULACION

¿QUE ES LA MODULARIDAD?

Es común dividir los algoritmos en módulos, cada módulo lleva a cabo cierta funcionalidad.Muchas veces los módulos sirven para más de un algoritmo, se podría decir que se reutilizan. Estos se  publica bibliotecas de tales módulos, que Se llaman “librerías” y se conoce que el módulo más pequeño es una subrutina

LAS SUBRUTINAS

-Son métodos auxiliares

-Toman uno o varios parámetros de tipos predefinidos

-Ejecutan su propio código a base de los parámetros recibidos

-Al recibir punteros, pueden modificar variables de la parte del programa que llamó a la subrutina

-Producen dependiendo del programa un valor de salida

Ejemplos:

Usamos subrutinas de las bibliotecas estándares de ANSI-C para la siguientes funciones:

-Impresión en el terminal que es la biblioteca (stdio.h)

-Lectura de datos del teclado que es la biblioteca (stdio.h)

-Operaciones matemáticas en la biblioteca (math.h)

-Manipulación de cadenas de caracteres en la biblioteca(string.h)

ENCADENADOS

Se  podria decir que como un método principal que llama a otro submetodo y ese a otro submetodo a si infinitamente

Ejemplo:

-El método principal (main) puede llamar a subrutinas . Luego, esas subrutinas pueden llamar a otras subrutinas. Esas luego a otras, Etcétera y no hay un límite fijo de “profundidad”

de llamadas

FLUJO DE CONTROL

Típicamente solamente una (sub)rutina de un programa específico puede estar en ejecución a la vez y la ejecución simultánea de dos o más (sub)rutinas

requiere programación paralela y múltiples núcleos

y/o procesadores

Se dice que la (sub)rutina en ejecución “tiene control” de la computadora y al terminar su ejecución, una subrutina devuelve el control de la computadora a la rutina principal

EJEMPLO

Código en ANSI-C

#include <stdio.h> // biblioteca que incluye la rutina printf

#include “pidevalor.h” // subrutina externa “nuestra”

int computo(int v) {

return (v % 2);

}

int main(int c, char** s) { // rutina principal

int valor = pidevalor(5, 10); // llamada a subrutina

printf(“%d\n”, computo(valor)); // llamadas a otras dos

return 1; // salir del programa

}

ITERACION

A veces es necesario realizar alguna computación de

manera repetida como componente del algoritmo.Este código estará o adentro de un ciclo tal como es o se puede “vestir” como una subrutina

A veces que se llama una subrutina o la ejecución de un bloque de código en un ciclo se conoce como iteración

RECURSION

La recursión es cuando una (sub)rutina llama a si misma

Análisis asintótico revisitado

-La asignación de una variable toma tiempo constante

-Cuando se llamada a una rutina toma tiempo constante, y luego hay que tomar en cuenta los pasos queconlleva

-Escribir una salida y leer una entrada simple ambos toman tiempo constante

Análisis de algoritmos recursivos

Para esto hay que escribir una ecuación recursiva para poder correctamente caracterizar la cantidad de llamadas que se hará a la rutina

bibliografia con la que me apoye para esta entrada:http://personales.unican.es/borgesce/Docencia/Algoritmica/Teoria/BloqueI3.pdf