algoritmia 3.0.3

A library of algorithms and data structures. Used in course EI1022/MT122 (Universitat Jaume I de Castelló)

Biblioteca algoritmia

Implementada en Python 3.

Utilizada en dos asignaturas de la Universitat Jaume I de Castelló:

• EI1022: Grado en Ingeniería Informática.
• MT1022: Grado en Matemática Computacional.

Contenido

Estructuras de datos:

• Colas: Fifo, Lifo
• Listas enlazadas: LinkedList
• Grafos: Digraph, UndirectedGraph
• Montículos: MinHeap, MaxHeap
• Diccionarios de prioridad: MinHeapMap, MaxHeapMap
• Conjuntos disjuntos: MFSet

Algoritmos sobre grafos:

• Recorridos de vértices y aristas
• Componentes conexos
• Árbol de recubrimiento mínimo
• Camino más corto
• Algoritmo de Dijkstra

Esquemas algorítmicos:

• Búsqueda con retroceso (backtracking)
• Ramificación y acotación (brand and bound)
• Divide y vencerás (divide and conquer)
• Reduce y vencerás (reduce and conquer)

Problemas:

• Mochila (Knapsack)
• Cambio de moneda (Coin change)
• Empaquetado (Bin packing)
• Viajante (Travelling salesman)
• N-reinas (N-queens)
• Coloreado de grafos (Graph coloring)
• Voraces exactos: MST (Kruskal y Prim), mochila fraccionaria