Sala P3.10, Pavilhão de Matemática

Pedro Filipe, 2º ano do MMA, IST
Danças com Apontadores

A necessidade de fazer backtracking como uma técnica de pesquisa em profundidade surge em múltiplos contextos em informática, sobretudo quando tentamos implementar algoritmos não determinísticos. No entanto, apesar de muito útil, é em geral bastante difícil implementar técnicas de backtracking eficientes. Neste seminário vamos estudar uma técnica apresentada por Hitotumatu e Noshita em 1979 e popularizada mais tarde por Knuth. Começamos por explicar a técnica de um modo geral e de seguida vemos alguns exemplos práticos de aplicação.