edittler / tda-fiuba Goto Github PK
View Code? Open in Web Editor NEWTrabajos prácticos de la materia TDA de FIUBA
Trabajos prácticos de la materia TDA de FIUBA
El algoritmo de ordenamiento por selección busca el menor elemento de una secuencia y lo intercambia con el primero. Se propone realizar k selecciones para encontrar el k elemento más pequeño.
Se usa una estrategia de división y conquista similar a la de quicksort pero descartando las divisiones que sabemos que no incluyen al k buscado.
Similar a BFS, pero encola los vértices en una cola de prioridad según una heurística de acercamiento al destino.
Esto es, ignora los pesos de las aristas pero consulta una función heuristica(v)
que da una aproximación de la distancia entre un vértice del camino, y el destino final.
h(v) = R(u)
.h(v) << R(v)
.h(v) >> R(v)
.Se propone usar un heap para almacenar los k elementos más chicos, intercambiándolos cuando sea necesario.
Dado un vértice de origen y de destino implementa el algoritmo de Dijkstra de camino mínimo.
h(v) = R(u)
.h(v) << R(v)
.h(v) >> R(v)
.Analizar qué algoritmo es el óptimo para cada k según el tamaño de la entrada (n).
En general, recomendamos seguir un patrón de diseño parecido al de Robert Sedgewick en Algorithms (2011, 4.ª ed.).
En primer lugar, TAD Grafo inmutable de funcionalidad mínima, y en segundo lugar un TAD separado para la búsqueda de caminos, con cuatro implementaciones diferentes.
El TAD Grafo mantendrá la mínima representación necesaria del grafo. Como es dirigido y pesado, se recomienda usar una pequeña clase Arista para guardar los pesos.
En cuanto a los algoritmos, se recomienda:
visitado(v)
: si se visitó un determinado vértice durante el recorridodistancia(v)
: la distancia hasta un vértice visitado (si no fue visitado, devolver ∞)camino(v)
: la lista de aristas desde el origen hasta un vértice (puede devolver null si el vértice no fue visitado, y una lista vacía en caso de pasarse el vértice de origen)distancia(v)
(explicado arriba)_edge_to(v)
: la arista que conduce a un vértice v en el camino de origen a destinoComo ejemplo en Python, el TAD Grafo podría plantearse así:
class Digraph:
"""Grafo no dirigido con un número fijo de vértices.
Los vértices son siempre números enteros no negativos. El primer vértice
es 0.
El grafo se crea vacío, se añaden las aristas con add_edge(). Una vez
creadas, las aristas no se pueden eliminar, pero siempre se puede añadir
nuevas aristas.
"""
def __init__(g, V):
"""Construye un grafo sin aristas de V vértices.
"""
def V(g):
"""Número de vértices en el grafo.
"""
def E(g):
"""Número de aristas en el grafo.
"""
def adj_e(g, v):
"""Itera sobre los aristas incidentes _desde_ v.
"""
def adj(g, v):
"""Itera sobre los vértices adyacentes a ‘v’.
"""
def add_edge(g, u, v, weight=0):
"""Añade una arista al grafo.
"""
def __iter__(g):
"""Itera de 0 a V."""
return iter(range(g.V()))
def iter_edges(g):
"""Itera sobre todas las aristas del grafo.
Las aristas devueltas tienen los siguientes atributos de solo lectura:
• e.src
• e.dst
• e.weight
"""
class Arista:
"""Arista de un grafo.
"""
def __init__(self, src, dst, weight):
...
Considera tanto la heurística como el peso de las aristas para encontrar el camino mínimo.
h(v) = R(u)
.h(v) << R(v)
.h(v) >> R(v)
.Se implementa un verificador que dado un conjunto y un candidato devuelve un booleano indicando si el valor indicado es el k elemento más pequeño. El algoritmo de fuerza bruta itera todos los elementos del conjunto y verifica de a uno si es la solución. Una vez el verificador devuelve true, devuelve ese elemento.
Dado un vértice de origen implementa el recorrido en anchura ignorando los pesos. Esta variación finaliza el algoritmo cuando se visita el destino.
h(v) = R(u)
.h(v) << R(v)
.h(v) >> R(v)
.Así como heapsort es una mejora del algoritmo de selección usando un heap, este algoritmo mejora el de k-selecciones haciendo k extracciones a un arreglo con la propiedad de heap.
Ordena el conjunto mediante un algoritmo veloz de comparación y luego seleccionar el k elemento del arreglo ordenado.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.