Das Buch "Klassische Informatik Aufgaben in Python"

Viele Aufgaben auf dem Gebiet der Informatik, die auf den ersten Blick neu oder einzigartig erscheinen, wurzeln tatsächlich in klassischen Algorithmen, Codierungsmethoden und Entwicklungsprinzipien. Und etablierte Techniken sind immer noch der beste Weg, um solche Probleme zu lösen!

Das Buch bietet Ihnen die Möglichkeit, die Python-Sprache besser zu lernen und sich an bewährten Aufgaben, Übungen und Algorithmen zu testen. Sie müssen Dutzende von Programmieraufgaben lösen: von der einfachsten (z. B. Auffinden von Listenelementen mithilfe der binären Sortierung) bis zu komplexen Aufgaben (Clustering von Daten mithilfe der k-means-Methode). Anhand von Beispielen für Suche, Clustering, Grafiken usw. werden Sie sich an das erinnern, was Sie vergessen haben, und die klassischen Techniken zur Lösung alltäglicher Probleme beherrschen.

Für wen ist dieses Buch?

Dieses Buch richtet sich an Programmierer mittlerer und hoher Ebene. Erfahrene Fachleute, die ihre Kenntnisse in Python vertiefen möchten, finden hier Aufgaben, die aus der Zeit bekannt sind, als sie Informatik oder Programmierung unterrichteten. Programmierer auf mittlerer Ebene werden mit diesen klassischen Aufgaben in der von ihnen gewählten Sprache - Python - vertraut gemacht. Für Entwickler, die sich auf ein Programmierinterview vorbereiten, wird die Veröffentlichung wahrscheinlich zu wertvollem Vorbereitungsmaterial.

Zusätzlich zu professionellen Programmierern kann dieses Buch von Studenten als nützlich angesehen werden, die für Bachelor-Programme in Informatik studieren und sich für Python interessieren. Es wird nicht behauptet, eine strenge Einführung in Datenstrukturen und Algorithmen zu sein. Dies ist kein Tutorial zu Datenstrukturen und Algorithmen. Sie werden auf seinen Seiten keinen Beweis für Theoreme oder die häufige Verwendung von O-Big-Notationen finden. Im Gegenteil, dieses Buch ist als zugänglicher praktischer Leitfaden für Methoden zur Lösung von Problemen positioniert, die das Endprodukt der Untersuchung der Datenstruktur, Algorithmen und Klassen künstlicher Intelligenz werden sollten.

Ich betone noch einmal: Es wird davon ausgegangen, dass die Leser mit der Syntax und Semantik von Python vertraut sind. Es ist unwahrscheinlich, dass ein Leser mit null Programmiererfahrung von diesem Buch profitiert, und ein Programmierer mit null Erfahrung in Python wird wahrscheinlich schwierig sein. Mit anderen Worten, „Klassische Informatikaufgaben in Python“ ist ein Buch für Python-Programmierer und Informatikstudenten.

Auszug. 1.5. Hanoi Türme

Es gibt drei hohe vertikale Säulen (im Folgenden: Türme). Wir werden sie als A, B und C bezeichnen. Scheiben mit Löchern in der Mitte sind auf Turm A aufgereiht. Die breiteste Scheibe - wir nennen sie Scheibe 1 - befindet sich unten. Die verbleibenden darüber befindlichen Scheiben werden durch zunehmende Anzahl angezeigt und verjüngen sich allmählich. Wenn wir beispielsweise drei Festplatten hätten, hätte die breiteste davon, die darunter liegende, die Nummer 1. Die nächstbeste Festplatte mit der Nummer 2 befindet sich über der Festplatte 1. Schließlich die engste Festplatte mit der Nummer 3 würde auf Scheibe 2 liegen.

Unser Ziel ist es, alle Laufwerke von Turm A nach Turm C zu verschieben, wobei die folgenden Einschränkungen zu berücksichtigen sind.

• Festplatten können jeweils nur einzeln verschoben werden.
• Das einzige Laufwerk, das zum Bewegen zur Verfügung steht, befindet sich oben auf einem Turm.
• Ein breiteres Laufwerk kann niemals auf ein schmaleres Laufwerk gelegt werden.
  Schematisch ist die Aufgabe in Abb. 2 dargestellt. 1.7.

1.5.1. Turmmodellierung

Ein Stapel ist eine Datenstruktur, die nach dem LIFO-Prinzip (Last-In-First-Out) modelliert ist. Das Letzte, was auf den Stapel kommt, wird das erste, das von dort abgerufen wird. Die beiden Hauptoperationen des Stapels sind Push (Put) und Pop (Extract). Durch die Push-Operation wird ein neues Element auf den Stapel verschoben, und Pop entfernt es vom Stapel und gibt das zuletzt eingefügte Element zurück. Sie können den Stapel in Python einfach modellieren, indem Sie die Liste als Sicherungsspeicher verwenden (Listing 1.20).


Listing 1.20. hanoi.py

from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container) 

Die vorgestellte Stack-Klasse implementiert die Methode __repr __ (), mit der sich der Inhalt des Turms leicht untersuchen lässt. __repr __ () wird ausgegeben, wenn die Funktion print () auf den Stapel angewendet wird.

Wie in der Einleitung angegeben, werden im Buch Typanmerkungen verwendet. Durch das Importieren von Generic aus einem Eingabemodul kann Stack eine parametrische Klasse für einen bestimmten Typ in Typanmerkungen sein. Ein beliebiger Typ T ist in T = TypeVar ('T') definiert. T kann ein beliebiger Typ sein. Wenn die Typanmerkung anschließend für Stack zur Lösung des Hanoi-Turmproblems verwendet wird, lautet die Eingabeaufforderung Stack [int], dh, der Typ int wird anstelle von T verwendet. Mit anderen Worten, hier ist der Stapel ein Stapel von ganzen Zahlen. Wenn Sie Probleme mit Typanmerkungen haben, lesen Sie Anhang B.

Stapel sind perfekt für die Hanoi Tower Challenge. Um die Scheibe zum Turm zu bewegen, können wir die Push-Operation verwenden. Um die Scheibe von einem Turm zum anderen zu bewegen, können wir sie vom ersten (Pop) schieben und auf den zweiten legen (Push).

Definieren Sie die Türme als Stapelobjekte und füllen Sie den ersten mit Datenträgern (Listing 1.21).

Listing 1.21. hanoi.py (Fortsetzung)

 num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i) 

1.5.2. Das Problem der Hanoi-Türme lösen

Wie kann ich das Problem der Hanoi-Türme lösen? Angenommen, wir versuchen, nur ein Laufwerk zu verschieben. Dann würden wir wissen, wie das geht, oder? Tatsächlich ist das Verschieben einer Festplatte ein grundlegender Fall für eine rekursive Lösung dieses Problems. Das Verschieben mehrerer Laufwerke ist ein rekursiver Fall. Der entscheidende Punkt ist, dass wir tatsächlich zwei Szenarien haben, die codiert werden müssen: Verschieben einer Festplatte (Basisfall) und Verschieben mehrerer Festplatten (rekursiver Fall).

Betrachten Sie ein bestimmtes Beispiel, um den rekursiven Fall zu verstehen. Angenommen, wir haben drei Festplatten - die obere, mittlere und untere, die sich auf Turm A befinden, und wir möchten sie auf Turm C verschieben. (Dies hilft anschließend, das Problem schematisch zu beschreiben.) Zuerst könnten wir die obere Festplatte auf Turm C verschieben. Dann - Bewegen Sie die mittlere Scheibe zu Turm B und dann die obere Scheibe von Turm C zu Turm B. Jetzt befindet sich die untere Scheibe noch auf Turm A und die beiden oberen Scheiben auf Turm B. Im Wesentlichen haben wir bereits zwei erfolgreich verschoben Fahren Sie von einem Turm (A) zum anderen (B). Das Verschieben der unteren Festplatte von A nach C ist der Grundfall (Verschieben einer Festplatte). Jetzt können wir die beiden oberen Platten von B nach C auf die gleiche Weise wie von A nach B verschieben. Wir verschieben die obere Platte nach A, die mittlere Platte nach C und schließlich die obere Platte von A nach C.

Im Informatikunterricht werden häufig kleine Modelle dieser Türme gefunden, die aus Stiften und Plastikscheiben gebaut sind. Sie können Ihr eigenes Modell mit drei Stiften und drei Blatt Papier erstellen. Vielleicht hilft Ihnen dies, die Lösung zu visualisieren.

In dem Beispiel mit drei Festplatten gab es einen einfachen Grundfall für das Verschieben einer Festplatte und einen rekursiven Fall für das Verschieben der verbleibenden Festplatten (in diesem Fall zwei) mithilfe eines temporären dritten Turms. Wir können den rekursiven Fall in die folgenden Schritte unterteilen.

1. Bewegen Sie die oberen n - 1 Laufwerke von Turm A zu Turm B (vorübergehend), wobei Sie C als Zwischenturm verwenden.
2. Bewegen Sie den unteren Antrieb von A nach C.
3. Bewegen Sie n - 1 Scheiben von Turm B zu Turm C, Turm A ist dazwischen.

Überraschenderweise funktioniert dieser rekursive Algorithmus nicht nur für drei, sondern für eine beliebige Anzahl von Festplatten. Codieren Sie es als hanoi () -Funktion, die für das Verschieben von Festplatten von einem Turm zu einem anderen mithilfe eines dritten temporären Turms verantwortlich ist (Listing 1.22).

Listing 1.22. hanoi.py (Fortsetzung)

 def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1) 

Nach dem Aufruf von hanoi () müssen Sie die Türme A, B und C überprüfen, um sicherzustellen, dass die Festplatten erfolgreich verschoben wurden (Listing 1.23).

Listing 1.23. hanoi.py (Fortsetzung)

 if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c) 

Sie werden feststellen, dass die Laufwerke tatsächlich verschoben wurden. Bei der Codierung der Lösung für das Hanoi-Tower-Problem ist es nicht erforderlich, jeden Schritt zu verstehen, der zum Verschieben mehrerer Festplatten von Turm A zu Turm C erforderlich ist. Wir haben den allgemeinen rekursiven Algorithmus zum Verschieben einer beliebigen Anzahl von Festplatten verstanden und ihn systematisiert, sodass der Computer den Rest erledigen kann. Dies ist die Kraft, rekursive Lösungen für Probleme zu formulieren: Wir können uns oft abstrakte Lösungen vorstellen, ohne Energie für die mentale Repräsentation jeder einzelnen Handlung zu verschwenden.

Übrigens wird die Funktion hanoi () abhängig von der Anzahl der Festplatten exponentiell ausgeführt, was die Lösung des Problems selbst für 64 Festplatten ungeeignet macht. Sie können versuchen, es mit einer anderen Anzahl von Festplatten auszuführen, indem Sie die Variable num_discs ändern. Mit zunehmender Anzahl von Festplatten nimmt die Anzahl der Schritte zum Ausführen der Hanoi-Turmaufgabe exponentiell zu. Weitere Details finden Sie in vielen Quellen. Wenn Sie mehr über die Mathematik hinter der rekursiven Lösung dieses Problems erfahren möchten, lesen Sie die Erklärung von Karl Birch im Artikel „On Hanoi Towers“ .

1.6. Echte Anwendungen

Die verschiedenen in diesem Kapitel vorgestellten Methoden (Rekursion, Memoisierung, Komprimierung und Manipulation auf Bitebene) sind in der Entwicklung moderner Software so weit verbreitet, dass man sich die Computerwelt ohne sie nicht vorstellen kann. Trotz der Tatsache, dass Aufgaben ohne sie gelöst werden können, ist es oft logischer oder zweckmäßiger, sie mit diesen Methoden zu lösen.

Insbesondere liegt der Rekursion nicht nur viele Algorithmen zugrunde, sondern sogar ganzen Programmiersprachen. In einigen funktionalen Programmiersprachen wie Scheme und Haskell ersetzt die Rekursion Schleifen, die in imperativen Sprachen verwendet werden. Es ist jedoch zu beachten, dass alles, was mit der rekursiven Methode erreicht werden kann, auch iterativ ausgeführt werden kann.

Memoization wurde erfolgreich eingesetzt, um die Arbeit von Parsern zu beschleunigen - Programmen, die Sprachen interpretieren. Dies ist bei allen Aufgaben nützlich, bei denen das Ergebnis einer kürzlich durchgeführten Berechnung wahrscheinlich erneut angefordert wird. Ein weiterer Aktionsbereich für Memoization ist die Laufzeit der Programmiersprache. Einige dieser Laufzeiten, beispielsweise für die Prolog-Version, speichern automatisch die Ergebnisse von Funktionsaufrufen (Auto-Mash), sodass die Funktion nicht das nächste Mal mit demselben Aufruf ausgeführt werden muss. Dies ähnelt dem Dekorator @lru_cache () in fib6 ().

Die Komprimierung hat die Welt des Internets mit seiner begrenzten Bandbreite erträglicher gemacht. Die in Abschnitt 1.2 beschriebene Bitfolgenmethode ist auf einfache Datentypen in der realen Welt anwendbar, die eine begrenzte Anzahl möglicher Werte aufweisen, für die sogar 1 Byte redundant ist. Die meisten Komprimierungsalgorithmen suchen jedoch nach Mustern oder Strukturen in einem Datensatz, die doppelte Informationen eliminieren. Sie sind viel komplizierter als in Abschnitt 1.2 beschrieben.

Einweg-Chiffren sind nicht für allgemeine Verschlüsselungsfälle geeignet. Sie erfordern, dass sowohl der Codierer als auch der Decodierer über einen der Schlüssel verfügen (in unserem Beispiel Dummy-Daten), um die ursprünglichen Daten wiederherzustellen. Dies ist zu umständlich und ermöglicht in den meisten Verschlüsselungsschemata nicht das Ziel, die Schlüssel geheim zu halten. Vielleicht interessiert Sie aber auch, dass der Name „Einweg-Chiffre“ von Spionen erfunden wurde, die während des Kalten Krieges Notizbücher aus echtem Papier mit darin aufgezeichneten fiktiven Daten verwendeten, um verschlüsselte Nachrichten zu erstellen.

Diese Methoden sind die Bausteine ​​von Programmen, auf denen andere Algorithmen basieren. In den folgenden Kapiteln sehen Sie, wie weit sie angewendet werden.

Über den Autor

David Kopec ist Dozent für Informatik und Innovation am Champlain College in Burlington, Vermont. Er ist ein erfahrener Softwareentwickler und Autor von Classic Computer Science Problems in Swift (Manning, 2018) und Dart for Absolute Beginners (Apress, 2014). David erwarb einen Bachelor-Abschluss in Wirtschaftswissenschaften und einen Master-Abschluss in Informatik am Dartmouth College. Sie können ihn auf Twitter über @davekopec kontaktieren.

»Weitere Informationen zum Buch finden Sie auf der Website des Herausgebers
» Inhalt
» Auszug

25% Rabatt auf Gutschein für Händler - Python

Nach Bezahlung der Papierversion des Buches wird ein elektronisches Buch per E-Mail verschickt.