REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

  1. Repozytorium Uniwersytetu w Białymstoku
  2. Czasopisma naukowe / Journals
  3. Formalized Mathematics
  4. Formalized Mathematics, 2020, Volume 28, Issue 1

Szukanie zaawansowane
  • Zespoły i Kolekcje


  • Zaloguj się
  • Zarejestruj się
  • Mój RUB
  • FAQ
  • Polityka
  • Regulamin
  • DOI
  • Instrukcja
  • Aspekty prawne
  • Open Access
  • Archiwum


  • Kontakt
  • O Dspace
  • Strona Biblioteki
  • Strona Uczelni



    • Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/9225
    Pełny rekord metadanych
    Pole DCWartośćJęzyk
    dc.contributor.authorFujiwara, Hiroshi-
    dc.contributor.authorWatari, Hokuto-
    dc.contributor.authorYamamoto, Hiroaki-
    dc.date.accessioned2020-06-10T11:23:43Z-
    dc.date.available2020-06-10T11:23:43Z-
    dc.date.issued2020-
    dc.identifier.citationFormalized Mathematics, Volume 28, Issue 1, Pages 89-92pl
    dc.identifier.issn1426-2630-
    dc.identifier.urihttp://hdl.handle.net/11320/9225-
    dc.description.abstractThe subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory [3]. The input is a sequence of positive integers and a target positive integer. The task is to determine if there exists a subsequence of the input sequence with sum equal to the target integer. It is known that the problem is NP-hard [2] and can be solved by dynamic programming in pseudo-polynomial time [1]. In this article we formalize the recurrence relation of the dynamic programming.pl
    dc.description.sponsorshipThis work was supported by JSPS KAKENHI Grant Numbers JP16K00033, JP17K00013 and JP17K00183.pl
    dc.language.isoenpl
    dc.publisherDeGruyter Openpl
    dc.rightsUznanie autorstwa-Na tych samych warunkach 3.0 Polska*
    dc.rights.urihttp://creativecommons.org/licenses/by-sa/3.0/pl/*
    dc.subjectdynamic programmingpl
    dc.subjectsubset sum problempl
    dc.subjectcomplexity theorypl
    dc.titleDynamic Programming for the Subset Sum Problempl
    dc.typeArticlepl
    dc.identifier.doi10.2478/forma-2020-0007-
    dc.description.AffiliationHiroshi Fujiwara - Shinshu University, Nagano, Japanpl
    dc.description.AffiliationHokuto Watari - Nagano Electronics Industrial Co., Ltd., Chikuma, Japanpl
    dc.description.AffiliationHiroaki Yamamoto - Shinshu University, Nagano, Japanpl
    dc.description.referencesMichael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. ISBN 0716710447.pl
    dc.description.referencesRichard M. Karp. Reducibility among combinatorial problems. In Miller et al. [3], pages 85–103. ISBN 978-1-4684-2001-2. doi:10.1007/978-1-4684-2001-2_9.pl
    dc.description.referencesRaymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors. Complexity of Computer Computations, 1972. Springer US. ISBN 978-1-4684-2001-2. doi:10.1007/978-1-4684-2001-2_9.pl
    dc.description.referencesWojciech A. Trybulec. Non-contiguous substrings and one-to-one finite sequences. Formalized Mathematics, 1(3):569–573, 1990.pl
    dc.identifier.eissn1898-9934-
    dc.description.firstpage89pl
    dc.description.lastpage92pl
    dc.identifier.citation2Formalized Mathematicspl
    Występuje w kolekcji(ach):Formalized Mathematics, 2020, Volume 28, Issue 1

    Pliki w tej pozycji:
    Plik Opis RozmiarFormat 
    forma_2020_28_01_0007.pdf225,56 kBAdobe PDFOtwórz
    Pokaż uproszczony widok rekordu Zobacz statystyki


    Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL Creative Commons