Notas de Estructuras de Datos

The ADT Matrix has you

Curso de segundo semestre de la licenciatura en Ciencias de la Computación (plan 2013). El contenido es sobre estructuras de datos; como listas, pilas, colas, gráficas, etc... Cómo se define un Tipo de Datos Abstracto, qué operaciones podemos definir sobre las estructuras y para que podemos usarlas.

Así con esta pequeña introducción dada, va una lista de las notas:

Java y XML

En estas notas, explico qué es un XML y cómo podemos usarlos en nuestra programación con Java.
Las notas tienen el siguiente anexo: Ejemplos XML.

Entrada y Salida con Java y más sobre Java y XML

En estas notas, describo cómo hacer lectura de archivos en Java, así comos escribir archivos: tanto existentes, como crear archivos nuevos. Por otro lado, se extiende el contenido sobre XML para incluir cómo escribir nuestros propios XML (o modificar un archivo ya existente).
Las notas tienen el siguiente anexo: Ejemplos entrada y salida

Recursión y Benchmarks

En estas notas, describo qué es la recursión. Entro en aspectos un poco más técnicos que en formalidades matemáticas. También se explica que es un benchmark y para qué se utilizan.
Las notas tienen el siguiente anexo: Ejemplo de recursión.

Backtracking

En estas notas, describo qué es el backtracking, usando los conocimientos previos en recursión de las notas anteriores. Se ejemplifica el backtracking con el problema de resolver un laberinto.
Las notas tienen el siguiente anexo: Ejercicio de backtracking.

Ejemplos de Listas

En estas notas, se introduce el Tipo de Datos Abstracto Lista y se propone un par de ejercicios:
  • Reconocimiento de palabras (o "toknes") dadas por el usuario. Estas palabras deberán relacionarse con todas las líneas en las que aparecen en un archivo de texto que proporcione también el usaurio.
  • El problema de José, como se le conoce a la adaptación presentada a un problema planteado originalmente por el historiador Flavius Josephus en el primer siglo de nuestra era.
Las notas tienen el siguente anexo: Ejercicios con listas

Programación genérica

En estas notas, describo qué es la programación genérica en Java y cómo hacer una clase genérica, siguiendo como ejemplo las clases java.util.ArrayList, java.util.LinkedList y java.util.Vector

Solución al problema de las torres de Hanoi

En estas notas, se plantea una solución al problema de las Torres de Hanoi y se plasma con un algoritmo recursivo. Luego, se da el reto de en base a dicha solución recursiva, construir una iterativa usando una sola pila, que deberá contener una representación de los contextos de cada paso recursivo.
Las notas tienen el siguiente anexo: Solución en Java.

Ejemplo de colas con planificación Round - Robin: Calendarización de procesos

Estas notas tratan un tema un tanto complicado para los primeros semestres de Ciencias de la Computación o Ingeniría en computación. Nos introduce a una de las técnicas más populares de calendarización de procesos (aka. "Cosas que tiene que hacer un procesador") para ejemplificar la utilidad y uso de la estructura de datos "Cola" mediante planificación Round - Robin.
Las notas tratan de fomentar la curiosidad del lector y puede consultar las referencias usadas para su elaboración para obtener más información al respecto de la calendarización de procesos en un sistema operativo. Si encuentra dificultades al entender los conceptos de Sistemas Operativos y Concurrencia que introducen estas notas, puede ignorarlos y concentrarse en el uso y funcionamiento de la cola que simula el ejercicio.
Las notas tienen los siguientes anexos:

Más ejemplo de colas

Usando ejemplos que se espera sean más simples que el de calendarización de procesos, se ejemplifica la utilidad y uso de colas con los siguientes problemas:
  • El problema de acomodo de trenes. El problema consiste básicamente en acomodar una serie de vagones de tren etiquetados con números naturales unívocos de forma que las etiqeutas en el tren acomodado sean de orden creciente.
  • Migrar la solución al problema de José para ahora usar una cola en lugar de una lista.
Las notas tienen el siguiente anexo: Ejercicios con colas

Aplicaciones de árboles

En estas notas revisamos una aplicación de la estructura de datos árbol. Los árboles son una de las estructuras de datos más útiles en computación; nos ayudan a organizar conjunto de datos, agrupados por alguna característica común en subárbobles. Por ejemplo, una desigualdad tricotómica, que puede resultar en un orden total o parcal; respectivamente cuando permitimos valores repetidos o únivocos en cada nodo del árbol. Esto hace las búsquedas tremendamente eficientes.
También podemos usarlos para representar lenguajes formales y crear compiladores de lenguajes de programación, modelar colas de prioridades y formar procesos en un ár;bol, como hacen algunos sistemas operativos.
Y el caso que vamos a estudiar: modelas sistemas de archivos.
Las notas tienen el siguiente anexo: Ejemplo de explorador de archivos

Códigos Hash

En esta lectura, se estudian y exploran las funciones hash: qué es una tabla hash (o diccionario/mapa parcialmente ordenado), qué es una función de compresión, qué es una colisión y una breve introducción a cómo usar hashing en Java.