Departamento de Ciência da Computação do IME - Universidade de São Paulo

MAC-122 PRINCÍPIOS DE DESENVOLVIMENTO DE ALGORITMOS


MAC122 é disciplina obrigatória do currículo do Bacharelado em Ciência da Computação do IME e de alguns outros cursos da USP. Trata-se da segunda disciplina de computação no currículo desses cursos. A disciplina está sob a responsabilidade do Departamento de Ciência da Computação do IME-USP.

HORÁRIO DAS AULAS:  segunda das 19:20 às 21:00 hs e quinta das 21:00 às 22:50 hs.
LOCAL: sala 7, Bloco B
PROFESSORA:  Leliane Nunes de Barros - email: leliane@ime.usp.br

Programa oficial

OBJETIVOS:   Estudo da correção, da análise de eficiência e do desenvolvimento de algoritmos e de suas estruturas de dados básicas.
PRÉ-REQUISITOS:  MAC-110 - Introdução à Computação.
CARGA HORÁRIA: 4 horas de aulas samanais (aproximadamente 30 horas de aulas no semestre) com direito a 4 créditos.
CONTEÚDO:


BIBLIOGRAFIA BÁSICA

DATAS DE PROVA E CRITÉRIO DE AVALIAÇÃO

                alteração >>>       Prova de Recuperação
                                               Terça, 24 de julho de 2001
                                               Horário: das 19:30 às 21:30 hs
                                               Local: sala 7, Bloco B
                                                                     A prova abrangerá todo o conteúdo da disciplina.

MONITOR

EXERCÍCIOS PROGRAMAS

OUTROS SÍTIOS RELACIONADOS

NOTAS
 


  BIBLIOGRAFIA OFICIAL DE MAC 122

D. D. Salvetti, L. M. Barbosa, ALGORITMOS, Makron books, 1998.
N. Wirth, ALGORITHMS AND DATA STRUCTURES, Prentice-Hall, 1986.
R. Sedgewick, ALGORITHMS, Addison-Wesley, 1988.
N. Ziviani, PROJETO DE ALGORITMOS COM IMPLEMENTAÇÕES EM PASCAL E C, Pioneira, 1993.
J. Bentley, PROGRAMMING PEARLS, Addison-Wesley, 1986.
J. Bentley, MORE PROGRAMMING PEARLS, Addison-Wesley, 1988.
A.V. Aho, J.D. Ullman, FOUNDATIONS OF COMPUTER SCIENCE, Computer Science Press, 1992.

Para ler algumas críticas sobre a bibliografia oficial, consulte a  página de referências bibliográficas  do professor Paulo Feofiloff - IME-USP.
A página de bibliografia para MAC122 do professor Carlos Eduardo Ferreira e do professor possue uma lista estensa de livros para a disciplina.

Notas de aula do Professor Paulo Feofiloff.


  DATAS DE PROVA E CRITÉRIO DE AVALIAÇÃO

Datas das provas

P1: 26 de abril    Lista de Exercícios Resolvidos     -- Lista de Exercícios Resolvidos (formato .doc)
P2: 21 de junho   Lista de Exercícios Preparatória para a P2
  PSUB: 5 de julho (a prova substitutiva será aberta, ou seja, qualquer aluno poderá fazê-la para melhorar a sua média)
alteração >>>       Rec: Terça, 24 de julho de 2001
                               Horário: das 19:30 às 21:30 hs
                               Local: sala 7, Bloco B
                                              A prova abrangerá todo o conteúdo da disciplina.

A média das provas (MP) será a média aritmética das duas maiores notas (P1, P2 e PSUB).

Exercícios-programas
Os exercícios são todos obrigatórios e a média de EPs (MEP) será a média aritmética.
Observações importantes:
Média final
Se MP >= 5.0 e MEP >= 5.0
então MFINAL = (2 * MP + MEP) / 3
senão MFINAL = min(MP, MEP)
Normas de aprovação
MFINAL >= 5.0                 =>     Aprovado
3.0 <= MFINAL <= 5.0      =>     Recuperação
MFINAL <= 3.0                  =>     Reprovado

A média final após a prova de recuperação será a média aritmética entre MFINAL e nota da Rec.
Serão aprovados os alunos que obtiverem média  >= 5.0  .



  NOTAS

        Lista de notas        Recuperação



  MONITORIA
Alexandre Murakami
plantão de monitoria:   segunda e terça das 18:15 hs às 19:15 hs
e-mail:                             ale_murakami@bol.com.br


  EXERCÍCIOS PROGRAMAS

       EP0:    arquivo-ps    --    arquivo-pdf
                    Data de entrega: 26 de março
                    "Aquecendo os motores"
                     O que entregar:

       EP1:    Verificação de um documento HTML
                    Data de entrega: 03 de maio
 
Tutorial   HTML
Faça um programa que verifique possíveis erros em páginas HTML. O programa deve receber como entrada um arquivo HTML e verificar se as seguintes etiquetas (e somente essas) estão balanceadas corretamente:

<HTML> <HEAD>, <TITLE>, <BODY>, <ADDRESS>, <CITE>, <CODE>, <EM>, <KBD>, <STRONG>, <VAR>, <B>, <I>, <U>, <STRIKE>, <S>, <BIG>, <SMALL>, <SUB>, <SUP>, <FONT>, <A>, <UL>, <OL>, <PRE>

Os atributos das etiquetas devem ser ignorados pelo seu programa. Todas as outras partes, texto e comandos desconhecidos do arquivo devem ser ignorados. Etiquetas que não são usadas em pares  (por ex. <IMG SRC = "newred.gif">) devem ser ignoradas. Nao se esqueça que HTML não diferencia entre maiúsculas e minúsculas, e seu programa também deve funcionar analogamente. Seu programa deve dizer, na saída, que as etiquetas estão corretamente balanceadas ou, caso contrário, que não estão. Nesse último caso, seu programa deve informar ao usuário qual etiqueta e qual linha do arquivo que está desbalanceada.

O algoritmo básico desse programa é semelhante ao do problema de expressões matemáticas contendo {}, [] e (), explicado em aula. Você pode usar funções C de manipulação de strings.

Receita para leitura e escrita em arquivo


                 EP2:   Algoritmos de Ordenação

                        EP2 - enunciado

                       Receita para geração de números aleatórios

    Receita para cronometrar a execução de um algoritmo


  OUTROS SÍTIOS RELACIONADOS
Página criada pelo Professor Roberto Marcondes, contendo ligações para páginas de outros professores do Departamento de Computação do IME  que estão relacionadas à disciplina MAC122.




Leliane Nunes de Barros
leliane@ime.usp.br
Instituto de Matemática e Estatística da USP