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:

• Exemplos de algoritmos usando pilhas e filas.
• Introdução aos conceitos de listas ligadas e ponteiros.
• Algoritmos recursivos.
• Busca, inserção e remoção em vetores e listas ligadas.
• Busca binária.
• Algoritmos de ordenação (inserção, seleção, mergesort, heapsort, quicksort, etc).
• Algoritmos de casamento de padrões.
• Alguns exemplos de algoritmos de enumeração e otimização sobre seqüências.
• Prova informal da correção de algoritmos.
• Estudo empírico da eficiência de algoritmos.

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

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).

Os exercícios são todos obrigatórios e a média de EPs (MEP) será a média aritmética.
Observações importantes:

• Não serão aceitos EP's atrasados!
• Não os deixe para última hora: você poderá não conseguir terminá-los!
• Não copie! Não faça em grupo! Exercícios realizados dessa maneira obterão nota zero!

Se MP >= 5.0 e MEP >= 5.0
então MFINAL = (2 * MP + MEP) / 3
senão MFINAL = min(MP, MEP)

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  .

        Lista de notas        Recuperação

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

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

• a listagem dos programas. O aluno deve adicionar linhas de comentários aos programas vistos em sala de aula;
• a impressão dos testes efetuados sobre 3 conjuntos de entrada/saída;
• para o Programa 4, além da impressão da saída, o aluno deve entregar um texto explicando o que o programa faz.

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

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.