ALGORITMOS E SUA ANÁLISE:
UMA INTRODUÇÃO À CIÊNCIA DA COMPUTAÇÃO

Valdemar W. Setzer
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP
www.ime.usp.br/~vwsetzer – esta versão: 7/11/17

Objetivo

Em geral muitas pessoas têm a ilusão de que usar um computador já dá um conhecimento sobre o que ele é e o que é um programa. Nesta palestra fazemos uma introdução aos algoritmos, que são a base de toda a programação de computadores, não dependem destes últimos e constituem um aspecto fundamental da ciência da computação (que não é o que se costuma chamar de "informática", nome errado pois o computador processa dados, e não informações). Esta palestra é parte do projeto Embaixadores da Matemática do IME.

Resumo

Proposição de um problema: ordenação de números. Resolução pelos participantes, em grupos de 2 ou 3, usando cartões e regras semelhantes às impostas por um computador. Classificação das soluções: métodos de seleção, da bolha e da inserção. Noção de complexidade no tempo, notação O() e análise desses métodos. Método da ordenação por árvore binária (os alunos constroem a árvore com eles mesmos). Análise da complexidade: O(nlogn). Comparação numérica com os 3 métodos iniciais. Noção de algoritmo ótimo. O que é um algoritmo? Descrição formal, programação. Corretude. Intratabilidade.

Pré-requisitos

Soma de progressões aritmética e geométrica. Noções de logaritmos.

Número mínimo de participantes

Idealmente deve haver no mínimo 15 participantes, necessários para uma das atividades.

Material necessário

  • Microcomputador; datashow; quadro negro ou branco, ou flip-chart.
  • Carteiras para os alunos ordenarem os cartões, em geral em grupos de 2 ou 3.
  • Meia folha de papel sulfite para cada aluno, para as avaliações finais.

Duração

Duas horas, preferivelmente mais pelo menos meia hora. Ideal: 3 horas com intervalo.

Avaliação

No fim da aula, os participantes fazem uma breve avaliação por escrito (one-minute paper) respondendo as seguintes perguntas: 1. Qual foi a coisa mais importante que aprendi? 2. Qual foi a maior dúvida que ficou? 3. Comentários.

Material na Internet

Artigo: http://www.ime.usp.br/~vwsetzer/alg/algoritmos.html

Apresentação: http://www.ime.usp.br/~vwsetzer/apresentacoes/algoritmos.pps

Avaliações de participantes: http://www.ime.usp.br/~vwsetzer/pals/algoritmos-avaliacoes.html

Bibliografia

Ver no artigo

Aulas realizadas (Em ordem cronológica reversa)

  1. 2/4/17 9-12h00, para professores e alunos de licenciatura em matemática e interessados, no Centro de Aperfeiçoamento do Ensino de Matemática (CAEM), do Instituto de Matemática e Estatística (IME) da USP, São Paulo, dentro do projeto Embaixadores da Matemática do IME.
  2. 3/3/17 na Escola Prof. Expedito Camargo Freire (EEECF) para professores de matemática e alunos, R. Genko Sakane 10, Brancas Nuvens, Campos do Jordão, (12) 3662-3311, dentro do projeto Embaixadores da Matemática do IME; info: prof. Benedito Mariano msditom@hotmail.com
  3. 3/3/17, para professores e alunos da Escola Prof. Expedito Camargo Freire (EEECF), R. Genko Sakane 10, Brancas Nuvens, Campos do Jordão, (12) 3662-3311, dentro do projeto Embaixadores da Matemática do IME; info: Benedito Mariano (diretor) <msditom@hotmail.com>
  4. 19/5/15, na disciplina CCM0128 - Computação II para o Curso de Ciências Moleculares da USP, Cidade Universitária, São Paulo (info: prof. Ronaldo Fumio Hashimoto <ronaldo@ime.usp.br>)
  5. 25/5/13, para professores do ensino fundamental e médio, promovida pelo Centro de Aperfeiçoamento do Ensino de Matemática (CAEM), do IME-USP, Cidade Universitária, São Paulo, SP
  6. 28/10/09, para alunos e professores do ensino médio do Colégio Porto Seguro, São Paulo (info: Profa. Maria America Cabral <americac@portoseguro.org.br>)
  7. 25/9/09, no Seminário do Centro de Aperfeiçoamento do Ensino da Matemática (CAEM) do Instituto de Matemática e Estatística da USP, São Paulo

Aulas programadas

  1. 8/11/17, na 1a. Jornada do Instituto Federal de São Paulo em Cubatão, SP; info: NADIR BARBOSA DA SILVA SANTOS nadir at.arroba ifsp.edu.br

Aguardando convites!

Ver lista de palestras dadas e programadas.
Ver títulos de outras palestras