Algoritmos

Un algoritmo describe una serie de pasos que se utilizan para resolver alguna clase de problemas (p.e. ordenar una lista) o realizar una tarea específica.

Un algoritmo puede ser ejecutado por personas o computadores, pero en esta sección nos vamos a concentrar en algoritmos que van a ser ejecutados por computadores (obviamente).

Para crear y utilizar algoritmos que van a ser ejecutados por computadores debes conocer conceptos como tipos de datos (cadenas de texto, números, booleanos, etc.), variables, condicionales, ciclos y algunas estructuras de datos como arreglos y diccionarios (llamados hashes en Ruby y objetos en JavaScript).

Un algoritmo se puede expresar de diferentes formas: en palabras, en pseudocódigo o en un lenguaje de programación como Ruby, JavaScript, Python, etc.

Un algoritmo está compuesto de unos datos de entrada, las instrucciones que se deben ejecutar y el resultado esperado.

Lo más importante de un algoritmo es que sea correcto, es decir, que genere el resultado que esperamos. Sin embargo, probar que un algoritmo es correcto es difícil, así que lo que recomendamos es crear pruebas automatizadas que cubran la mayoría de los casos.

Por otro lado, el rendimiento de un algoritmo también es importante y para eso vamos a explicar cómo calcular la complejidad de un algoritmo utilizando la notación Big-O.

Además de arreglos y diccionarios, vamos a ver otras estructuras de datos como matrices, listas encadenadas (linked lists), árboles, grafos, colas (queues) y pilas (stacks). Muchos algoritmos dependen de estas estructuras de datos específicas. Por ejemplo, encontrar la ruta más corta es más fácil utilizando un grafo.

Existen varias clases de algoritmos e identificar a cuál clase pertenece un problema es un primer paso. Algunas clases son:

  • Ordenamiento de listas (p.e. ordenar una lista de números en un arreglo)

  • Búsqueda en listas (p.e. encontrar un número dentro de un arreglo)

  • Grafos (p.e. encontrar la ruta más corta entre dos ciudades)

  • Programación dinámica

  • Conjuntos y cadenas (p.e. criptografía)

Para cada una de estas clases existen varios algoritmos que debemos conocer y aprender a utilizar para resolver diversos problemas.

Prerequisitos

Contenido