Der Verlag „DMK Press“ hat ein Buch „Olympiadenprogrammierung“ mit dem Untertitel „Algorithmen in Wettbewerben studieren und verbessern“ veröffentlicht. Es ist zu einem Hauch frischer Luft für alle geworden, die sich für eine solche intellektuelle Aktivität wie verschiedene Sportprogrammveranstaltungen interessieren, diese vorbereiten und sich darauf vorbereiten, daran teilzunehmen oder sie nur für die Zukunft zu planen. In Russland sind sie nicht gut bekannt.
Die russische Ausgabe des Buches „Guide to Competitive Programming“ (Springer International Publishing AG) wurde mit Unterstützung des Moskauer Instituts für Physik und Technologie und seines Leiters Alexei Maleev, Mail.Ru Group, sowie des Moskauer Projekts „Workshops ICPC“ veröffentlicht.
„Olympiade-Programme werden von Jahr zu Jahr beliebter bei Studenten und Studenten. Ein gutes Beispiel dafür war die Tatsache, dass wir, die Moscow Workshops ICPC, im November die zehnten Trainingslager-Vorbereitungen für die Weltmeisterschaft in verschiedenen Teilen der Welt abhalten werden, die bereits in Singapur, Europa und Südamerika sowie Russland stattgefunden haben. von Wladiwostok nach Moskau. Anfang Oktober fand in Moskau der Moskauer Programmwettbewerb statt, an dem 2284 Personen an 18 Orten der Moskauer Universitäten teilnahmen - ein absoluter Rekord für den Umfang des Wettbewerbs, der mit Unterstützung von Rosmolodezh ausgetragen wurde.
Wir freuen uns sehr über das lebhafte Interesse der Jungs und sind bereit, es in jeder Hinsicht zu unterstützen - zum Beispiel führen wir für Studenten der Moskauer Universitäten ein kostenloses Training für ICPC durch, an dem die besten Trainer teilnehmen. Und natürlich ist es für die Teilnehmer immer nützlich, Material zu konsolidieren, Aufgaben zu zerlegen und ihr Wissen zu erweitern. Deshalb freue ich mich sehr, dass Ihr Buch erschienen ist, und gratuliere uns allen dazu. Wir hoffen, dass es beim ICPC-Finale in Moskau im Juni 2020 bereits die Jungs geben wird, die es lesen und die Helden der zweiten, aktualisierten Ausgabe werden. “
Alexey Maleev, Direktor des Finales der ICPC 2020-Weltmeisterschaft in Moskau, Vizerektor des Moskauer Instituts für Physik und Technologie, Gründer des Moskauer Projekts „Workshops ICPC“.
"Leitfaden für wettbewerbsorientierte Programmierung" wurde aus dem Englischen ins Russische übersetzt. Zusätzlich zu Englisch und Russisch wurde die Veröffentlichung in Koreanisch veröffentlicht.
Der Autor des Buches ist Antti Laaxsonen, ein Lehrer und Forscher der Universität Helsinki Aalto (Finnland) [3] mit umfassender Erfahrung im Unterrichten von Programmierung und Algorithmen und der Trainer des finnischen Teams bei internationalen Programmierwettbewerben. Er hat eine hohe Bewertung von 2347 und den Status eines "internationalen Meisters" auf dem Codeforces-Portal unter dem Spitznamen "pllk". Im Jahr 2008 wurde er A. Laaxsonen einer der Organisatoren der Informatikolympiade in seinem Land. 2016 - wissenschaftlicher Leiter der Baltischen Olympiade in Informatik.
Die Zielgruppe des Buches sind alle interessiert und / oder arbeiten auf dem Gebiet der Olympiadenprogrammierung. Für die vollständige Assimilation des Materials sind jedoch Kenntnisse über die Grundlagen der Programmierung erforderlich, während der Autor keine Erfahrung mit dem Entwurf von Algorithmen und die Teilnahme an Olympiaden voraussetzt. All dies ermöglicht es uns, dieses Werk einem breiten Spektrum interessierter Leser zu empfehlen. Für Anfänger wird es eine Einführung in die moderne Olympiadenprogrammierung sein, erfahrene Spezialisten helfen bei der Systematisierung von Wissen und werden zu einem Referenzwerkzeug für sie.
Die Einreichung des Materials im Buch erfolgt von einfach bis komplex. Zunächst macht er sich mit den Zielen und Zielen des Buches vertraut, mit der Olympiadenprogrammierung, der Aufgabensammlung CSES [5] und anderen relevanten Büchern zur Olympiadenprogrammierung.
Nachdem der Leser die notwendige theoretische Grundlage erhalten hat, ist er bereit, mit der Praxis fortzufahren. Programmiertechnik ist das nächste Thema. Darin schloss der Autor die Grundlagen der C ++ - Sprache (C11-Standard) ein, die alle Beispiele des Buches implementiert. Analyse rekursiver Algorithmen und bitweiser Operationen.
In den Kapiteln des Buches wird der Leser Informationen zu den meisten Standardthemen und Beispielen für die Implementierung von Algorithmen finden, die den Teilnehmern bei der Programmierung von Olympiaden angeboten werden: Datenstrukturen, dynamische Programmierung, Graph- und Baumalgorithmen, Bereichsabfragen und Zeilenmanipulation.
Separat möchte ich einige Kapitel des Buches hervorheben. Zum Beispiel das Kapitel „Ausgewählte Entwurfsprobleme für Algorithmen“. Es umfasste Algorithmen mit paralleler Anzeige der Abflüsse, Abschreibungsanalyse und Ermittlung der Mindestwerte. Dem Leser werden Algorithmen zur Ermittlung der Hamming-Distanz, zur Lösung des Erreichbarkeitsproblems in Graphen, zur Zwei-Zeiger-Methode, zur ternären Suche, zur Minimierung von Summen und zu anderen interessanten Themen für die „Olympiade“ und ihre Trainer angeboten.
Als Beispiel werde ich ein Beispiel für Aufgaben aus dem Kapitel „Ausgewählte Fragen zum Entwurf von Algorithmen“ geben.
Betrachten wir Algorithmen mit paralleler Anzeige von Bits, bei denen bitweise Operationen für eine effiziente Datenverarbeitung verwendet werden. In einem typischen Fall können wir die for-Schleife durch bitweise Operationen ersetzen, was die Laufzeit des Algorithmus erheblich verkürzt.
Algorithmen für das parallele Durchsuchen
Algorithmen mit paralleler Anzeige von Ziffern basieren auf der Tatsache, dass einzelne Ziffern einer Zahl mit bitweisen Operationen parallel bearbeitet werden können. Daher besteht eine der Methoden zum Entwerfen von Algorithmen darin, die Schritte des Algorithmus so darzustellen, dass sie unter Verwendung bitweiser Operationen effektiv implementiert werden können.
Hamming Entfernung Hamming Entfernung
Hamming (a, b) zwischen Linien a und b gleicher Länge ist die Anzahl der Positionen, an denen sich diese Linien unterscheiden. Zum Beispiel:
Hamming (01101, 11001) = 2.
Betrachten Sie die folgende Aufgabe: Berechnen Sie bei n Bitketten der Länge k den minimalen Hamming-Abstand zwischen zwei Ketten. Zum Beispiel wäre für Zeilen [00111, 01101, 11110] die Antwort 2, weil
- Hamming (00111, 01101) = 2;
- Hamming (00111, 11110) = 3;
- Hamming (01101, 11110) = 3.
Das Problem kann "frontal" gelöst werden, indem der Hamming-Abstand zwischen zwei Zeilen berechnet wird. Die zeitliche Komplexität eines solchen Algorithmus ist (n
k). Verwenden Sie die folgende Funktion, um den Abstand zwischen den Linien a und b zu berechnen:
int hamming(string a, string b) { int d = 0 for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; }
Da die Zeichenfolgen jedoch aus Bits bestehen, kann die Lösung optimiert werden, indem die Zeichenfolgen als Ganzzahlen gespeichert und der Abstand zwischen ihnen mit bitweisen Operationen berechnet werden. Insbesondere wenn k ≤ 32 ist, können die Zeichenfolgen als Werte vom Typ int gespeichert werden. Um den Abstand zu berechnen, verwenden Sie diese Funktion:
int hamming(int a, int b) { return __builtin_popcount(a^b); }
Hier bildet die EXKLUSIVE ODER-Operation eine Zeile, in der sich die Einheiten an den Positionen befinden, an denen sich a und b unterscheiden. Dann wird die Anzahl der Einheitenstellen durch die Funktion __builtin_popcount berechnet. Die Tabelle zeigt die Ergebnisse des Vergleichs des ursprünglichen Algorithmus und des Algorithmus mit einer parallelen Ansicht der Bits in Bezug auf die Laufzeit auf einem modernen Computer. Der Algorithmus mit paralleler Anzeige von Bits erwies sich als etwa 20-mal schneller.
Tabelle: Laufzeit von Algorithmen zur Berechnung der minimalen Hamming-Distanz für n Bitfolgen der Länge k = 30
Die Kapitel „Mathematik“ und „Geometrie“ verdienen nicht weniger Beachtung. Wie der Leser bereits vermutet hat, widmen sie sich der Lösung mathematischer und geometrischer Probleme mit Hilfe der Programmiersprache C ++ und der Konstruktion geeigneter Algorithmen. Im Kapitel "Mathematik" warten wir auf fünf große Themen: "Zahlentheorie", "Kombinatorik", "Matrizen", "Wahrscheinlichkeit" und "Spieltheorie". Und im "Geometrischen": "Technische Mittel in der Geometrie", "Algorithmen basierend auf der Kehrlinie". Die komplexe Darstellung der Konstruktion von Algorithmen zur Lösung mathematischer und geometrischer Probleme macht das Buch somit zu einem „Fundstück“ für die „Olympiadniki“, da dies vor dem Hintergrund eines Buchmangels zu diesem Thema eine Seltenheit ist.
Eine Reihe von Problemen beschloss der Autor, in das Kapitel „Weitere Themen“ aufzunehmen. Ihre Entwicklung "kann manchmal bei der Lösung der schwierigsten Olympiadenprobleme helfen". Dies sind "Quadratwurzel in Algorithmen", "Und noch einmal über Segmentbäume", "Duchi", "Optimierung der dynamischen Programmierung" und "Verschiedenes". Basierend auf dem Namen der zusätzlichen Erklärung erfordern sie Unterüberschriften zu Segmentbäumen und zu verschiedenen Dingen.
In Bezug auf die Segmentbäume wird der Leser mit der langsamen Fortpflanzung, dynamischen Bäumen, Datenstrukturen an den Eckpunkten und zweidimensionalen Bäumen vertraut gemacht. Und in „Miscellaneous“ wartet er auf: ein Meeting in der Mitte (Aufteilen des Suchraums in zwei Teile, ungefähr gleich, Durchführen einer Suche in jedem Teil und anschließendes Kombinieren der Ergebnisse), Zählen von Mengen, parallele binäre Suche, dynamische Konnektivität.
Vervollständigen Sie das Buch Referenzinformationen zur Mathematik und eine umfangreiche Bibliographie (32 Quellen).
Das Buch „Olympiad Programming“ von Antti Laaxsonen ist eine hervorragende Einführung in die Welt der Sportprogramme. Gleichzeitig ein wunderbarer Nachschlagewerk. Das Buch ist für Anfänger "olympiadnikov" geeignet und hilft bei der Organisation des Wissens erlebt. Es wird für Trainer nützlich sein.
Wir stellen erneut fest, dass alle Beispiele in diesem Buch in der Programmiersprache C ++ implementiert sind. Er ist bei den Olympischen Spielen am gefragtesten. Aber jemand mag dies als Nachteil des Buches empfinden, da andere Sprachen populär sind - Python, Java. Diejenigen, die diese Programmiersprachen bevorzugen, können die vorgeschlagenen Probleme in einem Buch in ihrer Lieblingssprache lösen. Dies wird ein gutes Training sein. Gerade auf der Suche nach der optimalen Lösung werden die olympischen Aufgaben erledigt.
Der Artikel wurde verfasst von: Igor Shtompel, Autor und Moderator der Sektion "Career \ Education" in der Zeitschrift
"System Administrator"