NP-ТОЛЫҚ ЕСЕПТЕР АЛГОРИТМДЕРІ. I-БӨЛІМ

Жұмыста элементтерінің қосындысы берілген S сертификатына тең, оң бүтін сандардан тұратын n-элементті жиын үшін ішкі жиындар қосындысы есебінің параметрленген тұжырымдамасы қарастырылады. Индекстік сертификаттар мен екі өлшемді массивтер негізінде қуаттылығы (элемент саны) k-ға тең ішкі жиындарды құру әдісі ұсынылған. Бұл әдіс толық іріктеусіз (перебор) ішкі жиындарды тиімді таңдауға мүмкіндік береді. Негізгі идея элементтердің мәндерінен индекстік кеңістікке өтуге және массивтердің құрылымдалған диагональдарын пайдалануға негізделген. Бұл k мәні бекітілген жағдайда есептеулердің практикалық күрделілігін азайтады. Жұмыста қуаттылығы жұп болатын ішкі жиындарды құру алгоритмдері ұсынылып, олардың ақпаратты іздеу, үлкен деректерді өңдеу, сондай-ақ өңдеу жылдамдығы мен жадты ұтымды пайдалану маңызды рөл атқаратын құрылымдалмаған ақпаратты іздеу есептеріндегі тиімділігі көрсетілген. Алынған нәтижелер есептің шектеулі әрі параметрленген нұсқасына ғана қатысты екені және жалпы тұжырымдамадағы белгілі NP-толықтық теориясына қайшы келмейтіні атап өтілген.

1. Bellman R. Notes on the theory of dynamic programming IV – maximization over discrete sets // Naval Research Logistics Quarterly. – 1956. – Vol. 3, № 1–2. – P. 67–70.

2. Pisinger D. Linear time algorithms for knapsack problems with bounded weights // Journal of Algorithms. – 1999. – Vol. 33, № 1. – P. 1–14.

3. Koiliaris K., Xu C. A faster pseudopolynomial time algorithm for subset sum // To appear in SODA ’17. – 2017. – 18 p. – URL: https://arxiv.org/abs/1610.04712v2.

4. Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum // To appear in SODA’17. – 2017. – 18p. – URL: https://arxiv.org/abs/1610.04712v2.

5. Horowitz E., Sanni S. Computing partitions with application to the knapsack problem // Journal of the ACM (JACM). – 1974. – Vol. 21. – P. 277–292.

6. Schroeppel R., Shamir A. A T=O(2^n/2), S=O(2^n/4) algorithm for certain NP-complete problem // SIAM Journal on Computing. – 1981. – Vol. 10, № 3. – P. 456–464.

7. Cobham A. The intrinsic computational difficulty of functions // Proceedings of the Congress for Logic, Methodology and Philosophy of Science. – North-Holland, 1964. – P. 24–30.

8. Egmonds J. Paths, trees and flowers // Canadian Journal of Mathematics. – 1965. – Vol. 17. – P. 449–467.

9. Николаев А.В. Геометрический подход к задаче о разрезе. – Ярославль: ЯрГУ, 2014. – 68 с.

10. Ivan Rijsbergen C.J. Information Retrieval. – Glasgow: Dept. of Computer Science, University of Glasgow, 1979.

11. Adamansky A. Overview of full-text search methods and algorithms. – Novosibirsk: Novosibirsk State University, 2018. – 26 p.

12. Chen M., Mao S., Zhang Y., Leung V.C.M. Big Data. Related Technologies, Challenges, and Future Prospects. – Springer, 2014. – 100 p.

13. Лифшиц Ю. Точные алгоритмы и открытые проблемы // Современные задачи теоретической информатики. – URL: http://download.yandex.ru/class/...

14. Куликов А. Алгоритмы NP-трудных задач. Лекции. – СПб: Computer Science клуб СПб отделения МИАН, 2009.

15. Sinchev B., Sinchev A.B., Akzhanova J., Mukhanova A.M. New methods of information search. I // News of the National Academy of Sciences of Kazakhstan. Series of Geology and Technical Sciences. – 2019. – Vol. 3, № 435. – P. 240–246.

16. Sinchev B., Sinchev A.B., Akzhanova Z.A. Computing network architecture for reducing computing operation time and memory usage… // Патент USPTO. – 2019. – 38 p.

17. Akl S.G. Adaptive and optimal algorithms for enumerating permutations and combinations // The Computer Journal. – 1987. – Vol. 30. – P. 433–436.

18. Hoare C.A.R. Quicksort // The Computer Journal. – 1962. – Vol. 5. – P. 10–16.

19. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс, 2005.