Kategorie: Algorithms

Computer graphics

Computer graphics is a field within computer science that deals with the display of graphical elements on monitors and the processing of the corresponding data. The area of 3-dimensional representation and corresponding processing is particularly important because the goal is to render a 3D scene on a 2D screen.

Dynamic Programming

Dynamic programming is an optimization technique that utilizes recursion and specific rules to address, for example, NP-hard problems. The concept involves storing solutions for subproblems and reusing them when necessary, rather than recalculating their values. This approach frequently transforms the runtime complexity from exponential to polynomial, enhancing computational efficiency. Rules of dynamic programming When describing an algorithm it is defined as a dynamic algorithm if the following principles of optimization are suitable for it: =>A problem can be broken down to subproblems and is solved only once =>The solution of a subproblem might help you finding a feaseable solution for…

Rekurrenzen und Master-Theorem

Das nächste Thema im Bereich der Algorithmusentwicklung oder -beschreibung behandelt Rekurrenzen. Diese stellen ein mathematisches Konzept dar, um Laufzeiten rekursiver Algorithmen zu beschreiben. Insbesondere werden mit Hilfe von Rekurrenzen Algorithmen beschrieben, die dem Prinzip „Teile und herrsche“ folgen. In diesem Artikel werde ich detailliert erläutern, was dies bedeutet und wie man die Laufzeit solcher Algorithmen bestimmen kann. Für diesen Algorithmus ist es sinnvoll, wenn bereits Wissen zur O-Notation vorhanden ist. Andererseits habe ich hier einen Artikel zur O-Notation und Laufzeitanalyse von Algorithmen. Rekurrenzgleichungen Eine Rekurrenzgleichung hat folgende Struktur. Sie beinhaltet die 4 Konstanten a,b,c,d die alle positiv sein müssen. N…

Laufzeit von Algorithmen beweisen

Um Laufzeiten für Algorithmen anzugeben, benutzt man die O-Notation. Mit dieser Notation kann man Grenzen angeben. Man kann zum Beispiel eine obere Grenze oder auch untere Grenze angeben. Damit legt man einfach fest, dass ein Algorithmus entweder maximal oder mindestens so viel Zeit braucht.