Provas
2014/1
Bibliografia
Livro texto:
Literatura complementar:
Fundamentos
Para aprender a tratar relações de recorrência recomendo a leitura do livro:
Algumas relações de recorrência podem ser resolvidas utilizando o Teorema Mestre.
Uma ferramenta interessante para a solução de relações de recorrência é o Wolphram Alpha.
Ne ferrramenta acima copie e cole a equação: T(n) = 2*T(n/2) + n, T(1) = 1
Esta é a relção de recorrência do número de passos do merge sort e, como esperado, o resultado é O(n.logn)
De uma forma geral, é necessário definir a relação de recorrência e os casos base, separados por vírgula.
Na verdade, esta ferramenta é extremamente poderosa e é capaz de resolver vários outros tipos de problemas. Ainda no contexto deste curso, experimente as duas perguntas abaixo:
is P in NP?
is NP in P?
Os resultados foram os esperados?
Exercícios
Listas de exercícios: Lista 1, Lista 2,
Os exercícios mencionados abaixo são dos sites UVa ou URI. Clique aqui para uma breve introdução sobre como utilizar estes sites.
No UVa: 11057, 10567, 12192, 10341, 11413, 12032, 183
No UVa: 11264, 11389, 12405, 11100, 11292, 12210, 10656, 10718, 11157
No UVa: 357, 10306, 11517, 10616, 10819, 11566, 481, 11456, 787, 10684, 108, 10827, 11591
No UVa: 624, 10576, 11085, 524, 574, 10503
Trabalho
Clique aqui para obter os códigos das aulas de PD.
O primeiro aluno que consertar o código de mochila-bu.cpp ganhará um ponto na próxima prova. É importante enviar o código corrigido, com o erro comentado.
Os alunos que entregarem os programas do trabalho de implementação, até às 10:00hs do dia 30/05, também ganham 1 ponto.
Copyright ©2017 - STI - Todos os direitos reservados