1. Sejam bem-vindas e bem-vindos

Esse livro eletrônico foi escrito para dar suporte às aulas da disciplina Princípios de Desenvolvimento de Algoritmos. Desde 2015, temos utilizado a linguagem Python. Esse livro na verdade é uma continuação de nosso livro Introdução à Computação com Python, e por isso esse curso pode ser considerado a parte II do curso de introdução.

A metodologia de ensino que adotamos é orientada a problemas, ao invés, por exemplo, de ser orientada à linguagem. Acreditamos que dessa forma os alunos e alunas consigam continuar a desenvolver suas habilidades para resolver problemas computacionais e aplicá-las depois a outros domínios e/ou utilizando diferentes linguagens de programação.

Cada problema tem o objetivo de familiarizar os estudantes com ideias e conceitos práticos de utilização de estruturas de dados e algoritmos amplamente utilizados no processo da resolução de problemas computacionais.

1.1. Pré-requisitos

A disciplina “Princípios de Desenvolvimento de Algoritmos com Python” é de nível intermediário e exige certos conceitos e habilidades básicas de programação e pensamento computacional que são desenvolvidos em disciplinas de introdutórias como, por exemplo, Introdução à Computação com Python.

O material dessa disciplina utiliza a linguagem de programação Python. Se sua experiência anterior em programação não é com Python, mas com outra linguagem de programação como C, C++ ou Java, não se preocupe. O fundamental é ter familiaridade com:

• variáveis;
• operador de atribuição: =;
• execução condicional, alternativa e em cadeia: if, if-else e if-elif-else;
• comandos de repetição: while e for;
• operadores relacionais: ==, !=, <, >, <=, >=;
• operadores lógicos: and, or e not;
• funções: def ...; e
• estruturas indexadas: vetores, matrizes, listas.

Durante o andamento da disciplina, vários desses conceitos serão revistos. Para reforçá-los sugerimos a consulta frequente ao material da disciplina Introdução à Computação com Python.

1.2. Objetivos

O principal objetivo dessa disciplina é continuar a desenvolver suas habilidades de resolução de problemas computacionais. Acreditamos que essas habilidades sejam fundamentais no dia a dia de um profissional de ciências ou engenharia. Para isso vamos continuar evoluindo o raciocínio aplicado na formulação e resolução de problemas computacionais.

Um pouco mais detalhadamente, essa disciplina pretende fazer com que os estudantes:

• entendam o papel da abstração no processo de resolução de problemas;
• implementem e tenham a noção de tipos abstratos de dados (classes);
• entendam os tipos abstratos de dados pilha, fila, array e lista;
• entendam a importância de algoritmos;
• sejam capazes de estimar o consumo de tempo de algoritmos;
• entendam como a implementação e representação de dados impactam no desempenho (= consumo de tempo e espaço) de algoritmos;
• sejam capazes de explicar e de implementar buscas sequenciais e binária;
• sejam capazes de explicar e de implementar vários algoritmos de ordenação;
• entendam a ideia de hashing como técnica de busca;
• entendam como problemas complexos podem admitir soluções recursivas simples;
• implementem funções recursivas;
• entendam como recursão é implementada por um sistema computacional;
• sejam capazes de realizar análises experimentais simples (bechmark) de programas; e
• sejam capazes de estimar o desempenho de algoritmos através de notação assintótica (“O-grande”).

1.3. Estrutura

Para facilitar a sincronia entre aulas, conteúdos e atividades, esse livro está organizado em vários capítulos curtos que apresentam conceitos a serem trabalhados em cada aula na forma de exercícios práticos e, ao final de cada capítulo, propomos também uma série de exercícios para você treinar e continuar a se desenvolver.

Boa parte das atividades práticas realizadas em sala de aula são baseadas nessa série final de exercícios e que também servem de ponte para a introdução de outros tópicos.

1.4. Bibliografia

Além dessas notas de aula recomendamos também a consulta dos seguintes materiais:

• Problem Solving with Algorithms and Data Structures, por Brad Miller e David Ranum;
• Projeto de Algoritmos em C por Paulo Feofiloff; e
• Algoritmos em linguagem C por Paulo Feofiloff.

Apesar de alguns desses materiais utilizarem a linguagem C, eles são excelentes referências para complementar vários conceitos que veremos. Como a sintaxe da linguagem C é muito próxima à Python, o entendimento dos algoritmos não deve ficar prejudicada.

Muito do material encontrado nessas notas de aulas são resumos, adaptações e traduções de tópicos encontrados nesses livros.

1.5. Reconhecimentos

Esse livro interativo utiliza as seguintes ferramentas:

• Skulpt: um implementação do Python que é executada dentro de navegadores da Internet;
• Trinket.io: que permite usar o Skulpt de forma interativa no próprio navegador.
• Python Tutor: nos permite simular, passo a passo, programas em Python.
• Sphinx: esse texto foi escrito no formato RST (reStructured Text) e compilado para HTML usando Sphinx.

São Paulo, agosto de 2022.

Coelho e Hitoshi