Problemas musicais - estrutura, propostas e complexidade

• Luerbio Faria UERJ
• Natan Figueiredo UERJ
• Vinicius Fernandes dos Santos UFMG

DOI: https://doi.org/10.5753/etc.2024.2679

Resumo

Arranjos musicais têm sido tratados recentemente do ponto de vista combinatório. Esses problemas consideram uma partitura com um número dado de pautas correspondentes aos instrumentos participantes. O objetivo é selecionar um certo número de instrumentos que atendam a algumas propriedades musicais específicas. Neste trabalho, são propostos dois novos problemas de decisão para arranjo musical, o ARRANJO PARA k INSTRUMENTOS e o PREENCHIMENTO DE TEMPOS POR INSTRUMENTOS. É provado que ambos os problemas são NP-completos.

Referências

Curtis Roads. Research in music and artificial intelligence. ACM Computing Surveys (CSUR), 17(2):163–190, 1985.

Godfried T Toussaint. Algorithmic, geometric, and combinatorial problems in computational music theory. Proceedings of X Encuentros de Geometria Computacional, pages 101–107, 2003.

Erik D Demaine and William S Moses. Computational complexity of arranging music. The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, Volume 2, 2:364, 2017.

R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.