La geometría computacional es una rama que extiende el diseño y análisis de algoritmos, esta se comprende del estudio sistemático de algoritmos y estructuras de datos que refieran a objetos geométricos, esta área reúne tanto problemas matemáticos como problemas de ciencias de la computación, tiene aplicación en distintos campos como lo pueden ser la robótica, los gráficos por computadora o sistemas de ubicación geográfica, para dar una breve introducción veremos un algoritmo perteneciente a un problema estático que proviene de esta rama siendo un algoritmo para encontrar el cierre convexo dada una nube de puntos.
Veamos entonces el algoritmo para encontrar el cierre convexo (convex haull), este se refiere al polígono convexo que tenga en su interior todos los puntos, al ser un polígono convexo esto indica que todos los ángulos interiores son menores o iguales a 180 grados, dicho algoritmo es conocido como el algoritmo de graham (scan de graham), partimos encontrando el punto que tiene la coordenada mas pequeña en el eje Y, lo llamaremos p, tenemos ahora un angulo polar entre p y el resto de puntos, ordenamos dichos puntos de acuerdo al angulo polar que forman con p, una vez ordenados lo que haremos sera inicializar una pila en la que meteremos los primeros 2 puntos de nuestro ordenamiento, nos fijamos en la orientación que toma el angulo del punto en la pila con respecto al tercer punto en el ordenamiento si la orientación es de acuerdo al sentido contrario a las manecillas del reloj entonces lo metemos a la pila, si la orientación respecto al siguiente punto ordenado no es de acuerdo al sentido contrario a las manecillas del reloj entonces significa que ese punto no debería estar ahí por lo que quitamos el punto de la pila y comparamos la orientación con el punto actual de la pila y el siguiente punto ordenado, hacemos esto hasta que el punto que tengamos que meter sea igual a nuestro p inicial, lo que indica que habremos acabado y los puntos que están en la pila son los que forman nuestro cierre convexo, este algoritmo tiene una complejidad O(nlogn) por el tiempo que nos toma ordenar los puntos. A continuación se anexa un video de la mano del canal de youtube Inside code que explica el algoritmo y también muestra como seria una ejecución,(el video esta en ingles pero es posible activar subtítulos en español para una mayor comprensión):
Ahora toca explorar un algoritmo que es popularmente usado para la compresión de datos, estamos hablado del algoritmo para compresión de huffman, dicho algoritmo ofrece una compresión eficiente para los datos y es sencillo de entender, la idea del algoritmo es que dadas cadenas de símbolos contemos sus apariciones donde cada símbolo debe ser exactamente igual para contar las apariciones, por ejemplo no es lo mismo una "e" en la cadena que una "é" o "E", en este caso se contarían como símbolos distintos, podemos ordenar en una tabla de menor a mayor los símbolos totales en nuestra cadena seguidos de sus frecuencias, una vez contadas todas las frecuencias y registradas en nuestra tabla procedemos entonces con la construcción de un árbol binario, existen diferentes maneras para la construcción, pero se desea que los caracteres con frecuencias similares queden en un mismo nivel del árbol, para esto usaremos la estrategia de fijarnos en nuestros dos símbolos que tengan el menor numero de frecuencias, estos 2 símbolos serán nuestros dos nodos hoja que conectaremos a un nodo padre que tendrá la suma de las frecuencias de sus hijos, por lo que habremos creado un sub-arbol cuya frecuencia es igual a la suma de las frecuencias de sus hijos, podemos si se desea ubicar cual seria la posición de nuestro sub-arbol creado en la tabla de frecuencias para así saber que nodos deberíamos conectar a continuación, dicha conexión se realiza siempre tomando dos nodos y uniéndolos a un nodo padre que tenga la suma de frecuencias de ambos nodos, la idea de la construcción es ir conectando los nodos según las frecuencias menores para que los símbolos con menos repeticiones queden en los niveles inferiores del árbol y los símbolos con mas repeticiones queden en los niveles superiores del árbol, una vez que terminemos de conectar nuestros nodos nos quedara un solo árbol binario que contendrá todos nuestros símbolos de la cadena original, ahora para finalizar etiquetamos a todas las aristas que sean ramas izquierdas en nuestro árbol con 1 y etiquetamos con 0 todas las aristas que sean ramas derechas en nuestro árbol final, una vez listo nuestro árbol binario etiquetado la codificación de huffman en bits para cada símbolo sera la trayectoria desde la raíz de nuestro árbol hasta el nodo que contenga el símbolo de manera que cada que pasamos por una rama izquierda se agregara un 1 y si pasamos por una rama derecha se agregara un 0, al final la cadena de bits que representa la codificación dependerá de cuales ramas (izquierda o derecha) y cuantas ramas recorrimos en la trayectoria hasta llegar a nuestro símbolo en el árbol. A continuación se anexa un video con un ejemplo sencillo de aplicación del algoritmo de huffman de la mano del canal de youtube Matematicas con Jmq Mattosky:
Ademas de algoritmos para compresión también existen algoritmos aplicados para graficas donde si se llevo un curso de estructuras de datos le serán familiares algoritmos para recorrer graficas como lo son DFS (depht first search/búsqueda por profundidad) o BFS (brief first search/ búsqueda por amplitud), ambos algoritmos probablemente fueron introducidos para recorrer un tipo de grafica que ya conocemos bien, es decir un árbol, adicionalmente ambos tienen la complejidad O(|V| + |E|) donde |V| representa la cantidad de vértices en la grafica y |E| representa la cantidad de aristas en la grafica. Si se siente perdido en el tema anexamos a continuación un video de la mano del canal de youtube FLAGlab Uniandes que explica ambos algoritmos a detalle:
Sabemos ademas que existen graficas en las que las aristas tienen peso (graficas o grafos ponderados), esto se hace generalmente con el propósito de modelar distintas rutas que tienen un coste al pasar por ellas para llegar de punto A a punto B, normalmente lo que esperaríamos en un problema de este estilo es encontrar el camino mas corto que podemos recorrer, por lo que usamos un algoritmo que quizás resulta familiar, dicho algoritmo es el algoritmo de dijkstra, en dicho algoritmo la idea es iniciar desde un nodo y visitar todos sus vecinos donde a cada vecino le pondremos una etiqueta que sera [coste, nodo], en el coste sumaremos el peso de las aristas recorridas y en el nodo pondremos el nodo del que se visita, una vez agotemos todos los vecinos nos fijamos en el vecino en cuya etiqueta el coste sea menor, ahora repetiremos el proceso para ese nodo visitando sus vecinos y sumando el coste de las aristas, si se ya se tiene una etiqueta para ese nodo simplemente se actualiza la etiqueta [coste, nodo] con el coste acumulado y el nodo de donde estemos trabajando, esto se repite hasta llegar a nuestro nodo destino y entonces solamente queda reconstruir nuestro camino observando de donde viene cada conexión en los nodos. Puede ser útil ademas para este tipo de problemas encontrar el árbol generador mínimo (Minimum Spanning Tree), por lo que existen 2 algoritmos que nos facilitan la obtención del mismo que utilizan el paradigma de programación glotona, estos algoritmos son los de Prim y Kruskal. el algoritmo de prim consiste en fijarnos en la arista de menor peso siempre, dada una grafica ponderada nos vamos a fijar en la arista que tenga menor peso, dicha arista junto con sus vértices se ira a nuestro conjunto de árbol generador, ahora, verificaremos las aristas de los vértices en nuestro conjunto árbol y tomaremos aquella arista que tenga el menor peso entre ellas junto con su conexión al vértice cuidando siempre que no nos genere un ciclo, este paso lo vamos a repetir hasta tener n-1 aristas en nuestro conjunto árbol generador donde n es la cantidad total de vértices en la grafica. el algoritmo de kruskal consiste en primero ordenar las aristas por peso del peso mas pequeño al mas grande y agregar en el conjunto de árbol generador dichas aristas en el orden que presentan cuidando también que no generen un ciclo. A continuación se dejan un par de videos ilustrativos donde se ejemplifican los algoritmos de manera detallada, adicionalmente un extracto que explica a profundidad los algoritmos de prim y kruskal:
Algoritmo de dijkstra de la mano del canal de youtube Juan maTIC:
Ejemplo de Algoritmos de Prim y Kruskal de la mano del canal de youtube SUPERA MATES:
También a la hora de trabajar con graficas podemos encontrarnos con graficas dirigidas las cuales tienen la particularidad de que para cada par de nodos conectados solo podemos ir de uno a otro esto esta determinado por la dirección que toma la arista, esta determina hacia que nodo podemos movernos a partir del que ya estamos, las aplicaciones de algoritmos para estas graficas también son posibles pues es posible por ejemplo obtener el camino mas corto usando dijkstra igualmente, adicionalmente veremos un algoritmo que soluciona la ruta mas corta usando programación dinámica como manera alternativa
Ruta mas corta con programación dinámica de la mano del canal de youtube Alvaro Jesus Nina Laura :
Ademas estas graficas dirigidas suelen indicar también problemas de redes de flujo las cuales se modelan como una grafica dirigida donde tenemos un nodo de inicio (también llamado fuente) generalmente nombrado s y un nodo destino (también llamado sumidero) que generalmente nombramos t , cada arista tiene una capacidad por la cual puede pasar el flujo la cual se agota hasta que dicha arista no pueda permitir mas flujo digamos un indicador como [flujo/capacidad], generalmente se busca obtener el flujo máximo, es decir obtener si existen los caminos que no saturan la red desde nuestro punto inicial hasta nuestro punto final, un algoritmo bastante conocido para redes de flujos es el algoritmo ford fulkerson el cual se auxilia de caminos aumentantes que pueden incrementar el flujo total hasta que ya no sea posible incrementarlo mas, primeramente encontramos trayectorias que nos lleven al sumidero de tal manera que veamos que el flujo puede seguir aumentándose, es decir que no se a excedido la capacidad de la arista, posteriormente tendremos que determinar si podemos enviar flujo adicional a través de algún camino que tengamos, este flujo restante estará delimitado siempre por la capacidad restante en las aristas del camino y deberemos actualizar los valores del flujo y la capacidad de la arista conforme realicemos este procedimiento, repetimos el procedimiento de encontrar los caminos hasta que ya no halla ningún camino por el cual enviar flujo entonces la suma de flujos enviados sera el flujo máximo que podremos mandar, el algoritmo como tal tiene complejidad O(E * F), siendo E las aristas y F el flujo máximo, existe una mejora al algoritmo que utiliza BFS y logra una complejidad de O(V + E^2), siendo este el algoritmo de Edmonds-Karp. A continuación se anexa un video que contiene un ejemplo del funcionamiento del algoritmo y se dejan 2 extractos donde se explican a detalle ambos algoritmos:
ejemplo del Algoritmo de Ford Fulkerson de la mano del canal de youtube 24h Vending:
Adicionalmente se dejan 2 extractos del sitio web W3schools donde se explican a detalle los algoritmos de ford fulkerson y la mejora al algoritmo de Edmonds-Karp (ambas referencias se encuentran en ingles por lo que se recomienda traducir en caso de que no se logre comprender, una traducción importante para casos de graficas es que para referirse a las aristas se usa "edge" en ingles):
Ahora es turno de describir otra estrategia para resolver problemas, vimos que para los ordenamientos utilizamos el paradigma de divide y vencerás, sin embargo cuando podemos descomponer un problema en varios sub-problemas y estos a su vez tienen otros problemas superpuestos es decir estos sub-problemas pueden necesitar repetirse varias veces mientras resolvemos el problema inicial, entonces es un indicio de que podemos resolver el problema usando Programación Dinámica, la cual es una estrategia de programación usada cuando se desea evitar el calculo repetido de sub-problemas guardando el calculo de la solución para el problema que se repite y evitando la repetición del calculo para este mismo, es también buena idea usar programación dinámica cuando notamos que nuestro problema tiene una sub estructura optima, esto es cuando para hallar la solución optima del problema inicial tenemos que también hallar una solución optima paralos sub-problemas en los que dividimos el problema inicial, en otras palabras nos ayuda para resolver problemas de optimización. Una buena manera de saber si podríamos necesitar programación dinámica es pensar en una solución para el problema, si dicha solución "inocente" tiene una complejidad cuadrática entonces es posible que necesitemos usar programación dinámica. Para desarrollar un algoritmo usando programación dinámica necesitaremos una secuencia de 4 pasos que serán, primero la caracterización de la solución, es decir, describir la estructura de nuestra solución optima, visualizar la solución optima de nuestro problema para posteriormente aplicar el segundo paso, la recursión, que sera definir el valor de esta solución optima de manera recursiva, construyendo el algoritmo recursivo, lo siguiente es el tercer paso la memorización donde calcularemos el valor optimo y veremos donde guardar nuestros valores previos para poder utilizarlos posteriormente, finalmente el ultimo paso es la construcción de la solución optima esta es dada por la información que ya calculamos anteriormente. Cabe mencionar que también se puede utilizar la programación dinámica utilizando la tabulacion que es la técnica de resolver iterativamente desde el sub-problema mas pequeño hasta el sub-problema principal construyendo una tabla con los resultados y haciendo uso de la misma durante la resolución de los problemas. Como siempre se deja un video de apoyo para comprender de mejor manera el tema con ejemplos para una mayor claridad de la mano del canal ChioCode:
Algunos ejemplos populares de problemas que pueden ser resueltos con programación dinámica son encontrar la subsecuencia común mas larga o la multiplicación de una secuencia de matrices, particularmente encontrar la subsecuencia común mas larga es interesante por que puede ser extendida al reconocimiento de patrones lo cual es útil cuando hablamos de inteligencia artificial y lo que refiere al análisis y comparación de datos, a continuación se dejan 2 videos de apoyo que ilustran la solución de ambos problemas de manera amplia utilizando programación dinámica:
Algoritmo para encontrar la subsecuencia común mas larga de la mano del canal de youtube Xavier Ochoa:
Algoritmo para la multiplicación de una secuencia de matrices de la mano del canal de youtube Preparación Estudiantil de 10:
De la mano con la programación dinámica vienen también los algoritmos voraces o greedy algorithms que son usados cuando se nos presentan problemas que tienen sub-problemas cuyas posibles soluciones son demasiadas, estos algoritmos tienen como principio que si se topan con varias opciones se elija la que parece mas adecuada en ese momento, este puede en un principio no dar la solución optima a todos los problemas pero puede dar una solución suficiente para los mismos, el principio de elegir la opción mas optima en lugar de calcular todas las posibles soluciones y de entre ellas elegir la mas optima puede resultar mas intuitivo y sencillo, entonces hay que saber, ¿como podemos ver si con un algoritmo voraz es suficiente para resolver el problema y no tener que quebrarnos la cabeza con la solución de programación dinámica?, pues lo cierto es que al ir de la mano ambos conceptos para cada solución que utiliza un algoritmo voraz, generalmente existe otra solución al problema usando programación dinámica pero esta solución suele ser mas complicada, entonces para ver si nuestro problema puede ser resuelto con un algoritmo voraz necesitamos prestar atención a 2 propiedades la sub-estructura optima y la selección greedy,la sub-estructura optima es como mencionamos antes, dado un problema principal, si la solución optima de este problema necesita la solución optima de los sub-problemas que vallamos generando, esto indica que tenemos una sub-estructura optima, la segunda y mas importante es la selección greedy la cual consta de saber que podemos construir la solución optima global usando la elección de las opciones locales sin tener en cuenta los resultados de otros sub-problemas, es decir, tenemos que poder realizar esta elección sin depender de los resultados de los otros sub-problemas, tenemos ademas que probar que esta elección que realizamos en el algoritmo lleve a la solución optima global, esto se hace examinando alguna solución optima global que tenga algunos sub-problemas, suponemos que nuestro algoritmo greedy no da la solución optima con la selección que tenemos, entonces usamos una selección alternativa a la que toma nuestro algoritmo y eventualmente si la selección alternativa da una solución menos optima llegaremos a una contradicción por que se supone que nuestro algoritmo greedy no da la solución optima, con esta contradicción exhibida podemos decir que la contradicción viene de suponer que nuestro algoritmo greedy no era optimo y por ende para que no exista contradicción entonces nuestro algoritmo greedy es en efecto optimo, lo complicado para estos casos es entonces demostrar que nuestro algoritmo voraz da la solución optima siempre. A continuación se deja un video de apoyo sobre el tema de la mano del canal de youtube ChioCode en el que muestra también algunos ejemplos, ademas se anexan otros 2 videos de ejemplos concretos con problemas solucionados con algoritmos voraces:
Comenzamos entonces con los ordenamientos, el primer tema del curso. Si se ha tomado antes un curso sobre estructuras de datos entonces le sera familiar el tema. Aquí se dará un vistazo los algoritmos ya existentes que se han inventado para la ordenación de elementos, aquí hay algunos videos del canal Chio Code que explican estos algoritmos de una manera simplificada para mayor comprensión:
QuickSort: Este es un algoritmo de ordenamientos clásico que parte de la estrategia divide y vencerás, la idea del algoritmo es elegir un pivote en nuestro arreglo de elementos a ordenar una vez seleccionado entonces tendremos 2 sub arreglos de elementos, los que sean mayores que el pivote y los que sean menores que el pivote, la idea es aplicar el algoritmo anterior recursiva mente sobre los sub arreglos de elementos que vallamos formando para eventualmente lograr ordenar nuestros elementos, el punto malo es que la selección de nuestro pivote es importante para la complejidad del algoritmo puesto que si se elije un mal pivote, uno en el que por ejemplo todos los elementos son mayores o menores que el pivote entonces esto puede disparar nuestra complejidad hasta volverla cuadrática en el peor caso. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
MergeSort: También basado en la estrategia de divide y vencerás la idea de este algoritmo es dividir nuestro conjunto de elementos en mitades hasta que se llegue al subconjunto mas pequeño que contiene solo un elemento una vez hecho esto comparamos los sub arreglos para combinarlos en un nuevo sub arreglo que ya esta ordenado, hacemos lo mismo para los sub arreglos restantes hasta que eventualmente nos quede un nuevo arreglo que estará completamente ordenado, como dividimos nuestro arreglo original y luego lo combinamos para formar los sub arreglos ordenados la cantidad de veces que lo fuimos dividiendo siempre entonces este algoritmo tiene una complejidad O(nlogn) siempre, la cual es la máxima a la hora de ordenar con elementos que no conocemos. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
InsertionSort: Este algoritmo de ordenamientos es el mas intuitivo de todos dado un arreglo que queremos ordenar seleccionamos nuestro elemento a ordenar como pivote y lo comparamos con el resto de elementos para determinar la posición a la que pertenece, esto mismo lo haremos con el resto de elementos en el arreglo, al final del algoritmo tendremos entonces las posiciones correspondientes a cada elemento en nuestro arreglo y estará ordenado, lo malo es que no es muy eficiente puesto que al seleccionar uno y comparalo con el resto, para cada elemento que tenemos en el arreglo dará una complejidad cuadrática para el algoritmo por lo que seria ineficiente para arreglos que tengan un tamaño muy grande. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
Aunque la cota máxima para ordenar elementos que no conocemos es O(nlogn) hasta la fecha si dichos elementos son números entonces existen algoritmos que pueden ordenar mas eficientemente ya que no usan comparaciones, se auxilian mas bien de rangos que ya tengan cierto orden para usarlos como guiá y poder con ellos determinar la posición de nuestros números, estos son los algoritmos de counting sort y radix sort, A continuación dejamos dos videos del canal ChioCode en los que se explican a detalle dichos algoritmos:
Counting Sort:
RadixSort:
Podemos ademas, ordenar nuestros elementos haciendo uso de arboles binarios, auxiliandonos de estructuras de datos que ya hemos visto anteriormente como lo son los arboles de torneo, los montículos mínimos(min-heaps) y montículos máximos (max-heaps), un algoritmo popular que hace uso de lo antes mencionado es el llamado heap-sort, este consta de interpretar nuestro arreglo como un arbol binario y hacer uso de un max-heap, para poder ordenar los elementos en nuestro arreglo nos fijamos en la raíz que sera el elemento mas grande en nuestro arreglo y lo intercambiamos con el ultimo elemento del arreglo, dicho elemento sera una hoja del max-heap, procedemos a eliminar esa hoja, así tenemos ordenada nuestra ultima entrada en el arreglo, consideramos nuestro arreglo desde la primer hasta la entrada n-2 (pues la ultima ya esta ordenada) como otro árbol binario y auxiliandonos nuevamente de un max-heap repetimos el proceso anterior, esto lo hacemos hasta que nos quede solo la raíz y por tanto nuestro arreglo estará ordenado totalmente. Para una mejor ilustración del funcionamiento y complejidad del algoritmo tendremos el siguiente video de apoyo de la mano del canal Michael Sambol (el video esta en ingles pero se pueden activar subtítulos en español por si resulta difícil de entender):
Ya vimos como ordenar cosas, pero también hay que ver como podemos buscar cosas, los dos algoritmos mas populares serian búsqueda lineal y búsqueda binaria, la búsqueda lineal sigue el simple principio de dado el elemento que se desea buscar recorrer todo el arreglo donde queremos buscar y eventualmente encontrar nuestro elemento si se encuentra, si acabamos de recorrer nuestro arreglo sin coincidencias de dicho elemento significara que no estaba en el arreglo, la otra forma es búsqueda binaria la cual resulta mas eficiente puesto que vamos restringiendo los rangos de búsqueda en el arreglo, primeramente ordenamos nuestro arreglo, una vez ordenado nos posicionamos a la mitad de este y observamos si de casualidad ese es el elemento buscado si lo es lo encontramos, si no lo es entonces observamos que relación tiene nuestro elemento buscado con el elemento de la mitad del arreglo, si es menor entonces aplicamos el algoritmo en el sub arreglo desde la posición anterior a nuestro pivote en el arreglo hasta el inicio del arreglo, si es mayor entonces aplicamos el algoritmo en el sub arreglo desde la posición siguiente a nuestro pivote en el arreglo hasta el final del arreglo, hacemos este procedimiento recursivamente hasta encontrar nuestro elemento buscado. A continuación dejamos dos videos referentes a dichos algoritmos para una mejor compresión:
Búsqueda binaria, de la mano del canal de youtube Coding Tree:
Busqueda lineal, de la mano del canal de youtube Programa Tutos:
Usando la idea de Quick-sort podemos encontrar otro algoritmo eficiente para buscar el k-esimo elemento mínimo el cual se conoce como Quick-selection, supongamos un arreglo de tamaño n, en el algoritmo elegimos un pivote que similarmente a quick-sort ordene a la izquierda los elementos menores y a la derecha los elementos mayores a nuestro pivote, si el pivote y nuestro indice en el arreglo k-1 (puesto que el arreglo va de 0 a n-1) son iguales, significa que hallamos nuestro k-esimo elemento deseado, de lo contrario similarmente a búsqueda binaria comparamos la relacion entre nuestro indice k-1 buscado con el indice de nuestro pivote si es mayor a nuestro k-1 buscado entonces buscaremos en el sub arreglo desde 0 hasta el indice anterior de nuestro pivote y aplicamos el algoritmo en ese sub arreglo, de lo contrario entonces el rango del sub arreglo sera desde el indice siguiente de nuestro pivote hasta el indice n-1 del arreglo y aplicamos el algoritmo en este sub arreglo, hacemos este procedimiento recursiva mente hasta encontrar nuestro k-esimo elemento. Este algoritmo tiene un tiempo promedio O(n) (lineal) en el mejor caso, pero como esta basado fuertemente en Quick-sort la selección del pivote afecta la complejidad del misma puesto que si nos tocan varios pivotes malos seguidos en los que descartemos solo un elemento como en Quick-sort la complejidad se dispara a cuadrático. A continuación dejamos un video para una mayor comprensión del algoritmo de la mano del canal de youtube CS Robot (el video igualmente esta en ingles pero se pueden activar subtitulos en español por si se tiene dificultad al comprender):
Hemos visto que en algoritmos que se selecciona un pivote aleatorio existe la posibilidad de que si se selecciona mal nuestra complejidad sufra bastante, por ello también veremos como poder buscar un buen pivote para, con la ayuda de este algoritmo poder tener siempre una buena complejidad en dichos algoritmos mencionados anteriormente, vamos entonces a encontrar la mediana de medianas, para este algoritmo suponga que tenemos una lista de n elementos, vamos a dividir dicha lista en particiones de 5, si la lista no tiene longitud de algún múltiplo de 5 quiere decir que en una sub-lista nos quedaran menos de 5 elementos pero no hay ningún problema con ello, ahora ordenamos las sub-listas que al estar restringidas por elementos de a lo mas 5 siempre entonces ordenarlos sera lineal, una vez hecho esto podemos posicionarnos a la mitad de cada lista y esa sera su mediana, en otra lista digamos M almacenamos las medinas de cada sub-lista creada, ordenamos la lista M y seleccionamos la mitad, el elemento en la mitad sera entonces nuestra mediana de medianas buscada todo esto en tiempo lineal, esto puede aplicarse a algoritmos que dependan de un buen pivote como Quick-sort o Quick-selection para mejorar su complejidad significativamente. A continuación dejamos un articulo que explica a detalle el algoritmo (el material esta en ingles por lo que se recomienda traducir el texto en algún traductor online por si no es clara alguna parte.):
Ahora veamos una breve introducción a que es el análisis de algoritmos, donde ademas de ver un panorama general también tendremos que entender la notación Big O, la cual trataremos a lo largo del curso y con la que se medirá que tan eficiente es nuestro algoritmo en la mayoría de casos:
Notación Big O:
Ambos videos pertenecen al canal de youtube Chio Code el cual es una fuente bastante buena para encontrar material útil que puede ser aprovechado para la carrera. El link del canal por si deseas visitarlo es el siguiente:Canal de Chio Code.
Se recomienda la siguiente pagina web para visualizar las ejecuciones de los algoritmos que se vallan presentando: VisuAlgo, donde también se encuentran ejemplos de implementación. También la pagina web W3schools
donde en el apartado DSA se pueden encontrar explicaciones mas
profundas para algoritmos que revisaremos, la pagina se encuentra en
ingles así que se recomienda que de no ser clara alguna parte se ocupe
algún traductor en linea para poder entender los conceptos se recomienda
el traductor DeepL.
Este es un sitio web dedicado a la recopilación de algunos videos y materiales que se encuentran en la web sobre el diseño y análisis de algoritmos. Se presentaran dichos materiales de acuerdo al temario oficial de la carrera Ciencias de la Computación, impartida en la Facultad de Ciencias de la UNAM. Esperamos que estos recursos sean de utilidad para la gente que visite este pequeño sitio web.
