Notícias da UFSC

O estudante do curso de Ciências da Computação da Universidade Federal de Santa Catarina (UFSC), Tiago Royer, está entre os três finalistas que concorrem ao prêmio de melhor artigo científico do 35º Concurso de Trabalhos de Iniciação Científica (CTIC). A pesquisa estuda uma nova perspectiva sobre a máquina de Turing. O concurso é parte do Congresso da Sociedade Brasileira de Computação (CSBC) 2016, que ocorre no mês de julho, em Porto Alegre (RS).

O artigo de Royer, Blum axioms and nondeterministic computation of functions, é baseado em seu trabalho de conclusão de curso e define como uma máquina de Turing não determinística – um modelo teórico de computador idealizado por Alan Turing capaz de resolver problemas matemáticos – computa funções com mais de uma solução. Basicamente, ela é uma espécie de fórmula ou equação capaz de testar simultaneamente várias soluções possíveis para um problema. Utilizando essa máquina para resolver o jogo Sudoku, por exemplo, ela testaria todas as combinações possíveis para preencher os quadros do jogo ao mesmo tempo e confirmaria que o Sudoku em questão possui solução.

“Máquinas de Turing não determinísticas funcionam muito bem para problemas de decisão, isto é, problemas em que a resposta é apenas ‘sim’ ou ‘não’. No exemplo do Sudoku, o problema de decisão associado é determinar se um dado jogo possui solução ou não; entretanto, se o problema possui mais de uma solução, encontramos um problema: qual delas a máquina vai resolver? No meu TCC eu estudei formas de extrair um único valor de todas as possíveis soluções que uma máquina não determinística encontra”, afirma Tiago.

O artigo teve orientação de Jerusa Marchi, professora no Departamento de Informática e Estatística da UFSC. “O trabalho atingiu um nível de maturidade intelectual superior ao necessário no desenvolvimento de um TCC. Eu tive a felicidade de orientar o Tiago durante toda a sua graduação, por ser um estudante que se destaca e ser devoto aos estudos. Tínhamos discussões profundas acerca da Teoria da Computação e classes de complexidade. Foi ótimo trabalhar com ele.”

A conclusão do artigo é equivalente a de outros já publicados; mas, explica Jerusa, que “visualizar o processo de computação de outra forma e demonstrar equivalências faz com que caminhemos em direção à consolidação de conceitos. Seguramente, o que faz com que se destaque é a maturidade científica necessária para tratar o assunto. A construção das provas demanda profundo domínio dos conceitos relacionados ao tema”.

O Congresso da Sociedade Brasileira de Computação ocorre no Centro de Eventos da Pontíficia Universidade Católica do Rio Grande do Sul (PUC-RS), em Porto Alegre, entre os dias 4 e 7 de julho.

Mais informações no site do CSBC.

Bruno Rosa/Estagiário de Jornalismo/Propesq/Agecom/UFSC