Departamento de Ciência da Computação - IME - USP

MAC0122 Princípios de Desenvolvimento de Algoritmos

In Pursuit of Simplicity

Bem-vind@ à MAC0122 Princípios de Desenvolvimento de Algoritmos. A disciplina MAC0122 é de responsabilidade do Departamento de Ciência da Computação (DCC) do Instituto de Matemática e Estatística (IME) da Universidade de São Paulo (USP) e é oferecida no segundo semestre de cada ano aos ingressantes dos Bacharelados em Estatística, em Matemática e em Matemática Aplicada. Esta edição de MAC0122 é de responsabilidade de

Capella		Hitoshi	Coelho

A seguir está uma descrição de alguns dos ingredientes principais de MAC0122.

Introdução

Programas de computador armazenam, acessam e manipulam dados. Programas são uma formulação concreta de algoritmos baseados em uma representação particular dos dados. Muito do que é feito em várias áreas da ciência da computaçaõo, tais como compiladores, computação gráfica, sistemas operacionais, . . ., é buscar maneiras de representar os dados para que o armazenamento, acesso e manipulação destes seja feito de maneira eficiente, ou seja, consumindo pouco tempo e espaço. Sempre que representamos dados no computador consideramos cada um dos seguintes aspectos:

1. a maneira que os dados são modeladas (= classes);
2. o conjunto de operações definidas sobre estes dados (= métodos);
3. a maneira de armazenar os dados (= representação dos objetos);
4. os algoritmos usados para manipular os dados.
5. Apesar dos termos tipo de dados, tipo abstrato de dados e estrutura de dados parecerem semelhantes eles têm significados diferentes. O tipo de dado de uma variável é o conjunto de valores que ela pode assumir. Por exemplo, uma variável do tipo bool pode assumir os valores True e False.

Os itens 1 e 2 acima dizem respeito ao tipo abstrato de dados, ou seja, ao modelo junto com uma coleção de operações difinidas sobre os dados. Um exemplo de tipo abstrado de dados é o conjunto dos números racionais com as operações de soma, subtração, multiplicação e divisão. No contexto de orientação a objetos os tipos abstratos de dados são chamados de classes e as operações sobre os dados ou objetos são chamadas de métodos.

Já os itens 3 e 4 estão relacionados a aspectos de implementação. Para representar um tipo abstrato de dados em um computador usamos uma estrutura de dados, que é uma coleção de variáveis, possivelmente de diferentes tipos, relacionadas de diversas maneiras. Em programação orientada a objetos essa coleção de variáveis recebe o nome de atributos de estado.

Objetivos

O objetivo principal de MAC0122 é desenvolver um raciocínio aplicado na formulação e resolução de problemas computacionais, ensinar como abordar e resolver problemas computacionais.

Em MAC0122 estudaremos, através de exemplos, a correção, a análise de eficiência e projeto de algoritmos muito bacanas e que são amplamento utilizados por programadores.

Veremos alguns tipos abstratos de dados (ou classes) básicos e algumas estruturas de dados elementares para armazenar estes dados juntamente com os algoritmos para manipular estas estruturas. Existem várias estruturas de dados para um mesmo tipo abstrato de dados e em geral não existe uma estrutura de dados que é a melhor para todas as circunstâncias.

Os algoritmos e estruturas de dados que veremos em MAC0122 nasceram de aplicações cotidianas em ciência da computação. Novas aplicações irão requerer a criação de novos algoritmos e estruturas de dados. É pretenção desta disciplina fornecer aos estudantes elementos e técnicas que possam auxiliá-los a escrever bons algoritmos e estruturas de dados.

Programmers Life

Fonte: https://www.hongkiat.com/blog/programming-jokes/

Pré-requisitos

Para esta disciplina o pré-requisito é o conhecimento de técnicas básicas de programação que são vistas em disciplinas de Introdução à Computação como MAC0110, MAC0115 ou MAC2166. Alguns do pré-requisitos estão no livro Como Pensar como um Cientista da Computação - Aprendendo com Python: Edição interativa que é uma tradução do livro How to Think Like a Computer Scientist - Learning with Python: Interactive Edition.

Principais tópicos

MAC0122 estuda algoritmos para alguns problemas computacionais básicos. Isso serve de motivação para introduzir vários conceitos e idéias importantes. Alguns dos tópicos de MAC0122 são:

• Recursão: problemas de difícil resolução podem admitir soluções recursivas simples; como formular programas recursivos; entender recursão como uma forma de iteração; implementar uma formulações recursivas de problemas;...
• Estruturas de dados básicas: tipos de dados básicos como pilhas, filas e listas. implementação de pilhas, filas; desempenho de implementações básicas de estruturas de dados lineares; uso de pilhas para calcular o valor de uma expressão posfixa; uso de pilhas para converter um expressão infixa para posfixa; uso de filas para simulações básicas;...
• Análise de algoritmos: importância da análise de algoritmos; noções de notação assintótica para representar o consumo de tempo de algoritmos; como a implementação impacta o consumo de tempo de um algoritmo;...
• Busca e ordenação: implementação de buscas sequênciais e binárias; implementação de vários algoritmos de ordenação; hashing; ... Tudo isso regado a muita análise de desempenho, invariantes e correção de algoritmos.

A bibliografia básica desta disciplina são as notas de aula e o livro Problem Solving with Algorithms and Data Structures.

Python no seu computador

Utilizaremos Python 3. Em MAC0122 evitamos o uso de linguagens e sistemas proprietários. Preferimos os sistemas abertos e livres (Free and open source software).

Baixe e instale a distribuição Python Anaconda. Anaconda é uma plataforma agnóstica, ou seja, pode ser usada no Windows, macOS ou Linux.

Usaremos o Spyder, que vem com a Anaconda, como Ambiente Integrado de Desenvolvimento (IDE = Integrated Development Environment). Spyder (Scientific PYthon Development EnviRonment) é um ambiente interativo de desenvolvimento muito poderoso para a linguagem Python. Spyder proporciona editoração avançada, testes interativos, depuração e um ambiente de computação numérica graças ao suporte de IPython (interactive Python interpreter) e bibliotecas populares de Python como NumPy (álgebra linear), SciPy (processamento de sinais e imagens) or matplotlib (desenhador 2D/3D interativo).

Você pode seguir essas instruções para instalar Python 3 em seu computador.

Nota: as instruções mais atualizadas para instalação da Anaconda podem ser encontradas no sítio oficial da Anaconda.

Plantão de dúvidas

Para auxiliá-lo, MAC0122 conta com o trabalho fundamental de monitores. Os monitores e os profs darão plantão de dúvidas em locais e horários divulgados na página de MAC0122 em Horários dos plantões de dúvidas

Avaliação

A nota final em MAC0122 é devida a vários componentes.

Exercícios-programa

Em MAC0122, os projetos que envolvem programação recebem o nome de exercícios-programa (EPs). Esta edição de MAC0122 terá vários EPs. A data de entrega e o enunciado de cada EP será divulgado ao longo do semestre na seção "Exercícios-programa". O enunciado de cada EP deverá ser rigorosamente observado.

A entrega dos EPs é feita eletronicamente. O depósito (upload) dos seus EPs será feito através da página de MAC0122, conforme descrito em Instruções para entrega de EPs em Python. Não são aceitos EPs fora do prazo de entrega. A correção dos EPs e suas notas também serão disponibilizadas na página de MAC0122.

O sistema permite que os EPs sejam ressubmetidos desde que dentro do prazo. Não há limite no número de submissões dentro do prazo. A nota atribuída a cada EP para fins de avaliação é a nota da última submissão.

Provinhas

Teremos várias provinhas ao longo do semestre durante o horário das aulas. Cada provinha consumirá cerca de 10 minutos da aula e valerá um certo número de pontos. A média Mp dessas provinhas será a aritmética.

Provas

Teremos 3 provas. A média MP das provas será

    MP = max((P1 + P2 + P3)/3, (PSub + P2 + P3)/3, (P1 + PSub + P3)/3, (P1 + P2 + PSub)/3)

onde, P1, P2 e P3 são as notas das três provas e PSub = Mp.

Nota final

A nota final; NF, será calculada pela regra
se min(MP, MEP) >= 5, então

    NF = 0.5*MP +  0.5*MEP, 

senão

    NF = min(MP, MEP). 

Aqueles e aquelas com NF >=5 estarão aprovados.

Recuperação

Aqueles e aquelas que obtiverem nota final NF maior ou igual a 3 e menor que 5 terão direito a fazer a recuperação. A recuperação consistirá de uma prova. Se Prec é a nota na prova de recuperação então a nota da recuperação NR, será calculada pela regra

    NR = (Prec + NF)/2, 

A condição para aprovação é NR >=5.

Experienced Programmer

Fonte: https://br.pinterest.com/pin/486599934709469290/

Conduta ética

As provas e os EPs de MAC0122 devem ser feitos individualmente. Você tem responsabilidade sobre cópias feitas de questões de suas provas e de trechos de seus EPs. Quando autores e copiadores combinam, estão ludibriando o sistema de avaliação, enganando o sistema e seus colegas. Provas e EPs considerados plagiados, tanto o original como a cópia, receberão nota zero e os nomes dos alunos envolvidos serão encaminhados aos órgãos responsáveis.

O trabalho em grupo e a cooperação entre colegas é em geral benéfico e útil ao aprendizado. Para ajudar um colega você pode lhe explicar como resolveu um ou outro problema. Por exemplo, pode explicar que para fazer um determinado trecho de programa é possível usar dois "loops" ou que para representar os dados basta usar algumas variáveis etc... O que você não deve fazer é mostrar o seu programa! Você pode achar que a amizade é mais importante do que as considerações éticas acima, mas mostrar o seu programa pode prejudicar o aprendizado do seu colega:

• depois de o seu colega ter visto o seu programa, será muito mais difícil para ele imaginar uma solução original;
• o seu colega não entenderá realmente o problema: a compreensão passa pela feitura dos programas e não pela imitação/cópia;
• vocês passarão por outras avaliações, na forma de provas; é impressionante como são diferentes as provas escritas por alunos que fizeram EPs e pelos que não fizeram, e as notas baixas desses últimos são inevitáveis.

Além disso, o seu colega pode eventualmente divulgar a sua solução para outros colegas, colocando-o numa situação muito complicada.

Esses problemas ocorrem em muitos lugares, e as políticas e recomendações não variam muito. Algumas recomendações da Universidade de Lisboa valem também aqui e foram reproduzidas no parágrafo anterior.

Matrícula

Verifique seu status no sistema Júpiter depois do período de retificação de matrículas. Seu status deve ser "MATRICULADO". Se for "PENDENTE" ou "INSCRITO", procure imediatamente o Serviço de Alunos de Graduação.