Ol[a Guilherme,

O que nós alunos podemos esperar da P1?

Para o BE, BM e BMAP há apenas uma MAC0122 com dois profs, o Hitoshi e eu. As provas, tarefas e critérios são iguais para ambas as turmas.

Você devem esperar tópicos relacionados aos que vocês tem feito nos programas. Em MAC0122, tipicamente, as questões para medir o grau de aprendizado são do tipo "Escreva uma função/programa que bla-blá-blá." Podemos sugerir vários exercícios que estão nas páginas do professor Paulo Feofiloff.

A seguir estão os tópicos que vimos até agora.

Tópicos das aulas 01 a 08

Noções de consumo de tempo e invariantes

• busca de palavras em um texto
• busca em uma lista ordenada: busca binária
• ordenação por troca (= bubblesort())
• ordenação por inserção
• ordenação por seleção
• ordenação por inserção binária
• consumo de tempo no pior caso e no melhor caso
• notação assintótica (= notação O-grande)

Recursão

• Raciocício recursivo: torres de hanoi
• Mecanismo da recursão: fatorial recursivo
• Exercício: problema do máximo
• Devemos evitar de resolver mesmo problema várias vezes: binomial recursivo

Python

• comando de repetição: while, for i in range()
• comando de seleção simples: if
• comando de seleção alternativa: if-else
• comando de seleção em cadeia: if-elif-...-else
• entrada: função input(),
• saída: funções print()
• esqueleto de um programa em Python
• marcadores: %d (= para int),%f (= para float), %s (= para str)
• operadores relacionais: <, <=, >, >=, ==, !=
• operadores lógicos: and, or, not
• classes nativas: int, float, bool, str, list, Nonetype
• valores da classe int são potencialmente ilimitados
• definição de funções: def f():
• funções de conversão de strings: int(), float()
• listas: indexação, percorrendo, comprimento (= função len()), criando (método .append())
• strings: indexação, percorrendo, comprimento (= função len()), criando (concatenação operador +)
• classe list versus classe str
• referências vesus clones

Bibliografia

A bibliografia básica são:

• notas de aula
• Projeto de Algoritmos em C, Paulo Feofiloff (PF)
• Problem Solving with Algorithms and Data Structures, Brad Miller and David Ranum (MR)

Notação assintótica: PF, MR, slides

Busca de palavras em um texto: PF, slides

Busca em uma lista ordenada: PF, MR, slides

Bubblesort: MR

Ordenação por inserção: PF, MR, slides

Ordenação por seleção: PF, MR, slides

Ordenação por inserção binária: slides

Recursão: PF, MR, slides