Nesta página serão disponibilizados informações relativas às tarefas a
serem desenvolvidas para avaliação na disciplina.
Tarefas |
Comentários |
|
|
|
|
|
|
Emulador
Última correção no enunciado: 07/07/2003
Objetivos: desenvolver um applet/aplicativo para emular um computador simplificado
- Entrada do "programa": 3 modos, via teclado diretamente teclando sobre as células de memória;
via arquivo na versão aplicativa; e via parâmetro na versão applet.
- Número de instruções: 10
- Posições de memória: 100
- Números: com até 6 dígitos, sendo 5 se negativo
- Um acumulador (AC) e um registrador para "Endereço de Próxima Instrução" (EPI)
Entrega: dia 27/06
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa3.tgz seu_diretorio_com_arquivos
Em triplas
|
Algumas dicas:
- Implementa a partir de "applet", mas deve rodar também como aplicativo
- Applet: permitir entrada de "programa" manual ou não (de acordo com configuração) e
eventualmente ler de parâmetro se houver o parâmetro PROGRAMA
- Aplicativo: permitir ler "programa" de arquivo, permitir entrada manual e permitir gravar "programa" (na memória)
- Cada posição de memória terá 6 caracteres, porém se for instrução serão usados apenas os 3 primeiro (IEE: I número
da instrução e EE complemento, em geral um endereço de memória)
- Modelo e instruções:
0 AC <- cEE (se EE<>00, senão final de progr.) | Saída:______________
1 EE <- cAC | +---+
2 AC <- cAC + cEE | |EPI| +--+--+...+--+ o Início
3 AC <- cAC - cEE | +---+ | | | | | o Passo-a-passo
4 AC <- cAC * cEE | ... o ...
5 AC <- cAC / cEE | +--+ +--+--+ +--+
6 cAC>0 => EPI <- EE | |AC| | | | | |
7 EE <- leitura teclado | +--+ +--+--+...+--+
8 saída cEE | Entrada:____________
9 EPI <- EE (desvio incondicional) |
Sobrecarga de comandos para conseguirmos maior "poder" de computação:
- Instrução "0EE": "0-0000" => "final de programa";
"0-0011" => "AC <- 11";
"0--011" => "AC <- -11";
- Instrução "1EE": "1-0011" => "EE <- 11";
"1--011" => "EE <- -11";
Um exemplo: como traduzir "le(x); le(y); le(z); w = x+y+z; imprime(w);" ?
Mais simples: "799...", "798...", "797...", "099...", "298...", "297...", "108...", "808...".
Atenção à instrução "108...", o número "08" corresponde à posição de memória 8 que
corresponderia à pilha de execução. Mas isso é preocupação aos que
farão o compilador (vide abaixo se tiver curiosidade de como "compilar/gera código para" isso).
Entregar via
Panda2
|
|
|
|
Compilador
Última correção no enunciado: 07/07/2003
Objetivos: desenvolver um "compilador" simplificado, que gere código para o emulador acima
- Primeiro, NÃO deixe de examinar o exemplo já pronto de "compilador" para expressões aritméticas em
ex_compilador.tgz!!! Começe a partir deste exemplo.
- Monte o diagrama sintático de EXPR_LOG usando o modelo no exemplo ex_compilador.tgz
Entrega: dia 27/06
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa3.tgz seu_diretorio_com_arquivos
Em triplas
|
Algumas dicas:
O compilador será para um subconjunto reduzido para uma linguagem tipo Java, com:
- EXPR: com expressão artimética, com '+', '-', '*' e '/' (vide
ex_compilador.tgz)
- EXPR_LOG: com expressão lógica, com '&&', '||' e '!' ('e', 'ou' e 'não') e com os relacionais
'<','>','<=','>=','==','!='
- atribuição: 'variavel = EXPR;'
- if: comando de seleção, 'if (EXPR_LOG) comando1;', 'if (EXPR_LOG) comando1; else comando2;'
- while: comando de repetição, 'while (EXPR_LOG) comando;', 'while (EXPR_LOG) { comando1; ... }'
- le: comando simplificado para leitura de um valor, 'le(var1,var2...)'
- escreve: idem para saída, 'escreve(var1,var2...)'
Atenção: pegue as instruções de "máquina" no enunciado do "emulador".
Um exemplo: como traduzir um programa em "alto nível" para "linguagem de máquina" ?
Alto nível: "le(x); le(y); le(z); w = x+y+z; imprime(w);" ?
Código de "maquina": "799...", "798...", "797...", "099...", "298...", "297...", "108...", "808...".
Relevante ao projeto Compilador:
muita atenção à instrução "108...", o número "08" corresponde à posição de memória 8, esta posição
corresponderia, no exemplo, à pilha de execução. Para conseguir gerenciar isso de modo
eficiente é necessário adiar a montagem final do arquivo (guardando o código de "máquina" num "buffer"),
e usando endereço relativo: usa-se "end_ultima_instrucao + pos_relativa" para estas posições de memória
sendo que ao final sabe-se quantas instruções o programa precisou e portanto o valor de "end_ultima_instrucao".
Entregar via
Panda2
|
|
|
|
Buscador
Última correção no enunciado: 07/07/2003
Objetivos: construir um "processador" de conteúdos para páginas Web
Fazer um processador para páginas Web que, a partir de uma página local monta buscador
de palavras e páginas alcançáveis a partir da inicial.
Entrega: dia 27/06
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa3.tgz seu_diretorio_com_arquivos
Em triplas
|
Estrutura geral:
- Páginas referenciadas: monta uma página Web contendo "links" para todas as referidas pela inicial
e pelas seguintes (páginas "alcancáveis")
- Banco de palavras: fazer um banco de palavras, em memória, para buscas rápidas em qualquer das páginas
"alcancáveis" (implementar como B-árvore 2-3 ou como AVL)
- Tempo de busca: use as funções internas do Java para fornecer o tempo de busca
- Applet: para usar versão applet gere um arquivo com as palavras chaves de busca e páginas em que ocorrem
Algumas dicas:
- A lista de palavras não deve ser construida para "palavras" dentro de TAGs, p.e., em '< td align="center">'
não se deve inserir na árvore de busca os termos 'td', 'align' e nem 'center'
- Pode usar algum algoritmo pronto de árvore 2-3 ou de AVL, mas indique de onde veio o código
- Implemente de modo bem "encapsulado", de modo que fique fácil trocar a estrutura interna de representação
(p.e., trocar de 2-3 para AVL e vice-versa)
a partir da discussão na
lista
Para conseguir ler um arquivo remotamente a partir de um "applet" (que esteja no diretório "http" em que o "applet"
se encontra), veja:
http://www.ime.usp.br/~leo/mac323/03-1/exemplos/ex_pega_arq.zip
Para conseguir abrir o navegador com uma página específica, veja o exemplo que preparei em:
http://www.ime.usp.br/~leo/mac323/03-1/exemplos/abrir_navegador.java
Entregar via
Panda2
|
|
Expressões Aritméticas: parte gráfica AWT
Última correção no enunciado: 28/05/2003
Objetivos: desenvolver um sistema gráfico para a parte
anterior do projeto
o usuário pode entrar com várias expressões aritméticas (in-fixa),
digitando inclusive parâmetros e escolhendo-se intervalos para visualização.
Exemplo: A * x^2 + B
Sendo A e B parâmetros, o usuário escolhe intervalo de variação de x, e de A
ou B (um só deles, podendo ser constante - início=fim). O parâmetro escolhido é o ativo.
Entrega: dia 06/06 (adida em 1 semana)
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa2b.tgz seu_diretorio_com_arquivos
Em duplas
|
Implementar:
- Use apenas AWT, seu programa deve funcionar também na versão applet e
a versão aplicativa poderá gravar as funções disponíveis.
- O programa deve permitir visualizar mais que uma função (dentre as disponíveis - usando os mesmos valores
de janela, para x e para o parâmetro "ativo")
- A versão "applet" deve ter um parâmetro de configuração (tipo
<applet ... <param name="1" value="A * x^2 + B">
<param name="2" value="sin(x)">
</applet>
(vide exemplo ex_awt_mouse.zip)
Algumas dicas: (alterado em 22/05/2003)
Desenho da função (x,f(x)):
- Precisão: em alguma viável estática
pode ser definido o número de pontos a serem empregados em cada
gráfico (quanto maior mais preciso), mas também pode ser
deixado para o usuário definir este valor.
- Representação gráfica: deve-se usar uma interpolação
linear entre cada par de pontos
[(xi, f(xi)), (xi+1, f(xi+1))] do gráfico
(se quiser pode deixar uma "checkbox" para o usuário
escolher desenho com linhas ou apenas com pontos - no último
caso pode desenhar o "ponto" através de um g.drawOval(x,y, raio_x,raio_y)).
Pegando coordenada (x,f(x)) do gráfico:
- Coordenada: Quando o usuário passar o "mouse" sobre o gráfico de uma das
funções, digamos f(.), o programa pode listar (através de texto em alguma barra de
mensagem, e no caso de "aplicativo", podería-se tembém colocar um "pop-up menu").
- Como fazer: Usando o método "mouseMoved", que pega a coordena
(x,y) do "mouse" na tela, convertendo-a para a coordenada do
gráfico e fazendo uma busca nas funções ativas na tela.
Veja como usar o "mouseMoved" no exemplo AWT-mouse.
Entregar via
Panda2
|
|
Expressões Aritméticas
Última correção no enunciado: 18/03/2003
Objetivos: dada uma expressão aritmética (in-fixa)
Exp(x), envolvendo Oper abaixo
descrito, montar uma lista ligada (ou vetor, ou
pilha...) em notação pós-fixa
e implementar métodos de avaliação.
Oper: a expressão poderá envolver operadores, constantes, parâmetros, funções e
variável x, por exemplo,
a*(sin(x))^2 + b
Entrega: dia 25/04
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa2.tgz seu_diretorio_com_arquivos
Em duplas
|
Algumas dicas: (alterado em 22/04/2003, 14/04/2003)
- Oper: os operadores, parâmetros, funções e constantes aceitas
- operadores: *, +, -, %, / e ^ (potência)
- constantes: qualquer valor "real"
- parâmetros: quaisquer letras do alfabeto latino
- funções: as funções da classe
java.lang.Math: sin(.), cos(.),
tan(.), asin(.), acos(.),
atan(.), exp(.), log(.),
sqrt(.)
- Implementar um método para listar a expressão na forma original
(in-fixa) e sua correspondente pós-fixa.
O usuário deve poder escolher uma opção para listar as expressões
chamando este método.
- Usar as classes:
|No| -> |NoOp|, |NoVar|, |NoConst|, |NoParam|
|Exp| = |No inicio; mét. avalia expressao(); mét. converte in-pós(); verifica sintaxe() ...|
Vector com cada Exp criada (Vector v=new Vector(); v.addElement( ... ))
- Usuário pode criar quantas expressões (Exp) desejar, sendo
cada uma inserida num Vector (a expressão original pode
ser armazenada como String, mas a outra tem que
ficar em pós-fixa);
- Colocar métodos para teste, deixando o usuário escolher expressão
para listar, valor de parâmetros, parâmetro a variar, intervalos
de variação da variável x e do parâmetro "ativo" e a
quantidade números a serem de valores. Por exemplo: listar
a*x^2 + b, com a (parâmetro "ativo") variando -1 entre
1, fixando-se b=1, e para cada valor do parâmetro "ativo",
listar 10 valores para
x entre -1 entre 1 (-1,
-0.9,...,0.9,1).
O objetivo posterior deste teste é colocá-lo na forma gráfica,
assim o usuário pode ver o gráfico de a*x^2 + b e qual o
impacto da variação do a (ver mudança na concavidade) e
do b (mudança no vértice da parábola).
Entregar via
Panda2
|
|
Problema da satisfatibilidade
Objetivos: dada uma expressão f envolvendo N variáveis lógicas, encontrar valores
para estas variáveis de modo que f(v1,...,vN) = true
Entrega: dia 19/03
Entregar: arquivo compactado (*.tgz: tar cvfz nome_grupo_tarefa1.tgz seu_diretorio_com_arquivos
Em duplas
|
Implementar uma árvore binária, com uma classe noExp e duas sub-classes
noExpOperando e noExpOperador:
- implementar um método que avalia uma expressão lógica; e
- implementar um método que testa todas as possíveis atribuições para as variáveis
buscando uma que resulte true
- convenções: * é e;
+ é ou; e
! é não; .
- exemplo de entrada: f(.) definida por v1 * ( v2 + v3 ) + v1 * ( v2 * v3)
Entregar via
Panda2
|
|