OPTYMALIZACJA PROBLEMU NAJWIĘKSZEJ PODTABLICY DLA SPECYFICZNYCH DANYCH
Tomasz Rojek
trojek@pk.edu.plCracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics (Polska)
Abstrakt
Problem najwiekszej podtablicy to inaczej znalezienie podciągu, którego suma na największą wartość. Artykuł opisuje optymalizację algorytmu Kadane dla specyficznych danych (z powtarzającymi się ciągami zer lub liczb negatywnych). W przypadku niekorzystnych danych wejściowych zaproponowa modyfikacja nieznacznie spowalnia działanie algorytmu (mniej niż 1% szybkości działania). Ulepszenie algorytmu nie zmienia rzędu asymptotycznego tempa wzrostu, lecz zmniejsza ilość elementarnych operacji. Eksperymenty wykazały, że dla sprzyjających danych możemy zmniejszyć efektywny czas działania algorytmu o 25%.
Słowa kluczowe:
analiza i projektowanie algorytmów, problem maksymalnej podtablicy, algorytm Kadane, optymalizacjaBibliografia
Lloyd A.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19, 2003, 1294–1295.
Google Scholar
Bae Sung Eun: Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Ph.D. Thesis, University of Canterbury, 2007.
Google Scholar
Bentley J.: Programming pearls: algorithm design techniques. Communications of the ACM, 27(9), 1984, 865–873.
Google Scholar
BT Series Broadcasting. Parameter values for the HDTV standards for production and international programme exchange BT Series Broadcasting service – volume 5, 2002.
Google Scholar
Grenander U.: Pattern analysis. Springer, 1978.
Google Scholar
Huang X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Computer applications in the biosciences: CABIOS 10, 1994, 219–225.
Google Scholar
Larson R. C., Odoni A. R.: Urban operations research. Prentice-Hall, New Jersey 1981.
Google Scholar
Lin Yaw Ling, Jiang Tao, Chao Kun Mao: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. Journal of Computer and System Sciences 65, 2003, 570–586.
Google Scholar
Perumalla K., Deo N.: Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters 5(03), 1995, 367–373.
Google Scholar
Tokyo IBM: Data Association Mining Rules: Using Algorithms, Optimized and Scheme, Visualization, 1996.
Google Scholar
Wang L., Xu Ying: SEGID: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics 19, 297–298, 2003.
Google Scholar
Autorzy
Tomasz Rojektrojek@pk.edu.pl
Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics Polska
Statystyki
Abstract views: 191PDF downloads: 240
Licencja
Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa – Na tych samych warunkach 4.0 Miedzynarodowe.
