[ Principal | Tarefas ]

MAC 323 - 2003

Tarefas

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

  1. 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.
  2. Número de instruções: 10
  3. Posições de memória: 100
  4. Números: com até 6 dígitos, sendo 5 se negativo
  5. 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:
  1. Implementa a partir de "applet", mas deve rodar também como aplicativo
  2. 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
  3. Aplicativo: permitir ler "programa" de arquivo, permitir entrada manual e permitir gravar "programa" (na memória)
  4. 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)
  5. 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:
  1. Instrução "0EE": "0-0000" => "final de programa"; "0-0011" => "AC <- 11"; "0--011" => "AC <- -11";
  2. 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

  1. 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.
  2. 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:
  1. EXPR: com expressão artimética, com '+', '-', '*' e '/' (vide ex_compilador.tgz)
  2. EXPR_LOG: com expressão lógica, com '&&', '||' e '!' ('e', 'ou' e 'não') e com os relacionais '<','>','<=','>=','==','!='
  3. atribuição: 'variavel = EXPR;'
  4. if: comando de seleção, 'if (EXPR_LOG) comando1;', 'if (EXPR_LOG) comando1; else comando2;'
  5. while: comando de repetição, 'while (EXPR_LOG) comando;', 'while (EXPR_LOG) { comando1; ... }'
  6. le: comando simplificado para leitura de um valor, 'le(var1,var2...)'
  7. 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:
  1. Páginas referenciadas: monta uma página Web contendo "links" para todas as referidas pela inicial e pelas seguintes (páginas "alcancáveis")
  2. 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)
  3. Tempo de busca: use as funções internas do Java para fornecer o tempo de busca
  4. Applet: para usar versão applet gere um arquivo com as palavras chaves de busca e páginas em que ocorrem
Algumas dicas:
  1. 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'
  2. Pode usar algum algoritmo pronto de árvore 2-3 ou de AVL, mas indique de onde veio o código
  3. 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:
  1. 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.
  2. 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")
  3. 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)):
  1. 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.
  2. 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:
  1. 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").
  2. 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

 

[ Página inicial | Panda2 | Lista MAC323 | Lista Java | Info ]