Muchas tareas en el campo de la informática, que a primera vista parecen nuevas o únicas, se basan en algoritmos clásicos, métodos de codificación y principios de desarrollo. ¡Y las técnicas establecidas siguen siendo la mejor manera de resolver tales problemas!
El libro le dará la oportunidad de dominar mejor el lenguaje Python, ponerse a prueba en tareas, ejercicios y algoritmos probados por el tiempo. Tiene que resolver docenas de tareas de programación: desde las más simples (por ejemplo, encontrar elementos de la lista usando la ordenación binaria) hasta las complejas (agrupar datos usando el método k-means). Al trabajar con ejemplos de búsqueda, agrupación, gráficos, etc., recordará lo que ha olvidado y dominará las técnicas clásicas para resolver problemas cotidianos.
¿Para quién es este libro?
Este libro está destinado a programadores de nivel medio y alto. Los profesionales experimentados que desean profundizar su conocimiento de Python encontrarán aquí tareas que les son familiares desde el momento en que enseñaron informática o programación. Los programadores de nivel medio se familiarizarán con estas tareas clásicas en su lenguaje elegido: Python. Para los desarrolladores que se están preparando para una entrevista de programación, es probable que la publicación se convierta en un valioso material preparatorio.
Además de los programadores profesionales, este libro puede ser considerado útil por los estudiantes que estudian para programas de pregrado en informática y están interesados en Python. No pretende ser una introducción rigurosa a las estructuras de datos y algoritmos. Este no es un tutorial sobre estructuras de datos y algoritmos. No encontrará pruebas de teoremas o el uso abundante de O grandes anotaciones en sus páginas. Por el contrario, este libro se posiciona como una guía práctica accesible de métodos para resolver problemas que deberían convertirse en el producto final del estudio de la estructura de datos, algoritmos y clases de inteligencia artificial.
Lo enfatizo nuevamente: se supone que los lectores están familiarizados con la sintaxis y la semántica de Python. Es poco probable que un lector con experiencia en programación cero se beneficie de este libro, y un programador con experiencia cero en Python probablemente será difícil. En otras palabras, "Tareas de informática clásica en Python" es un libro para programadores de Python y estudiantes de informática.
Extracto 1.5. Torres de hanoi
Hay tres columnas verticales altas (en adelante, torres). Los designaremos A, B y C. Los discos con agujeros en el centro están encadenados en la torre A. El disco más ancho, lo llamaremos disco 1, se encuentra debajo. Los discos restantes ubicados encima están indicados por números crecientes y se van reduciendo gradualmente. Por ejemplo, si tuviéramos tres discos, el más ancho de ellos, el de abajo, tendría el número 1. El siguiente disco más ancho, en el número 2, se ubicaría sobre el disco 1. Finalmente, el disco más estrecho, en el número 3 estaría en el disco 2.
Nuestro objetivo es mover todas las unidades desde la torre A a la torre C, teniendo en cuenta las siguientes restricciones.
- Los discos solo se pueden mover de uno en uno.
- La única unidad disponible para moverse es la que se encuentra en la parte superior de cualquier torre.
- Una unidad más ancha nunca se puede colocar encima de una más estrecha.
Esquemáticamente, la tarea se muestra en la Fig. 1.7.
1.5.1. Modelado de torres
Una pila es una estructura de datos modelada según el principio de último en entrar, primero en salir (LIFO). Lo último que se pone en la pila se convierte en el primero que se obtiene de allí. Las dos operaciones principales de la pila son push (put) y pop (extract). La operación de inserción empuja un nuevo elemento a la pila, y pop lo elimina de la pila y devuelve el último elemento insertado. Puede modelar fácilmente la pila en Python usando la lista como almacenamiento de respaldo (Listado 1.20).
Listado 1.20. hanoi.py
from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container)
La clase Stack presentada implementa el método __repr __ (), que facilita el examen del contenido de la torre. __repr __ () es lo que se generará cuando la función print () se aplique a la pila.
Como se indicó en la introducción, las anotaciones de tipo se utilizan en el libro. La importación de genéricos desde un módulo de entrada permite que Stack sea una clase paramétrica para un tipo específico en anotaciones de tipo. Un tipo arbitrario T se define en T = TypeVar ('T'). T puede ser de cualquier tipo. Cuando la anotación de tipo se usa posteriormente para Stack para resolver el problema de la torre de Hanoi, la solicitud será Stack [int], es decir, se usará el tipo int en lugar de T. En otras palabras, aquí la pila es una pila de enteros. Si tiene dificultades con las anotaciones de tipo, consulte el Apéndice B.
Las pilas son perfectas para el desafío de la torre de Hanoi. Para mover el disco a la torre, podemos usar la operación de empuje. Para mover el disco de una torre a otra, podemos empujarlo desde la primera (pop) y colocarlo en la segunda (push).
Defina las torres como objetos de Pila y llene la primera con discos (Listado 1.21).
Listado 1.21. hanoi.py (continuación)
num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i)
1.5.2. Resolviendo el problema de las Torres de Hanoi
¿Cómo puedo resolver el problema de las torres de Hanoi? Supongamos que estamos tratando de mover solo una unidad. Entonces sabríamos cómo hacer esto, ¿verdad? De hecho, mover un disco es un caso básico para una solución recursiva a este problema. Mover varias unidades es un caso recursivo. El punto clave es que, de hecho, tenemos dos escenarios que necesitan ser codificados: mover un disco (caso base) y mover varios discos (caso recursivo).
Para entender el caso recursivo, considere un ejemplo específico. Supongamos que tenemos tres discos: el superior, el medio y el inferior, ubicados en la torre A, y queremos moverlos a la torre C. (Posteriormente, esto ayudará a describir esquemáticamente el problema). Primero podríamos mover el disco superior a la torre C. Luego, - mueva el disco del medio a la torre B, y luego el disco superior de la torre C a la torre B. Ahora tenemos el disco inferior todavía ubicado en la torre A y los dos discos superiores en la torre B. Esencialmente, ya hemos movido con éxito dos conducir de una torre (A) a otra (B). Mover el disco inferior de A a C es el caso básico (mover un disco). Ahora podemos mover los dos discos superiores de B a C usando el mismo procedimiento que de A a B. Movimos el disco superior a A, el disco del medio a C y finalmente el disco superior de A a C.
En las clases de ciencias de la computación, a menudo se encuentran modelos pequeños de estas torres, construidas con alfileres y discos de plástico. Puedes hacer tu propio modelo con tres lápices y tres hojas de papel. Quizás esto lo ayude a visualizar la solución.
En el ejemplo con tres discos, hubo un caso básico simple de mover un disco y un caso recursivo de mover los discos restantes (en este caso dos) usando una tercera torre temporal. Podemos dividir el caso recursivo en los siguientes pasos.
- Mueva las unidades n - 1 superiores de la torre A a la torre B (temporal), utilizando C como torre intermedia.
- Mueva la unidad inferior de A a C.
- Mueva n - 1 discos de la torre B a la torre C, la torre A es intermedia.
Sorprendentemente, este algoritmo recursivo funciona no solo para tres, sino para cualquier cantidad de discos. Codifíquelo como una función hanoi (), que es responsable de mover discos de una torre a otra utilizando una tercera torre temporal (Listado 1.22).
Listado 1.22. hanoi.py (continuación)
def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1)
Después de llamar a hanoi (), debe verificar las torres A, B y C para asegurarse de que los discos se hayan movido correctamente (Listado 1.23).
Listado 1.23. hanoi.py (continuación)
if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c)
Verá que las unidades se han movido. Al codificar la solución al problema de la torre de Hanoi, no es necesario comprender todos los pasos necesarios para mover varios discos de la torre A a la torre C. Llegamos a comprender el algoritmo recursivo general para mover cualquier número de discos y lo sistematizamos, permitiendo que la computadora haga el resto. Este es el poder de formular soluciones recursivas a los problemas: a menudo podemos imaginar soluciones en abstracto, sin desperdiciar energía en la representación mental de cada acción individual.
Por cierto, la función hanoi () se ejecutará exponencialmente dependiendo del número de discos, lo que hace que la solución del problema incluso para 64 discos no sea adecuada. Puede intentar ejecutarlo con un número diferente de discos cambiando la variable num_discs. A medida que aumenta el número de discos, el número de pasos para completar la tarea de la torre de Hanoi crece exponencialmente; se pueden encontrar más detalles en muchas fuentes. Si está interesado en aprender más sobre las matemáticas detrás de la solución recursiva de este problema, vea la explicación de Karl Birch en el artículo
"Sobre las Torres de Hanoi" .
1.6. Aplicaciones reales
Los diversos métodos presentados en este capítulo (recursión, memorización, compresión y manipulación a nivel de bits) están tan extendidos en el desarrollo de software moderno que sin ellos es imposible imaginar el mundo de la informática. A pesar de que las tareas pueden resolverse sin ellas, a menudo es más lógico o conveniente resolverlas utilizando estos métodos.
En particular, la recursión subyace no solo en muchos algoritmos, sino incluso en lenguajes de programación completos. En algunos lenguajes de programación funcionales, como Scheme y Haskell, la recursión reemplaza los bucles utilizados en los lenguajes imperativos. Sin embargo, debe recordarse que todo lo que se puede lograr utilizando el método recursivo también se puede realizar de forma iterativa.
La memorización se ha utilizado con éxito para acelerar el trabajo de los analizadores sintácticos, programas que interpretan idiomas. Esto es útil en todas las tareas donde es probable que se solicite nuevamente el resultado de un cálculo reciente. Otra área de acción para la memorización es el tiempo de ejecución del lenguaje de programación. Algunos de estos tiempos de ejecución, por ejemplo, para la versión Prolog, guardan automáticamente los resultados de las llamadas a funciones (auto-mash), por lo que la función no tiene que ejecutarse la próxima vez con la misma llamada. Esto es similar al decorador @lru_cache () en fib6 ().
La compresión ha hecho que el mundo de Internet, con su ancho de banda limitado, sea más soportable. El método de cadena de bits discutido en la Sección 1.2 es aplicable a tipos de datos simples en el mundo real que tienen un número limitado de valores posibles, para los cuales incluso 1 byte es redundante. Sin embargo, la mayoría de los algoritmos de compresión funcionan buscando patrones o estructuras en un conjunto de datos que eliminan la información duplicada. Son mucho más complicados que los descritos en la sección 1.2.
Los cifrados desechables no son adecuados para casos generales de cifrado. Requieren que tanto el codificador como el decodificador tengan una de las claves (datos ficticios en nuestro ejemplo) para restaurar los datos originales, lo cual es demasiado engorroso y en la mayoría de los esquemas de cifrado no permite alcanzar el objetivo de mantener las claves en secreto. Pero puede interesarle saber que el nombre de "cifrado desechable" fue inventado por espías que durante la Guerra Fría utilizaron cuadernos de papel reales con datos ficticios grabados en ellos para crear mensajes cifrados.
Estos métodos son los componentes básicos de los programas; otros algoritmos se basan en ellos. En los siguientes capítulos verá cuán ampliamente se aplican.
Sobre el autor
David Kopec es profesor titular de informática e innovación en el Champlain College en Burlington, Vermont. Es un desarrollador de software experimentado y autor de Classic Computer Science Problems in Swift (Manning, 2018) y Dart for Absolute Beginners (Apress, 2014). David obtuvo una licenciatura en economía y una maestría en informática del Dartmouth College. Puede contactarlo en Twitter por @davekopec.
»Se puede encontrar más información sobre el libro en
el sitio web del editor»
Contenidos»
ExtractoCupón de 25% de descuento para vendedores ambulantes -
PythonTras el pago de la versión en papel del libro, se envía un libro electrónico por correo electrónico.