|  
Seja bem-vindo à minha página
pessoal.
Sou aluno do Bacharelado em Ciência da Computação
da Universidade de São Paulo, ingressante do ano de
2003.
Esta página contém alguns dos trabalhos desenvolvidos
durante o curso, dentre outros assuntos não tão
importantes assim (pra falar a verdade, nem um pouco importantes).
Para sugestões, elogios, contatos, mande-me um e-mail.
Reclamações, críticas não-construtivas
e encheções serão automaticamente encaminhadas
para /dev/null.
O curso de Bacharelado em Ciência da
Computação (BCC) teve sua primeira turma formada
em 1974, quando ainda era oferecido como opção
para os graduandos do curso de Matemática.
A partir de 1984 o curso passa a ser oferecido na sua forma
atual, com o ingresso pelo vestibular da Fuvest.
Oferecido pelo Instituto de Matemática e Estatística
da USP, o BCC é reconhecido como um dos melhores cursos
de Computação do país.
Sugiro uma visita à seção Graduação
no sítio do Departamento de Ciência da Computação
(DCC), que contém uma boa quantidade de informações.
Estão aqui disponíveis os trabalhos
desenvolvidos durante o curso.
Entre eles encontram-se os famigerados EPs (Exercícios-Programa),
trabalhos diversos e algumas monografias.
Tenha em mente que muitos dos programas desenvolvidos estão
sob a ótica de um iniciante em programação.
Os arquivos estão disponíveis
na seguinte forma:
- Código-fonte:
para interessados em programação.
Para compilar o código é necessário
um compilador Java, sendo recomendado o kit
J2SE da Sun (inclui o JRE para execução
de classes e applets).
|
- Executáveis:
para interessados em funcionalidade (se é
que há alguma).
- Windows: para plataforma Windows
32 bits;
- Linux: para plataformas Linux
i386;
- JAR: formato multiplataforma,
executa em Windows, Linux, MacOS, Solaris,
etc.
É necessário o JRE —
Java Runtime Environment (Ambiente
de Execução Java) —
para rodá-lo.
|
|
 |
Baixe no sítio da Sun
o J2SE ou JRE se necessário. |
Os programas estão licenciados sob
a GPL.
Clique
aqui para obter uma cópia da licença.
| Primeiro Semestre
de 2003 |
EP1:
Resta-um
MAC0110 |
Primeiro exercício-programa
da disciplina MAC0110 (Introdução
à Computação), e também
do BCC. Sei que um dia vou rir (bastante) disso.
Baseia-se no jogo "resta-um" onde palitos
são tirados sucessivamente, onde perde
aquele que retirar o último palito.
Possui um truque interessante, que garante que
o computador nunca perde.
Download:
|
EP2:
Catálogo de CDs
MAC0110 |
Primeira
incursão no terreno pantanoso da programação.
O programa cataloga por padrão 300 CDs,
e é capaz de usar o recurso de seriação
em Java, sendo capaz de armazenar o conteúdo
de um catálogo de CDs em uma mídia
qualquer.
Download:
|
EP3:
Campo Minado
MAC0110 |
Uma inocente implementação
de um inocente jogo que vem incluso em um inocente
sistema operacional (se é que ele é
merecedor desse título).
Esqueça gráficos 3D, vídeos
em tela cheia e efeitos especiais que utilizam
seu conjunto de caixas de som Dolby Surround.
É uma implementação feita
totalmente em modo texto, que conta inclusive
com um jogador automático (você vai
se sentir inteligente ao vê-lo jogar).
Possui um algoritmo recursivo para mostrar as
posições livres do tabuleiro.
Download:
|
Monografia:
Software Livre
MAC0110 |
Até a presente
data de confecção desta página,
o Software Livre ainda é um assunto polêmico,
mal-explorado e mal-divulgado.
Sem pretensão alguma de resolver isso,
esta dissertação fala um pouco sobre
a origem do movimento para o Software Livre, licença
GPL, entre outros e, claro, Linux.
Download:
|
| Segundo Semestre
de 2003 |
EP0:
Desafio
MAC0122 |
Primeiro
exercício-programa do segundo semestre,
gentilmente publicado durante as merecidas
férias do mês de julho (obviamente,
foi ignorado durante as mesmas).
A tarefa consiste em encontrar o último
dígito não-nulo de um fatorial qualquer,
de modo eficiente, ou seja, sem calcular o fatorial.
Para tanto foi utilizado um algoritmo simples,
que remove 2's e 5's das parcelas do cálculo
do fatorial e checa o último dígito
obtido.
Não é lá muito eficiente,
para 1.000.000.000! o programa leva quase meia
hora calculando.
Caso você descubra que o programa vai muito
além de 1.000.000.000! ganha um vale-bandejão.
Download:
|
EP1:
Jogo-da-velha 3D
MAC0122 |
Objetivo: criar
um jogo-da-velha 3D e fazer um jogador automático
que analise as jogadas do oponente em diversos
níveis de profundidade.
Para fazer as análises é necessário
utilizar pilhas.
Download:
- Não disponível, código
com problemas (e bota problema nisso)
|
EP2:
Catálogo de CDs,
DVDs e Livros
MAC0122 |
Reinvenção
do EP2 de MAC0110.
A diferença desta vez é que o programa
até chega a ser útil, tem uma interface
modo texto interessante (vamos lá, desprenda-se
da GUI), salva arquivos em disco e, penso eu,
tem capacidade de armazenamento virtualmente ilimitada.
A implementação envolve o uso extensivo
de listas ligadas e tabelas de hash, e
uma boa dose de programação orientada
a objetos.
Algumas classes estão com o código
meio mal-acabado (poluído, redundante),
mas o programa cumpre razoavelmente sua tarefa.
Download:
|
EP3:
Algoritmos de ordenação
MAC0122 |
Inserção Direta,
Seleção Direta, BubbleSort,
QuickSort, MergeSort, HeapSort .
Estes são os algoritmos que foram submetidos
a testes e comparações, para verificar
a eficiência dos mesmos na prática
em diversas situações.
Os algoritmos estão implementados em classes
separadas, e uma classe separada é capaz
de aplicar testes em lote ou isolados, determinando-se
um número de elementos por vetor e um número
de amostras (aleatórias, parcialmente ordenadas
e ordenadas inversamente). A mesma classe gera
um relatório para cada algoritmo, em formato
CSV, para que se possa fazer estatísticas,
caso desejado.
Não tente fazer o Inserção
e o Seleção funcionarem pra vetores
grandes, a menos que seu dia seja tedioso o suficiente
para esperar os algoritmos ordenarem.
Outra observação: para vetores grandes,
a implementação do QuickSort
estoura a pilha de recursão. Ordena bem
uns 25.000 elementos.
Mais uma observação! Os pontos de
contagem de trocas, comparações
e etc podem não estar a contento. Ajuste-os
se necessário.
Download:
|
EP4:
Busca de melhor caminho
MAC0122 |
Com base em uma história
real, mas fictícia (Guerra
em Pandópolis), a intenção
é verificar a possibilidade de se realizar
um caminho entre dois pontos, dada uma condição.
No fundo, a história é utilizar
um algoritmo baseado na procura de melhor caminho,
sendo que aqui a implementação foi
baseada no Bellman-Ford-Moore (BFM).
Não há garantias da corretude do
algoritmo (quem sabe em MAC0328 — Algoritmos
em Grafos?), mas, aparentemente, ele resolve o
problema proposto.
Verifique o formato de entrada de dados na página
do enunciado do exercício (não tente
entender a história, é uma piada
interna).
Download:
|
| Primeiro
Semestre de 2004 |
EP1:
Adição e multiplicação
de precisão "ilimitada"
MAC0323 |
E dá-lhe listas ligadas!
Desta vez elas foram utilizadas na implementação
de soma e multiplicação de precisão
virtualmente ilimitada. Isto é, o uso de
listas permite que sejam realizadas adição
e multiplicação de grandes números
(grandes MESMO), em tese, sem limite de tamanho.
Na prática há um limite de tamanho
por número a ser utilizado, que é
o tamanho máximo de caracteres que cabe
num objeto String do Java. Mais uma vez,
se você descobrir quais os maiores números
que esse programa consegue utilizar, ganha um
vale-bandejão. Ah, sim, tem que provar
que o resultado está correto.
Download:
|
EP2:
Soma de matrizes esparsas
MAC0323 |
O exercício considera
o problema de operações em matrizes
esparsas, isto é, que possuem grande número
de linhas e colunas, bem como grande número
de posições das matrizes preenchidas
com zeros. O interesse é economizar espaço
em memória, utilizando alocações
ligadas para suprimir o espaço que seria
ocupado pelos inúmeros zeros.
Esta implementação trata apenas
da soma entre duas matrizes esparsas, mas pode
ser facilmente estendida para multiplicação
e outras operações, bastando que
se adicione a classe correspondente.
Download:
|
EP3:
Árvores Binárias de Busca
MAC0323 |
Árvores binárias
de busca oferecem uma maneira eficiente de se
localizar dados.
Tanto inserção quanto remoção
são O(n) no pior caso e O(log
n) no caso médio.
Esta é uma implementação
simples de árvore binária de busca,
cujos testes inserem e buscam elementos (inserção
com atribuição de chaves aleatórias),
determinam a altura da árvore e a percorrem
em ordem simétrica/in-ordem.
Download:
|
| Segundo Semestre
de 2004 |
| Será? |
|
| |
Comentários
serão bem-vindos caso algum desses códigos
ou programas lhe tenha sido útil, parcial
ou totalmente. |
|
|
