1. Seja N={ 1, 2, ..., n}. Enumere todas as sequências crescentes dos elementos de N existem, começando com 1 e terminando com n ? (As sequências podem ter qualquer tamanho.)
   
   Enuncie o teorema, prove por indução matemática e escreva o algoritmo correspondente.
   
   
2. Seja u_n o número de palavras de n caracteres no alfabeto { 0,1 } que tem a propriedade de não possuir 2 zeros consecutivos. Prove, por indução, que: u₁=2, u₂=3, u_n = u_n-1 + u_n-2, para n³3.
   
   Escreva um algoritmo para enumerar todas estas palavras.
   
   Enuncie o teorema, prove por indução matemática e escreva o algoritmo correspondente.
   
   
3. Considere agora o problema de gerar as rodadas de um campeonato onde todos os n participantes jogam entre-si. Em cada rodada, todos os participantes jogam, e existem n-1 rodadas (n é sempre par) de n/2 jogos.
   
   Assuma que n=2^k, para k=1,2,....
   1. Enuncie o teorema de que sabe-se resolver este problema para n = 2^k, k=1,2,..., e apresente sua prova por indução forte. (Assuma que as rodadas de dois conjuntos de tamanho n/2 são conhecidas).
   2. Escreva o algoritmo correspondente à sua prova.
   
   
4. Considere o conjunto P de todas as permutações dos elemento 1, 2, ..., n. Considere que estas permutações estão ordenadas lexicograficamente. A função rank(p), definida para p Î P, retorna a posição no conjunto ordenado da permutação p. A função unrank( k ), definida para k = 1, 2, ..., n! retorna a permutação que ocupa a posição k no conjunto ordenado P.
   
   Projete algoritmos para estas duas funções.

This document was translated from L^AT_EX by H^EV^EA.