Estruturas de Dados I - trabalho prático

Estes trabalhos devem ser entregues até dois dias antes da data de apresentação.

Estas especificações são PARCIAIS, e mais informações e restrições serão adicionadas!
Todos os trabalhos devem ser feitos em C;
Todos os programas devem ser compiláveis e funcionar em ambiente Unix! (Eu farei os testes em Linux);
Os trabalhos deverão ser acompanhados de um pequeno texto descrevendo a arquitetura do programa, algoritmos e estruturas de dados usados. Este texto deve estar no formato PDF. De preferência em um formato semelhante ao de artigos científicos de Computação e Matemática;
Os textos deverão justificar as escolhas de algoritmos e estruturas de dados usados. Estas escolhas também serão avaliadas!

Indexação dinâmica de texto

Seu programa lerá um texto e permitirá que você procure palavras. O programa deve ter um prompt interativo, que aceita os comandos read, find, show, save.

Um exemplo de consulta ao programa:

*) read historia.txt
 *> arquivo historia.txt lido e indexado
*) find chocolate
Linha      Ocorrencia
10         "... copo de chocolate quente ..."
13         "... tomar o chocolate ..."
9          "... mais choclate ..."
 *> 3 ocorrencias encontradas
*) show 12-14
12 havia voltado para casa.
13 Ele entao decidiu tomar o chocolate,
14 percebendo que naquele dia nao"
 *> 3 linhas mostradas
*)

O programa deve ordenar as ocorrências por frequência de busca, e a frequência de busca deve ficar armazenada em disco, para que o usuário possa sair do programa e voltar tendo as frequências preservadas. O comando "save" gravará as frequências de busca no arquivo (por exemplo historia.txt) em algum lugar onde possa encontrar depois (por exemplo, em .indexador-freq_historia.txt

Grep flexível

Estude a ferramenta grep do Unix. Você fará um concorrente do grep, que faz casamento de padrões por proximidade.

Este tecto tem alguns problemas.
Varas palsvras estao escritas de forma arrada,
como alias acontece muoto quando estamos com prassa
escrevendo um texto.
Eu tento nao cometer erros, mas...

apgrep texto
1: Este tecto tem alguns problemas.
4: escrevendo um texto.

Note que a palavra "tento" não foi selecionada, mesmo tendo um só caracter diferente de "texto" (porque a distância de teclado entre as duas é muito grande).

O programa deve aceitar frases também, entre aspas

Typo corrector

Este tecto tem alguns problemas.
Varas palsvras estao escritas de forma arrada,
como alias acontece muoto quando estamos com prassa.

1: texto -> texto
2: palsvras -> palavras
2: arrada -> errada, arada
3: muoto -> muito
4: prassa -> passa, pressa

Note que as palavras "arrada" e "prassa" não foram incluídas, porque o programa não usou apenas a distância de teclado.

O programa deve usar uma lista de palavras do Português (ou Inglês) para decidir quando trocar uma palavra por outra;
Quando houver duas possíveis substituições, aquela que tem distância 1 no teclado deve ser preferida (por exemplo, bsla deve ser trocada por bala ou bela, e não por bola);
O programa deve produzir, à escolha do usuário, uma ou mais das seguintes saídas:
- Um novo texto na saída-padrão
- Um diff que possa ser aplicado ao texto original
- Uma lista de correções por linha (como a do exemplo)

Manipulação simbólica de matrizes

Implemente dois algoritmos em matrizes: um para calcular o determinante e outro para multiplicar duas matrizes. As matrizes serão especificadas de forma simbólica.

det:
x y
a b

r: xb - ay

det:
x 0
a b

r: xb

det:
x 4
3 2

r: 12 - 2x

mul:
2 b
a 0

x -1
4 y

r:
2x+4b   -2 + by
ax      -a

Use representação esparsa para as matrizes.

Algoritmos genéticos para o TSP

Use AG para resolver o TSP (traveling salesperson problem).

As cidades devem ser representadas como uma matriz esparsa: se não há caminho de uma cidade a outra, a entrada não deve aparece na matriz (note que a interpretação da ausência do valor na matriz não é "custo zero", mas "custo infinito").
Como não há necessariamente aresta entre cada par de cidades, o grafo pode não ser Hamiltoniano (ele pode nem ser cíclico!) Assim, não se pode exigir que as cidades sejam percorridas uma só vez, mas pode-se exigir que o número de repetições seja minimizado.

Algoritmos para caminhos mínimos

Implementar os algoritmos de Bellman-Ford e Dijkstra.

Comparar o tempo de execução para diversos grafos gerados automaticamente. O sseguintes links podem ajudar:
```
	http://sourceforge.net/projects/graphgene/
	http://sourceforge.net/projects/bouquet/
	http://www.brandonparker.net/graph_gen.php 
```
Além disso, vocês podem procurar por random graph generator
Fazer o programa gerar uma versão visual do grafo, usando o graphviz.
Escolher uma das opções a seguir:
- Propor uma aplicação real (e implementar a proposta em um simulador)
- Paralelizar ambos os programas tanto quando possível, e ver o efeito na prática (este último ponto seria fantástico, mas vc precisaria escrever código para multithread em C)