Seminar im Wintersemester 2018/2019
Görschwin Fey und Gianluca Martino
Datenstrukturen, Algorithmen und deren effiziente Implementierung
Praktische Anwendungen von Algorithmen sind allgegenwärtig: In der Produktion und in anderen kommerziellen Umgebungen ist es oft wichtig, knappe Ressourcen auf die günstigste Weise zuzuweisen. Eine Ölgesellschaft möchte beispielsweise wissen, wo sie ihre Brunnen platzieren muss, um den erwarteten Gewinn zu maximieren. Ein Kandidat für die Präsidentschaft könnte bestimmen wollen, wo er Geld für Werbung ausgeben soll, um die Chancen auf den Gewinn einer Wahl zu maximieren. Eine Fluggesellschaft möchte beispielsweise Besatzungen den Flügen auf die kostengünstigste Art und Weise zuweisen, um sicherzustellen, dass jeder Flug abgedeckt ist und dass die alle Vorschriften bezüglich der Crew-Planung eingehalten werden.
Eine geeignete Auswahl von Datenstrukturen kann die Effizienz des Algorithmus beschleunigen und auch beim Entwurf von Algorithmen zu einer klaren Struktur beitragen. Es ist daher selbstverständlich, dass Datenstrukturen und Algorithmen zusammen betrachtet werden. Während des Seminars wird über einige interessante Algorithmen in der Geschichte der Computerprogrammierung und deren Implementierung in C++ diskutiert.
Algorithms, Data Structures, and their Efficient Implementation
Practical applications of algorithms are ubiquitous: In manufacturing and other commercial settings, it is often important to allocate scarce resources in the most beneficial way. An oil company may wish to know where to place its wells in order to maximize its expected profit. A candidate for the presidency may want to determine where to spend money buying campaign advertising in order to maximize the chances of winning an election. An airline may wish to assign crews to flights in the least expensive way possible, making sure that each flight is covered and that government regulations regarding crew scheduling are met.
Appropriate choices of data structures can expedite algorithm efficiency and also aid clear thinking when designing algorithms. It is thus natural for data structures to be studied with algorithms.
During the seminar we will discuss some of the most interesting algorithms in the history of computer programming and their implementation in C++.
Basic references:
Knuth, D.E., 2011. The Art of Computer Programming, Volumes 1-4A Boxed Set. Addison-Wesley Professional.
C++ standard (ISO/IEC 14882: 2017)
Topics:
Hash maps:
Czech, Z.J., Havas, G. and Majewski, B.S., 1992. An optimal algorithm for generating minimal perfect hash functions. Information processing letters, 43(5), pp.257-264.
Shortest path in graphs:
Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4. 4 (2): 100–107. doi:10.1109/TSSC.1968.300136.
Search in strings:
Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing. 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . doi:10.1137/0206024.
Boyer, Robert S.; Moore, J Strother (October 1977). "A Fast String Searching Algorithm". Comm. ACM. New York, NY, USA: Association for Computing Machinery. 20 (10): 762–772. doi:10.1145/359842.359859. ISSN 0001-0782.
Maximum matching in graphs:
Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4.
Fast Fourier Transform:
Cooley, James W.; Tukey, John W. (1965). "An algorithm for the machine calculation of complex Fourier series". Mathematics of Computation. 19 (90): 297–301. doi:10.1090/S0025-5718-1965-0178586-1. ISSN 0025-5718.
Disjoint-set:
Galler, Bernard A.; Fischer, Michael J. (May 1964). An improved equivalence algorithm. Communications of the ACM. 7. pp. 301–303. doi:10.1145/364099.364331.
Fast Inverse Square Root:
Walczyk, C.J., Moroz, L.V. and Cieśliński, J.L., 2018. Improving the accuracy of the fast inverse square root algorithm. arXiv preprint arXiv:1802.06302.
Minimum Spanning Tree:
Pettie, S. and Ramachandran, V., 2002. An optimal minimum spanning tree algorithm. Journal of the ACM (JACM), 49(1), pp.16-34.
Fibonacci Heap:
Fredman, M.L. and Tarjan, R.E., 1987. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), pp.596-615.
Lossless compression:
Ziv, Jacob; Lempel, Abraham (September 1978). "Compression of Individual Sequences via Variable-Rate Coding". IEEE Transactions on Information Theory. 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . doi:10.1109/TIT.1978.1055934.
