MAC-IME-USP IMRE SIMON CARLOS EDUARDO FERREIRA

SALA 290A TEL.: 3818 6142 SALA 297A TEL.: 3818 6140

EMAIL is@ime.usp.br E-MAIL cef@ime.usp.br

MONITORA: ELIDIA Y. ITIKAWA MONITOR: MARCIO C. CABRAL

Este exerc�cio-programa ser� avaliado pelo c�digo e tamb�m pelos testes que voc�s fizerem para avaliar a corretude e efici�ncia do algoritmo, assim como o relat�rio com os resultados que voc�s obtiverem para o problema proposto.

Um dos algoritmos que estudamos nas aulas para ordena��o de vetores foi o bubblesort. A id�ia deste algoritmo � aplicar sucessivamente invers�o de pares de elementos que est�o na ordem incorreta, at� que ao final de certo n�mero de passos o vetor estar� ordenado. A id�ia deste exerc�cio-programa � oferecer uma opera��o de invers�o mais ``poderosa'', e buscar algoritmos de ordena��o mais eficientes utilizando tal opera��o.

Escreva uma fun��o inverte com o seguinte prot�tipo

int inverte (int v[], int i, int k, int n)

v[i], v[i+1], , v[i+k-1]

Exemplo: Suponha que o vetor cont�m os elementos 1, 3, 4, 2, 6, 7, 8, 9, 5. Ao aplicarmos inverte(v, 3, 3, 9) obtemos no vetor a seguinte ordem: 1, 3, 4, 7, 6, 2, 8, 9, 5. Ao aplicarmos ao mesmo vetor inicial inverte(v, 0, 4, 9) obtemos: 2, 4, 3, 1, 6, 7, 8, 9, 5.

Sua tarefa neste exerc�cio-programa � escrever algoritmos que recebam um vetor com elementos e ordenam este vetor, utilizando a opera��o inverte descrita acima. Obviamente um jeito f�cil de fazer isso � implementar o bubblesort (as trocas s�o chamadas do inverte com ). Este algoritmo faz no m�ximo chamadas da fun��o inverte.

Uma aplica��o deste exerc�cio-programa ocorre em Biologia Computacional. Sabemos que o DNA � uma cadeia dupla de unidades b�sicas (bases nitrogenadas) e uma forma de tentar estabelecer graus de ``parentesco'' (ou proximidade) entre esp�cies � calcular o n�mero m�nimo de opera��es b�sicas (muta��es, revers�es, transloca��es, etc) que levam a seq��ncia gen�tica de um indiv�duo de uma esp�cie em um da outra. Uma dessas opera��es � a revers�o. Uma revers�o ocorre quando um ``peda�o'' do DNA se desprende e se ``cola'' novamente na seq��ncia, por�m na ordem invertida. Esse fen�meno parece ser relativamente freq�ente, e seu estudo � de interesse aos pesquisadores de filogenias. Podemos pensar no problema de transformar uma seq��ncia de DNA em outra atrav�s de ``revers�es'' como o problema de ordenar uma seq��ncia atrav�s de aplica��es da fun��o inverte.

Este exerc�cio-programa est� aberto a diversas perguntas, que voc�s poder�o e dever�o explorar em suas solu��es:

• Escreva v�rios algoritmos diferentes de ordena��o e compare o n�mero de chamadas que cada um faz para ordenar uma seq��ncia qualquer. � poss�vel determinar qual de seus algoritmos � mais eficiente?
• � poss�vel escrever um algoritmo que ordena a seq��ncia utilizando sempre um n�mero m�nimo de chamadas � fun��o inverte?
• Pense agora no problema em que o � fixo (por exemplo, ou ). � poss�vel ordenar um vetor com elementos aplicando a fun��o inverte com fixo? Se �, em que casos? Para quais valores de e ? Se n�o, por que? Coloque todas as suas conclus�es em seu relat�rio.
• Suponha agora que a opera��o inverte funciona ``circularmente'' no fim do vetor.

  Exemplo: Aplicando ao vetor do exemplo acima inverte(v, 7, 5, 9) obtemos: 1, 5, 9, 2, 6, 7, 8, 4, 3.

  As mesmas perguntas acima se aplicam a esta nova vers�o do problema.

  Um joguinho baseado nesta id�ia pode ser visto na sala 297A, em que e . Quem quiser brincar... ;-)

• About this document ...