He estado buscando un buen curso en línea en estructuras de datos, pero descubrí que Google también devuelve resultados para cursos de algoritmos, que dicen cosas como:

En este curso aprenderá varios principios fundamentales del diseño de algoritmos: métodos de dividir y conquistar, algoritmos de gráficos, estructuras prácticas de datos (montones, tablas hash, árboles de búsqueda) , algoritmos aleatorios y más. [fuente]

y

Al final de esta clase, comprenderá los conceptos clave necesarios para diseñar nuevos algoritmos para gráficos y otras estructuras de datos importantes y para evaluar la eficiencia de estos algoritmos. [fuente]

y

Este curso proporciona una introducción al modelado matemático de problemas computacionales. Cubre los algoritmos comunes, los paradigmas algorítmicos y las estructuras de datos utilizadas para resolver estos problemas . [fuente]

Mi pregunta es: ¿los algoritmos y las estructuras de datos están íntimamente relacionados, lo que significa que deben entenderse juntos o es un tema más fundamental que el otro?

EDITAR: Para aquellos que voten para cerrar esta pregunta, ¿podrían decirme por qué y tal vez cómo mejorarla? Aprender a hacer las preguntas correctas es parte del proceso educativo.

Existen todo tipo de mezclas. Tiene estructuras de datos, que no están asociadas con algoritmos, algoritmos, que no requieren estructuras de datos (reales), pero la mayoría de las veces vienen en un paquete.

Editar: como @Doval señaló correctamente, las estructuras de datos per se no tienen ninguna operación asociada con ellas. El acto de combinar la estructura de datos y el algoritmo forma un tipo de datos abstracto.

Estructuras de datos sin algoritmos.

Considere, por ejemplo, una estructura de datos para almacenar coordenadas bidimensionales, llamadas apropiadamente Point. No hay mucho en términos de algoritmos que ser hecho por un punto y realmente es sólo un contenedor para una xy yvalor. Por supuesto, al dar esta estructura de datos, ahora puede agregar todo tipo de algoritmos (cálculo de distancia, cascos convexos, lo que sea que tenga).

Puede pensar en muchas estructuras de datos, que son simplemente una acumulación de datos individuales. Si bien esto ocurre con frecuencia en la práctica, no es un buen material de enseñanza, porque no hay nada que aprender de él, una vez que haya entendido, que los elementos de datos individuales se pueden acumular en una nueva estructura de datos (como lo que aprende después del Pointejemplo anterior , si le proporciono esa asombrosa estructura de datos llamada Point3D, ¿qué puede hacer lo mismo para el espacio tridimensional?)

Algoritmos sin estructuras de datos (reales)

"Real", porque obviamente cada algoritmo interesante necesita tipos de datos primitivos como enteros o booleanos, y no queremos considerarlos como estructuras de datos en este contexto. De manera similar a lo anterior, estos algoritmos suelen ser bastante simples. En particular, no vienen con un estado complicado de ningún tipo, porque eso generalmente entra en una estructura de datos (ver la siguiente sección).

Un ejemplo para tal algoritmo sería calcular el máximo común divisor de dos números. Los algoritmos de Euklid para el mcd solo necesitan tener dos enteros y los manipula.

Sin embargo, una vez que las cosas comienzan a ponerse más interesantes, muy pronto ingresas al mundo de los tipos de datos abstractos. Por ejemplo, el tamiz de Eratóstenes se basa en una matriz. Podríamos tener una discusión ahora, si una matriz sigue siendo primitiva, o de hecho, podría discutir si un entero no es ya una estructura de datos. De cualquier manera, los algoritmos que existen completamente sin estructuras de datos son bastante aburridos, incluso si acepta su existencia aislada.

Algoritmos combinados con estructuras de datos, también conocidos como tipos de datos abstractos.

Ahora estos son los interesantes, pero por dos razones muy diferentes. Por lo general, puede abordarlos desde dos direcciones: primero la estructura de datos o el algoritmo primero.

Si bien un tipo de datos abstractos se define por la combinación de estructura de datos + algoritmos / operaciones, a menudo los vemos con un enfoque en cualquiera de ellos y consideramos el otro como habilitadores.

Estructura de datos, luego algoritmo

Encontrará tipos de datos abstractos, que son bastante simples de usar, pero involucran algoritmos más o menos complicados para que funcionen internamente. Por ejemplo, a HashMapes trivial de usar, pero implica una función hash ingeniosa y se ocupa de las colisiones hash en el interior. Sin embargo, desde su punto de vista como usuario, le importa como algo que contiene datos para usted, no algo que haga algo por usted.

A diferencia del último grupo a continuación, estas estructuras de datos no exponen a sus usuarios a estos algoritmos. No necesita saber ni preocuparse por HashMapla función interna de hash para poder usarla. (Sin embargo, para usarlo de manera efectiva, es posible que desee saber estas cosas;)

Algoritmo, luego estructura de datos

La otra dirección significa que tiene un algoritmo, que desea poder usar simplemente, pero que necesita estructuras de datos internamente para que funcione como se esperaba. Un ejemplo sería un algoritmo de particionamiento de espacio binario (BSP), que simplemente puede solicitar el bidimensional Pointde un gran conjunto de puntos que está más cerca de un punto de consulta dado. Sin embargo, necesita una estructura de árbol (e incluso algoritmos adicionales como cálculos de distancia) en el interior para escribir realmente el algoritmo.

En general, se puede decir que los algoritmos en este grupo usan estructuras de datos involucradas para su representación interna del estado. Yo diría que este grupo de algoritmos es el más diverso y encontrará muchos muchos diferentes que se ajustan a este esquema general. Con respecto al punto de vista, los vemos interesantes, porque hacen algo (por ejemplo, clasificación) por nosotros y no nos importa tanto la parte que contiene los datos.

Estructuras de datos y algoritmos estrechamente relacionados.

Finalmente, tiene estructuras de datos, que están muy relacionadas con algoritmos que se corresponden directamente con ellas. Un ejemplo típico es un árbol binario, que, cuando desea hacer algo significativo con él, le impone el tema de los algoritmos de caminar por el árbol (primero en profundidad, primero en amplitud, lo que sea).

Para estos casos, cambiamos de vez en cuando el enfoque de nuestra visión de los tipos de datos abstractos resultantes. A veces te importa la estructura de tu árbol, unos minutos más tarde te importa poder ejecutar una operación de búsqueda en él, luego te preguntas sobre eliminar un nodo y enseguida cómo se ve la estructura después. Si bien todo esto también es válido para las otras secciones anteriores, no es algo que sea el foco principal en su mente, por ejemplo, cuando almacena / recupera datos a / desde una Map, o cuando ordena una lista vinculada.

Las estructuras de datos a menudo influyen en los detalles de un algoritmo. Debido a esto, los dos a menudo van de la mano.

Considere, por ejemplo, un algoritmo para cortar su césped. Es probable que la estructura real de su césped influya en cómo corta el césped. Si vive en una casa pequeña en un suburbio densamente poblado y su césped es solo un pequeño rectángulo de unos pocos metros cuadrados de área, probablemente preferiría cortar su césped con una segadora en lugar de un tractor / segadora. Si su césped involucra muchos acres de terreno plano de pradera, su preferencia puede ser la cortadora de césped en lugar de la segadora de empuje (aunque eventualmente cualquiera de ellas puede hacer el trabajo). Si su césped involucra acres de tierra con grandes áreas planas, pero algunas colinas pequeñas y varios árboles, puede desarrollar un algoritmo más interesante para cortar el césped que involucra tanto una cortadora de césped como una segadora de empuje, o alguna otra hierba Técnicas de corte.

Sin embargo, en última instancia, la estructura de sus datos puede tener un impacto significativo en sus decisiones sobre cómo desarrollar su algoritmo (o qué algoritmos usar). Por esta razón, los dos temas a menudo van de la mano.

Y viceversa: a veces el algoritmo que queremos usar influye (al menos al comienzo de la informática) en las estructuras de datos que desarrollas para admitir el algoritmo. Por ejemplo, pasar de una lista de matriz a la idea de una lista vinculada y, finalmente, a un BST para almacenar una lista ordenada que permita una búsqueda rápida.