Download Algorithmische Konzepte der Informatik: Berechenbarkeit, by Juraj Hromkovic PDF

By Juraj Hromkovic

ISBN-10: 3519003325

ISBN-13: 9783519003328

Das Buch versteht sich als eine einfache Einf?hrung in die grundlegenden algorithmischen Konzepte der Informatik. Die Konzepte werden in ihrer historischen Entwicklung und gr??eren Zusammenh?ngen dargestellt, um so die eigentliche Faszination der Informatik, die viel kontraintuitive ?berraschungen bereith?lt, zu wecken.

Show description

Read Online or Download Algorithmische Konzepte der Informatik: Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung PDF

Similar german_4 books

Technische Hydraulik: Kompendium für den Wasserbau

Dieses Kompendium ist sowohl als Nachschlagewerk, Formel- und Beispielsammlung f? r den Ingenieur im Beruf, aber auch als kurzes, umfassendes Lehrbuch f? r Studenten des Bauingenieurwesens geeignet. Es behandelt die Grundlagen, wie sie in den Pflichtvorlesungen im Grundstudium gelehrt werden, aber auch den fortgeschrittenen Lehrstoff des Hazpt- und Vertiefungsstudiums.

Systemtechnik des Schienenverkehrs: Bahnbetrieb planen, steuern und sichern

Dieses Lehrbuch vermittelt das aktuelle Basiswissen der Eisenbahnbetriebslehre in Verbindung mit den betrieblichen Funktionalit? ten der Leit- und Sicherungstechnik. Es beschreibt prozessorientiert die ma? gebenden Systemeigenschaften des Schienenverkehrs. Die neue four. Auflage enth? lt zahlreiche Verbesserungen und wurde u.

Die Blechabwicklungen: Eine Sammlung praktischer Verfahren und ausgewählter Beispiele

Die Bibel für "Abwickler": Das Standardwerk zur Abwicklungsgeometrie nicht nur für den Blechbüchsenproduzenten, sondern auch zur optimierten Materialnutzung für Leder-, Papier- und Furnierbearbeiter.

Additional resources for Algorithmische Konzepte der Informatik: Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung

Example text

3) Das Wort(m, n/Pm) betrachten wir jetzt als die Komprimierung von Bin(n). 22, dass für alle i E IN - {O} für mehr als die Hälfte aller Zahlen n aus {2 i , 2i + 1, ... , 2i +1 - 1} die Länge von Wort(m,n/Pm) mindestens pogn1-1 ist. Analog hat mehr als die Hälfte der Zahlen aus {2 i , 2i + 1, ... , 2i+I_1} die Kolmogorov-Komplexität von mindestens POg2 n1- 2. Damit erhalten wir, dass für alle i E IN - {O} eine n- < 2i+l - 1, mit Zahl n-l ' 2i < _ _ ~ und existiert. 3) einsetzen, erhalten wir POg2 n 1 - 1 ~ 2 rlog2 POg2 rlog2 m 111 +pog2Pog2 m11 + pog2 m 1 + Pog2(n/Pm)l Daraus folgt log2 Pm < 2· POg2 log2 log2 m1 + POg2 log2 m 1 + POg2 m1 + 1 < 2 ·log2log2log2 m + log2log2 m + log2 m + 5.

Begin for i = 1 to n do write(O) ; end Alle Programme Yn sind gleich bis auf das n. Die Kosten für die binäre Kodierung Bin( n) von n sind pog2 n 1- Daher kann man behaupten, dass eine Konstante c existiert, so dass K(Yn) ~ POg2 n 1+ c = Pog21Ynil +c für alle nEIN - {O}. 19. 20. B. ohne Variablendeklaration auskommt. 4 Kolmogorov-Komplexität 53 Wir können auch den Informationsgehalt von Zahlen messen, wenn wir die Messung der Kolmogorov-Komplexität an ihrer Binärdarstellung durchführen. 17. Die Kolmogorov-Komplexität einer natürlichen Zahl ist K(n) = K(Bin(n)).

Finden Sie zwei Wörter x, y E (E boo1 )*, so dass (i) die Komprimierungsmethode der Teilwörterpotenzen eine wesentlich kürzere Darstellung für x als die Methode der Primzahlzerlegung liefert und (ii) die Komprimierungsmethode der Primzahlzerlegung für y zu einer wesentlich kürzeren Darstellung führt als die Methode der Teilwörterpotenzen. Eine Definition des Komplexitätsmaßes muss robust sein in dem Sinne, dass die gemessene Komplexität eine breite Gültigkeit hat und daher unter unterschiedlichen Rahmenbedingungen genutzt werden kann.

Download PDF sample

Rated 4.28 of 5 – based on 22 votes