| Compartilhamento |
|
Exportar este item:
Use este identificador para citar ou linkar para este item:
http://www.bdtd.uerj.br/handle/1/23602| Tipo do documento: | Dissertação |
| Título: | Problemas Computacionais de Arranjo Musical |
| Título(s) alternativo(s): | Musical Arrangement Computacional Problems |
| Autor: | Figueiredo, Natan  |
| Primeiro orientador: | Faria, Luerbio |
| Segundo orientador: | Santos, Vinicius Fernandes dos |
| Primeiro membro da banca: | Masquio, Bruno Porto |
| Segundo membro da banca: | Iazzetta, Fernando Henrique de Oliveira |
| Terceiro membro da banca: | Souza, Uéverton dos Santos |
| Resumo: | Arranjos musicais têm sido tratados recentemente do ponto de vista combinatório. Demaine e Moses em 2017[1], consideraram três problemas de decisão associados a arranjos musicais.Esses problemas consideram uma partitura com um número dado de pautas correspondentes aos instrumentos participantes. O objetivo é selecionar um certo número de pautas que atendam a algumas propriedades musicais específicas. Nessa dissertação, definimos versões mais gerais dos três problemas originais de Demaine e Moses, as quais chamamos arranjo-consonante geral, j-notas simultâneas geral e velocidade de transição limitada geral. Demonstramos a NP-completude para os novos problemas a partir de max3 sat3 e grau máximo 4 conjunto independente, problemas cujas versões de otimização são MAX3SAT - e grau máximo 4 conjuntos independente, problemas cujas completos. A relação entre os ótimos nessas provas permitiram mostrar que as versões de otimização correspondentes dos 3 problemas são MAXSNP-difíceis e que portanto,não admitem Esquema de Aproximação Tempo Polinomial a menos que P=NP. Provamos que o problema j-notas simultâneas é não aproximável por uma razão de aproximação inferiora n1−ε, para nenhum ϵ > 0. Além disso,demonstramos que,quando no máximo 4 instrumentos tocam simultaneamente cada tempo,o problema se torna FPT (tratável por parâmetro fixo)em relação ao tamanho k da solução. Dois novos problemas de decisão foram introduzidos arranjo para k instrumentos e preenchimento de tempos por instrumentos. Os dois novos problemas foram provados serem NP-completos,respectivamente,através de reduções k-coloração e cobertura de vértices. O problema preenchimento de tempos por instrumentos também foi demonstrado ser FPT no parâmetro τ – o número máximo de pautas que toca em cada tempo. |
| Abstract: | Musical arrangementshaverecentlybeenconsideredfromacombinatorialpoint of view.DemaineandMosesin2017[1] statedthreedecisionproblemsassociatedwith musicalarrangements.Theseproblemsinputascorewithagivennumberofstavescor- respondingtotheparticipatinginstruments.Thegoalistoselectacertainnumberof stavessuchthattheymeetsomespecificmusicalproperties.Inthisdissertation,wede- fine moregeneralversionsofDemaineandMoses’threeoriginalproblems,whichwecall general consonantarrangement, general j-simultaneousnotes and general limitedtransitionspeed. WeprovetheNP-completenessforthenewproblems from max3sat3 and maximum degree4independentset, problemswhoseoptimi- zation versionsareMAXSNP-complete.Therelationshipbetweentheoptimainthese problems allowedustoshowthatthecorrespondingoptimizationversionsofthe3pro- blems areMAXSNP-hardandthereforedonotallowPolynomialTimeApproximation SchemeunlessP=NP.Weprovethattheproblem general j-simultaneousnotes is notapproximablebyanapproximationratiolowerthan n1−ε, forany ε > 0, unless P=NP andwhenateachtimeamaximumof4instrumentsplay,then general jsimultaneousnotes is FPT(FixedParameterTractable)withrespecttothesize k of the solution.Twonewdecisionproblemsareintroducedhere:the arrangement for k instruments and the time fillingbyinstruments. Thetwonewproblemsare proventobeNP-completethrough,respectively,reductionsfrom k-coloring and from vertexcover. Theproblem time fillingbyinstruments is proventobeFPTwith respectto τ – themaximumnumberofstavesplayingeachtime. |
| Palavras-chave: | Musical arrangement NP-complete Approximation Arranjo musical NP-completo Aproximação Complexidade computacional Arranjo (Música) |
| Área(s) do CNPq: | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | Brasil |
| Instituição: | Universidade do Estado do Rio de Janeiro |
| Sigla da instituição: | UERJ |
| Departamento: | Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística |
| Programa: | Programa de Pós-Graduação em Ciências Computacionais |
| Citação: | FIGUEIREDO, Natan. Problemas Computacionais de Arranjo Musical. 2024. 88 f. Dissertação (Mestrado em Ciências Computacionais) - Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2024. |
| Tipo de acesso: | Acesso Aberto |
| URI: | http://www.bdtd.uerj.br/handle/1/23602 |
| Data de defesa: | 26-Fev-2025 |
| Aparece nas coleções: | Mestrado em Ciências Computacionais |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Dissertação - Natan Figueiredo - 2024 - Completa.pdf | Dissertação completa | 3,65 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
| Termo - Natan Figueiredo - 2024.pdf | 374,7 kB | Adobe PDF | Baixar/Abrir Pré-Visualizar Solictar uma cópia | |
| CRN - Natan Figueiredo - 2024.pdf | 240,79 kB | Adobe PDF | Baixar/Abrir Pré-Visualizar Solictar uma cópia |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.