This textbook covers the mathematical foundations of the analysis of algorithms. The gist of the book is how to argue, without the burden of excessive formalism, that a given algorithm does what it is supposed to do. The two key ideas of the proof of correctness, induction and invariance, are employed in the framework of pre/post-conditions and loop invariants.
The algorithms considered are the basic and traditional algorithms of computer science, such as Greedy, Dynamic and Divide & Conquer. In addition, two classes of algorithms that rarely make it into introductory textbooks are discussed. Randomized algorithms, which are now ubiquitous because of their applications to cryptography; and Online algorithms, which are essential in fields as diverse as operating systems (caching, in particular) and stock-market predictions.
This self-contained book is intended for undergraduate students in computer science and mathematics.
Płać wygodnie kartą, Klarną, Apple Pay lub Google Pay. Nie jesteś zadowolony? Zawsze masz 14-dniową gwarancję zwrotu pieniędzy. Więcej przeczytasz w naszych warunkach. Masz pytania? Napisz do nas na hello@memmo.org.
Memmo ułatwia naukę – gdziekolwiek jesteś na świecie. U nas znajdziesz podręczniki i sprytne narzędzia do nauki w jednym miejscu: streszczenia, quizy, podcasty i fiszki. A do tego Ted, Twój kumpel do nauki, który odpowie na wszystko, co Cię nurtuje. Ponad 50 000 studentów już tu się uczy – stworzone, byś uczył się szybciej i mniej stresował.