Gregorio Malajovich: Ensino

MAE511: Fundamentos da Computação Científica 1 (Graduação)

Horário:15:10 a 16:50

Início: 3a feira, 7 de março.

Local: Aulas suspensas em 21/3. Alunos ainda inscritos devem procurar o professor imediatamente na sala C-109C.

Ementa: O curso cobre os conceitos básicos de análise de algoritmos, incluindo noções de combinatória, estruturas de dados (listas e árvores), e uma versão abstrata (simplificação) de linguagem assembler (a máquina MMIX, que substitui a máquina MIX já obsoleta). Para isso seguiremos o texto clássico de Donald Knuth, com as recentes atualizações (ver bibliografia abaixo).

Este é um curso piloto para a graduação em Engenharia Matemática a ser criada em um futuro próximo. A carga de trabalho é comparável à carga de trabalho dos cursos avançados do Bacharelado em Matemática Aplicada.

Bibliografia:
Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms. Addison-Wesley, Boston, 1997, 3d Edition.
Donald E. Knuth, The Art of Computer Programming Fascicle 1:MMIX, disponível aqui

Pré-requisitos: Não há pré-requisitos formais mas há pré-requisitos em termos de conhecimentos e habilidades. A lista zero de exercícios é parte dos pré-requisitos, a outra parte é a capacidade de acompanhar o material do curso (sugiro obter e dar uma olhada na bibliografia). É necessário conseguir completar a primeira lista (abaixo) ANTES DA PRIMEIRA AULA.

Avaliação Arguição dos exercícios e listas, em sala.

Listas de exercícios:

Lista zero (para a primeira aula).

Consiga uma cópia da bibliografia. A partir da página da linguagem MMIX, baixe e instale o assembler e o emulador mmix (mmixal, mmix) e uma versão do gcc capaz de produzir código para o mmix. Rode alguns exemplos usando o mmixal e o mmix-gcc.
Instruções detalhadas: No meu sistema (Debian Gnu/Linux 8), eu baixei mmix-20160804.tgz, descomprimi em um diretório vazio, e segui as instruções do arquivo README. Depois de executar make doc e make all, passei para modo superusuário e copiei os executáveis para o diretório /usr/local/bin. Também baixei e instalei mmixdebugger.jar. Depois baixei e instalei a versão adaptada do gcc já compilada do link optmmix-date-.tgz a partir desta subpágina. Isso requer ter algumas das bibliotecas da arquitetura i386 instaladas, mesmo usando a arquitetura amd64.
Uma vez o ambiente instalado, rode alguns exemplos. Tente também produzir um programa mmix a partir de uma fonte C ou C++ com o comando mmix-gcc hello.c -S.

Lista 1

Modifique o exemplo do algoritmo de Euclides, modificado conforme o exercício 1.2.1.13 (imprima T).

Lista 2

Escreva um programa MMIX que aceite como argumento uma cadeia de caracteres, e imprima essa cadeia na ordem reversa. No final o programa deve detectar se a cadeia é palíndroma (igual à sua reversa) ou não.

Lista 3

Implemente em MMIX o método do crivo de Eratóstenes para produzir uma tabela de números primos. Compare o desempenho (tempo de execução) com o dos programas exemplos.

Lista 4

Exercício 1.3.2.27' (do Fascículo 1).

Lista 5

1. Escreva um programa MMIX que aceite um argumento e verifique que este descreva um produto de ciclos de permutação, como no Algoritmo 1.3.3.A. 2. Implemente o algoritmo em MMIX.

Lista 6

Escreva um programa MMIX que aceite um parâmetro n entre 1 e 20 e produza todas as permutações de n elementos, em formato de produto de ciclos.

Planejamento
Data Matéria Exercícios cobrados
7 de março Indução, algoritmos, algoritmo de Euclides. 1.1, 1.2.1. Lista zero
9 de março Máquina MMIX, implementação do Alg. de Euclides 1.3.1'
14 de marçoNúmeros, potências, somas, produtos 1.2.2, 1.2.3Ex.1.2.1.8, 1.2.1.13
16 de março Mais máquina MMIX, descrição detalhada. 1.3.1'Lista 1
21 de marçoTeoria elementar dos números 1.2.4Ex.1.2.2.22,1.2.3.{30-33}
23 de marçoO assembler MMIX. 1.3.2'Lista 2
28 de março Permutações, fatoriais, coeficientes binomiais 1.2.5, 1.2.6 Ex.1.2.4.{26,37,45,46,47}
30 de março O assembler MMIX (2). 1.3.2' Lista 3
4 de abril Números harmônicos e de Fibonacci 1.2.7, 1.2.8 Ex.1.2.6.{47,53,60,61,64}
6 de abril Aplicação a permutações 1.3.3 Lista 4
11 de abrilFunções geradoras 1.2.9 Ex.1.2.7.{13,14,15} e Ex.1.2.8.{29,30,34}
13 de abrilRecesso (Semana Santa)
18 de abrilSubrotinas, corotinas, recursão. 1.4.1', 1.4.2' Lista 5
20 de abrilRecesso (Tiradentes)
25 de abrilAnálise de um algoritmo. 1.2.10Ex. 1.2.9.{10,15,19,25}
27 de abrilRotinas interpretativas 1.4.3' Lista 6
2 de maioRepresentações assintóticas 1.2.11*
4 de maioPilhas, filas, deques 2.2.1
9 de maioAlocação sequencial 2.2.2
11 de maioAlocação por ponteiros 2.2.3
16 de maioListas circulares 2.2.4
18 de maioListas duplamente encadeadas 2.2.5
23 de maioArrays e listas ortogonais 2.2.6
25 de maioPercurso de árvores binárias2.3.1
30 de maioRepresentação binária de árvores 2.3.2.{1,2}
1 de junhoMais representações de árvores 2.3.3
6 de junhoPropriedades matemáticas das árvores 2.3.4
8 de junhoLema "do infinito" 2.3.4.3
13 de junhoEnumeração de árvores 2.3.4.4
15 de junhoCorpus Christi
20 de junhoComprimento de caminhos 2.3.4.5
22 de junhoEstruturas multiplemente encadeadas 2.4
27 de junhoAlocação dinâmica 2.5

MAE720: Álgebra Linear Computacional (Mestrado e Doutorado) e MAE471(Graduação)

Horário:3a e 5a 17:10-18:50

Início: 3a feira, 7 de março.

Local: Sala B-106-B.

Ementa: Aritmética de ponto flutuante. Normas de matrizes e números de condicionamento. Solução de sistemas de equações lineares e de problemas de autovetores, com ênfase nos aspectos matemáticos. Uso das bibliotecas blas e lapack. Neste primeiro curso, focaremos em matrizes densas ou estruturadas. Pré-requisitos: Álgebra linear (graduação), e conhecimento de uma linguagem de programação como C, C++ ou Fortran.

Bibliografia:
Demmel, James: Applied Numerical Linear Algebrai. SIAM, 1997. (Ver também errata).

Listas de exercícios: Ver tabela abaixo. Os exercícios serão arguidos em sala na data indicada.
Planejamento
Data Matéria Exercícios cobrados
7 de marçoIntrodução, 1.1 a 1.4
9 de marçoAritmética de Ponto Flutuante, 1.5 e 1.6
14 de marçoNormas, 1.7. Ex 1.1 a 1.7
16 de marçoIntrodução à BLAS. Ex 1.8, 1.9
21 de marçoEquações lineares: perturbação, 2.1 e 2.2. Ex 1.10 a 1.12
23 de marçoEliminação Gaussiana e introd. ao Lapack (2.3). Ex 1.18
28 de marçoAnálise do Erro 2.4. Ex 1.20
30 de marçoMelhoria da Precisão 2.5. Ex 2.2, 2.3, 2.8
4 de abrilComputação por blocos 2.6. Ex.2.4.
6 de abrilParalelismo e introdução ao MPI. Ex 2.9
11 de abrilMatrizes estruturadas 2.7, 2.8.2.10
13 de abrilRecesso (Semana Santa)
18 de abrilO grupo ortogonal. Ex.2.14
20 de abrilRecesso (Tiradentes)
25 de abrilO problema de mínimos quadrados, 3.1, 3.2. Ex.2.16
27 de abrilPerturbação, 3.4. Ex 3.1
2 de maioProblemas de posto deficiente, 3.5,3.6,3.7. Ex.3.3
4 de maioProblemas aproximação de tensores. Ex 3.8,3.9
9 de maioProblemas não-simétricos de autovalores 4.1 a 4.3. Ex.3.19 ou 3.20
11 de maioAlgoritmos: iteração direta, inversa, ortogonal, 4.4.1-3. Ex 4.1, 4.2, 4.3
16 de maioAlgoritmos: iteração QR, 4.4.4-8. Ex.4.4
18 de maioPolinômios de matrizes 4.5-4.8. Ex.4.6
23 de maioProblemas simétricos de autovalores 5.1-5.2 Ex.4.14
25 de maioProblemas simétricos de autovalores (continuação) 5.1-5.2. Ex.5.1, 5.2
30 de maioAlgoritmos: iteração tridiagonal, Rayleigh, 5.3.1, 5.3.2. Ex.5.4
1 de junhoAlgoritmos: divide et impera, deflação 5.3.3. Ex.5.5
6 de junhoAlgoritmos: Biseção, Jacobi 5.3.4, 5.3.5. Ex.5.6,5.7
8 de junhoAlgoritmos para a SVD 5.4. Ex.5.13
13 de junhoAlgoritmos para a SVD (continuação) 5.5. Ex. 5.23
15 de junhoCorpus Christi
20 de junhoReticulado de Toda e fluxo de matrizes
22 de junhoApresentação de trabalhos
27 de junhoApresentação de trabalhos

Canal do twitter para avisos urgentes

O objetivo é manter um canal de comunicação utilizável caso a rede da UFRJ esteja inoperante. Para acessar o canal abaixo, é necessário autorizar javascript de twitter.com e de twimg.com.
Tweets de @gmalajovich