Contents |
Now that we have seen several simple algorithms, which were illustrative in the sense that, although useful indeed, they were all pretty basic, we can delve now into more complicated problems to get an idea of how complex an algorithm typically looks like. We will consider important problems, namely:
The first one is a natural extension of our very first algorithm: finding the largest element of a list, which we have seen is both simple to implement and is very efficient: go through the list and retain the largest one. What if we would like the second largest? Or count how many largest element there are (degeneracy)? Or find the median? All this requires sorting, which is a basic problem that is not, however, so simply achieved. It is also a problem very much studied, due to its importance, and that counts a considerable amount of variations, so a nice ground of study and a perfect starting point if you want to investigate further.
The second problem, encryption, is important for Physics as it applies to data notions of order, entropy, etc., which are initially Physical concepts (borrowed from Thermodynamics). It so happens that these notions are more fundamentally rooted in data-information and computer-science, but this was realized a posteriori, and they remain important in Physics so it is worth considering them at the algorithmic level.
The third problem, cryptography, is also relevant to Physics given the emergence of quantum cryptography, which brings to computer science new resources to tackle problems. In particular, we will show in Modern Physics that quantum technology promise a way to break today's most popular schemes of encryption, known as RSA, using quantum algorithms (namely, Shor's algorithm) in a way that is not possible with classical physics, hence the interest in building a so-called quantum computer. To understand well the quantum aspects of this problem, we will need to also understand its classical implementation, which is a scientific-computing task that we study as part of this Lecture.
This page is still largely in progress.
See Cryptography.