Muitas tarefas no campo da Ciência da Computação, que à primeira vista parecem novas ou únicas, estão realmente enraizadas em algoritmos clássicos, métodos de codificação e princípios de desenvolvimento. E técnicas estabelecidas ainda são a melhor maneira de resolver esses problemas!
O livro lhe dará a oportunidade de aprender mais profundamente a linguagem Python, testar-se em tarefas, exercícios e algoritmos testados pelo tempo. Você precisa resolver dezenas de tarefas de programação: das mais simples (por exemplo, localizar itens da lista usando classificação binária) às complexas (agrupar dados usando o método k-means). Trabalhando com exemplos dedicados à pesquisa, agrupamento, gráficos, etc., você se lembrará do que havia esquecido e dominará as técnicas clássicas para resolver problemas do dia a dia.
Para quem é este livro?
Este livro é destinado a programadores de nível médio e alto. Profissionais experientes que desejam aprofundar seus conhecimentos sobre Python encontrarão aqui tarefas familiares desde o momento em que ensinaram ciência da computação ou programação. Programadores de nível intermediário se familiarizarão com essas tarefas clássicas na linguagem escolhida - Python. Para desenvolvedores que estão se preparando para uma entrevista de programação, é provável que a publicação se torne um material preparatório valioso.
Além de programadores profissionais, este livro pode ser considerado útil por estudantes de graduação em ciências da computação e interessados em Python. Não afirma ser uma introdução rigorosa às estruturas e algoritmos de dados. Este não é um tutorial sobre estruturas de dados e algoritmos. Você não encontrará provas de teoremas ou o uso abundante de O grandes notações em suas páginas. Pelo contrário, este livro está posicionado como um guia prático acessível para métodos de solução de problemas que devem se tornar o produto final do estudo da estrutura de dados, algoritmos e classes de inteligência artificial.
Enfatizo novamente: presume-se que os leitores estejam familiarizados com a sintaxe e a semântica do Python. É improvável que um leitor com experiência em programação zero se beneficie deste livro, e um programador com experiência em Python provavelmente será difícil. Em outras palavras, "Tarefas clássicas de ciência da computação em Python" é um livro para programadores e estudantes de ciência da computação.
Trecho. 1.5 Torres de Hanói
Existem três colunas verticais altas (a seguir, torres). Nós os designaremos A, B e C. Discos com orifícios no centro estão amarrados na torre A. O disco mais largo - o qual chamaremos de disco 1 - está localizado abaixo. Os discos restantes localizados acima dele são indicados por números crescentes e diminuem gradualmente. Por exemplo, se tivéssemos três discos, o mais largo, o abaixo, teria o número 1. O próximo disco mais largo, no número 2, estaria localizado acima do disco 1. Por fim, o disco mais estreito, no número 3 ficaria no disco 2.
Nosso objetivo é mover todas as unidades da torre A para a torre C, levando em consideração as seguintes restrições.
- Os discos podem ser movidos apenas um de cada vez.
- A única unidade disponível para movimentação é aquela localizada no topo de qualquer torre.
- Uma unidade mais ampla nunca pode ser colocada em cima de uma unidade mais estreita.
Esquematicamente, a tarefa é mostrada na Fig. 1.7
1.5.1 Modelagem de Torres
Uma pilha é uma estrutura de dados modelada com base no princípio LIFO (last-in-first-out). A última coisa que entra na pilha se torna a primeira que é buscada a partir daí. As duas operações principais da pilha são push (colocar) e pop (extrair). A operação de envio empurra um novo item para a pilha, e o pop remove-o da pilha e retorna o último item inserido. Você pode modelar facilmente a pilha no Python usando a lista como armazenamento de backup (Listagem 1.20).
Listagem 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)
A classe Stack apresentada implementa o método __repr __ (), que facilita o exame do conteúdo da torre. __repr __ () é o que será produzido quando a função print () for aplicada à pilha.
Conforme declarado na introdução, as anotações de tipo são usadas no livro. A importação de Genérico de um módulo de entrada permite que o Stack seja uma classe paramétrica para um tipo específico nas anotações de tipo. Um tipo arbitrário T é definido em T = TypeVar ('T'). T pode ser de qualquer tipo. Quando a anotação de tipo for usada posteriormente para Stack na solução do problema da torre de Hanói, o prompt será Stack [int], ou seja, o tipo int será usado em vez de T. Em outras palavras, aqui a pilha é uma pilha de números inteiros. Se você estiver tendo dificuldades com as anotações de tipo, dê uma olhada no Apêndice B.
As pilhas são perfeitas para o desafio da torre de Hanói. Para mover o disco para a torre, podemos usar a operação push. Para mover o disco de uma torre para outra, podemos empurrá-lo da primeira (pop) e colocá-lo na segunda (push).
Defina as torres como objetos Stack e preencha a primeira com discos (Listagem 1.21).
Listagem 1.21. hanoi.py (continuação)
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 Resolvendo o problema das torres de Hanói
Como posso resolver o problema das torres de Hanói? Suponha que estamos tentando mover apenas uma unidade. Então saberíamos como fazer isso, certo? De fato, mover um disco é um caso básico para uma solução recursiva para esse problema. Mover várias unidades é um caso recursivo. O ponto principal é que, de fato, temos dois cenários que precisam ser codificados: mover um disco (caso base) e mover vários discos (caso recursivo).
Para entender o caso recursivo, considere um exemplo específico. Suponha que temos três discos - superior, médio e inferior, localizados na torre A, e queremos movê-los para a torre C. (Posteriormente, isso ajudará a descrever esquematicamente o problema.) Primeiro, podemos mover o disco superior para a torre C. Em seguida - mova o disco do meio para a torre B e, em seguida, o disco superior da torre C para a torre B. Agora temos o disco inferior ainda localizado na torre A e os dois discos superiores na torre B. Basicamente, já movemos com êxito dois dirija de uma torre (A) para outra (B). Mover o disco inferior de A para C é o caso básico (mover um disco). Agora podemos mover os dois discos superiores de B para C usando o mesmo procedimento de A para B. Movemos o disco superior para A, o disco do meio para C e, finalmente, o disco superior de A para C.
Nas aulas de ciência da computação, pequenos modelos dessas torres são frequentemente encontrados, construídos a partir de pinos e discos de plástico. Você pode fazer seu próprio modelo com três lápis e três folhas de papel. Talvez isso ajude você a visualizar a solução.
No exemplo com três discos, houve um caso básico simples de mover um disco e um caso recursivo de mover os discos restantes (neste caso dois) usando uma terceira torre temporária. Podemos dividir o caso recursivo nas seguintes etapas.
- Mova as unidades n - 1 superiores da torre A para a torre B (temporária), usando C como torre intermediária.
- Mova a unidade inferior de A para C.
- Mova os discos n - 1 da torre B para a torre C, a torre A é intermediária.
Surpreendentemente, esse algoritmo recursivo funciona não apenas para três, mas para qualquer número de discos. Codifique-a como uma função hanoi (), responsável por mover os discos de uma torre para outra usando uma terceira torre temporária (Listagem 1.22).
Listagem 1.22. hanoi.py (continuação)
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)
Após chamar hanoi (), é necessário verificar as torres A, B e C para garantir que os discos foram movidos com sucesso (Listagem 1.23).
Listagem 1.23. hanoi.py (continuação)
if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c)
Você descobrirá que as unidades foram realmente movidas. Ao codificar a solução para o problema da torre de Hanói, não é necessário entender todas as etapas necessárias para mover vários discos da torre A para a torre C. Chegamos a entender o algoritmo recursivo geral para mover qualquer número de discos e sistematizá-lo, permitindo que o computador faça o resto. Esse é o poder de formular soluções recursivas para problemas: geralmente podemos imaginar soluções abstratas, sem desperdiçar energia na representação mental de cada ação individual.
A propósito, a função hanoi () será executada exponencialmente, dependendo do número de discos, o que torna a solução para o problema mesmo para 64 discos inadequados. Você pode tentar executá-lo com um número diferente de discos alterando a variável num_discs. À medida que o número de discos aumenta, o número de etapas para concluir a tarefa da torre de Hanói aumenta exponencialmente; mais detalhes podem ser encontrados em muitas fontes. Se você estiver interessado em aprender mais sobre a matemática por trás da solução recursiva desse problema, consulte a explicação de Karl Birch no artigo
“On Hanoi Towers” .
1.6 Aplicações reais
Os vários métodos apresentados neste capítulo (recursão, memorização, compactação e manipulação no nível de bits) são tão difundidos no desenvolvimento de softwares modernos que, sem eles, é impossível imaginar o mundo da computação. Apesar do fato de que as tarefas podem ser resolvidas sem elas, geralmente é mais lógico ou conveniente resolvê-las usando esses métodos.
Em particular, a recursão está subjacente não apenas a muitos algoritmos, mas também a linguagens de programação inteiras. Em algumas linguagens de programação funcionais, como Scheme e Haskell, a recursão substitui os loops usados em linguagens imperativas. No entanto, deve-se lembrar que tudo o que pode ser alcançado usando o método recursivo também pode ser executado iterativamente.
A memorização foi usada com sucesso para acelerar o trabalho dos analisadores - programas que interpretam linguagens. Isso é útil em todas as tarefas em que é provável que o resultado de um cálculo recente seja solicitado novamente. Outra área de ação para memorização é o tempo de execução da linguagem de programação. Alguns desses tempos de execução, por exemplo, para a versão do Prolog, salvam automaticamente os resultados das chamadas de função (auto-mash), para que a função não precise ser executada na próxima vez com a mesma chamada. Isso é semelhante ao decorador @lru_cache () em fib6 ().
A compressão tornou o mundo da Internet, com sua largura de banda limitada, mais suportável. O método de cadeia de bits discutido na Seção 1.2 é aplicável a tipos de dados simples no mundo real que possuem um número limitado de valores possíveis, para os quais até 1 byte é redundante. No entanto, a maioria dos algoritmos de compactação trabalha procurando padrões ou estruturas em um conjunto de dados que eliminam informações duplicadas. Eles são muito mais complicados do que o descrito na seção 1.2.
Cifras descartáveis não são adequadas para casos de criptografia geral. Eles exigem que o codificador e o decodificador possuam uma das chaves (dados simulados em nosso exemplo) para restaurar os dados originais, o que é muito complicado e na maioria dos esquemas de criptografia não permite atingir o objetivo de manter as chaves em segredo. Mas você pode estar interessado em saber que o nome “cifra descartável” foi inventado por espiões que durante a Guerra Fria usaram cadernos de papel reais com dados fictícios gravados neles para criar mensagens criptografadas.
Esses métodos são os blocos de construção dos programas, outros algoritmos são baseados neles. Nos capítulos seguintes, você verá o quão amplamente eles são aplicados.
Sobre o autor
David Kopec é professor sênior de ciência da computação e inovação no Champlain College em Burlington, Vermont. Ele é um desenvolvedor de software experiente e autor de Classic Computer Science Problems in Swift (Manning, 2018) e Dart for Absolute Beginners (Apress, 2014). David obteve um diploma de bacharel em economia e um mestrado em ciência da computação pelo Dartmouth College. Você pode entrar em contato com ele no Twitter por @davekopec.
»Mais informações sobre o livro podem ser encontradas no
site do editor»
Conteúdo»
TrechoCupom de 25% de desconto para vendedores ambulantes -
PythonApós o pagamento da versão impressa do livro, um livro eletrônico é enviado por e-mail.