Portafolio de Kimberly Ardon

Sabemos que el trabajo principal de una maquina guardar y recuperar información además de realizar cálculos. Ahora bien el problema radica en que la maquina debe saber que es lo que nosotros queremos que ella almacene o use para determinada tarea y es ahí donde nacen los tipos de datos.

Tipos de datos

Simples: Son aquellos que hacen referencia a un solo valor estos puede ser de tipo entero, flotante (decimal), lógico, y de tipo carácter.

Estructurados: Como su nombre indica estos tipos de datos son estructurados por otros tipos de datos generalmente de datos simples. Ejemplos de estos son los arreglos, y registros.

Una estructura de datos es cualquier representación de datos y sus operaciones asociadas.

Ambos son algoritmos de ordenamiento en secuencia en los cuales la información (datos) es colocada y luego retirada.

Para diferenciarlos conviene recordar dos cosas, primero a pila de libros y segundo la cola del supermercado, si retiramos un libro de la pila se hace con el ultimo que se dejó en la pila por eso la frase de la pila es “primero en entrar último en salir”. En cambio en la cola del supermercado siempre se atiende al que llego primero a si que “el primero en entrar es el primero en salir”.

Cabe mencionar la diferencia de una estructura estática de dinámica una pila o cola estática tienen un tamaño ya esta establecido mientras en el dinámico el tamaño lo decide el usuario durante la ejecución.

Es una representación enlazada de elementos de un cierto tipo de datos, la idea básica es construir una lista cuyos elementos llamados nodos tendrán dos partes, una contiene información y es de tipo simple y la segunda es un puntero que apunta al siguiente elemento de la lista. La diferencia entre listas enlazadas simples y dobles es que las dobles requieren más espacio y sus operaciones resultan más costosas pero facilitan su manipulación pues se puede tener acceso a un elemento de la lista en ambas direcciones, también se puede insertar o borrar un nodo si damos su dirección pero en las listas simples requieren la dirección del nodo anterior para borrar o insertar correctamente. Las listas enlazadas dobles apuntan tanto a quien las apunta como a quien tienen en frente como (Sauceda 2015) menciono “son elefantes mutantes que tienen dos cabezas y todos van tomados de sus trompas”.

Métodos básicos de las listas:

Inicialización o creación

Insertar

Eliminar

Buscar

Recorrer

Comprobar

Imprimir 

Podemos implementar este tipo de estructura para un supermercado cuando pasamos lo que compramos el cajero ingresa los datos de la compra y estos se guardan en la lista y ocupara el tamaño exacto de la lista no importa cuantos productos llevemos y podemos sacar de la lista cualquiera que no queramos llevar sin importar el lugar de su ubicación.

Alfred V. Aho,   John E, Horpcoroft   Jeffrey D. Ullman  (1983) Estructura de datos y algoritmos

“Un árbol es una estructura jerárquica sobre una colección de objetos. Los árboles se usan para organizar información en sistemas de bases de datos y para representar la estructura sintáctica de un programa fuente en los compiladores”(pag.76).

Estos se organizan en forma que el nodo raíz sea lo más importante del árbol luego los datos de menor tamaño se van a la izquierda y los de mayor tamaño a la derecha.

Existen dos tipos de árboles los arboles binarios de búsqueda (ABB) y AVL (se llama a si por los creadores de tal estructura Adelson- Velskii y Landis).

Los AVL se diferencian por su estructura los ABB pues son balanceados es decir que el factor de equilibrio esta de 1 a -1 mientras que el ABB no se preocupa por eso solo se  dedica  a almacenar ”izquierda-derecha, izquierda-derecha” si saber su factor de equilibrio.

Métodos que implementan

Crear

Construir (crea la raíz)

Verificar si esta vacío

ObtenerRaíz

ObtenerIzquierdo

ObtenerDerecho

Borrar

Insertar

Búsqueda Post-orden (raíz, izquierdo, derecho.

Búsqueda In-orden (izquierdo, raíz, derecho)

Búsqueda Pre-orden­  (raíz, izquierdo, derecho)

Método extra del AVL

Rotación (implementado para obtener la característica esencial del AVL y es que este equilibrado)

Aplicación

Se podría usar un árbol en una aplicación en la que se use quiera ver el nota de un grupo de alumnos usaríamos el 60 de nodo raíz y los reprobados quedarían en el sub árbol izquierdo y los aprobados en sub-árbol derecho.

Usualmente las aplicaciones que implementan grafos son las que buscan modelar rutas, planificar tareas,  incluso es implementada por sistemas de geo-posicionamiento global.

Es una representación de una gráfica cuyos punto de interés son llamados vértices estos a su vez están unidos por líneas que las conocemos como aristas.

Una definición formal de grafos que recopile de http://www.monografias.com/trabajos16/grafos/grafos.shtml  es:

“Un grafo es una terna G = (V, A, j), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices”.

Métodos de los grafos

Arista (u, v).

Arista Peso (u, v, w).

Borra Arista (u, v).

Elimina del grafo la arista (u, v).

Adyacente (u, v).  Operación que devuelve cierto si los vértices u, v están unidos.

Nuevo Vértice (u)

Borra Vértice (u, v)

Recorrer

Tipos de recorrido en un grafo

Recorrer consiste en visitar tomando un vértice de partida y analiza los enlaces a otros vértices, esto se puede hacer de dos formas en profundidad y en anchura:

Anchura

Los pasos a seguir son:

1. Marcar el vértice de partida
2. Meter en la cola el vértice de partida
3. Entrar en un bucle

3.1     quitar el nodo frente de la cola w  visitar w

3.2   meter en la cola todos los vértices adyacentes a w que no estén marcados como visitados

       4. Fin

Profundidad

Los pasos a seguir son:

1. se escoge el vértice de partida y se mete en la pila
2. se meten en la pila sus adyacentes no marcados y se marcan
3. fin

Se pueden clasificar en dos tipos: los grafos dirigidos y los no dirigidos.

Es existen varias opciones para representar los grafos todo depende de las necesidades ya que se puede usar matriz de adyacencia o una representación mediante listas de adyacencia, para un grafo con muchas aristas, es preferible usar una matriz, en cambio sí son pocas se usan listas de adyacencia que se ajustan al número de ellas.

También llamada matriz de costos ya que permite manipular mejor la información tal que podamos saber el costo de los caminos al conocerlos podemos obtener un camino más corto de un vértice a otro, o utilizar la información para otros fines.

Dijkstra busca un camino más corto a través de la matriz de caminos ¿Cómo lo hace?

Primero debe tenerse en cuenta que las aristas deben tener un costo no negativo.

Luego se debe tener dos arreglos S y D y la matriz de caminos.

S almacena los vértices de los cuales se conoce la distancia mínima usualmente se inicia con el

Vértice de partida.

D de almacena el menor costo de los vértices visitados

Al final del recorrido de la matriz de costos D tendrá la distancia mínima entre el vértice de partida y cada uno de los vértices al cual tiene acceso.

Yaddy sanchez y Wilfredo torrros En la pagina con vinculo http://www.unicauca.edu.co/matematicas/eventos/log&co/MEMORIAS/AlgoritmosVoraces_abstract.pdf lo definen de una mare muy acertada mencionan: “Son utilizados para solucionar problemas de optimización y toman decisiones basándose en la información que tienen de modo inmediato, sin tener en cuenta los efectos que estas decisiones pueden tener a futuro”.

Ejemplos de algoritmos voraces son: dijkstra, Prim, Kruskal.

Un algoritmo recursivo es aquel que se llama a si mismo, para lograrlo basta con hacer la llamada correspondiente dentro de cuerpo del sub-programa que se quiere hacer llamar al finalizar la ejecución es sustituida por el valor de retorno. Todo proceso recursivo puede convertirse en iterativo y viceversa la diferencia radica que los recursivos son más simples, pero son más lentos a la hora de ejecutarse y requieren más recursos.

Ejemplos de estructuras que pueden ser recursivos: Quicksort Pilas Colas

Analizamos varios algoritmos, queda ganar más experiencia en el empleo de ellos pues todos son importantes sin embargo, eso es cierto si se aplican correctamente, a lo que me refiero es, “que una decisión correcta, tomada por una razón equivocada puede ser incorrecta”.  Si tenemos las herramientas solo queda aprender a usarlas en momento correcto, para optimizar nuestros códigos.  

El trabajo realizado fue muy apropiado ya que son los temas y la investigación realizada hace que el los temas desarrollados en clase se tengan una mejor compresión o enfoque.