La maison d'édition «DMK Press» a publié le livre «Programmation Olympiade» avec le sous-titre «Étudier et améliorer les algorithmes en compétition». C'est devenu une bouffée d'air frais pour tous ceux qui sont intéressés, se préparent et se préparent à participer, ou tout simplement à planifier dans le futur, à une activité intellectuelle telle que divers événements de programmation sportive. En Russie, ils ne connaissent pas bien.
L'édition russe du Guide de la programmation concurrentielle (Springer International Publishing AG) a été publiée avec le soutien du MIPT IT Education Development Center et de son directeur Alexei Maleev, Mail.Ru Group, ainsi que du projet ICPC des ateliers de Moscou.
«La programmation des Olympiades devient de plus en plus populaire chaque année auprès des étudiants et des étudiants. Un bon exemple de cela est le fait qu'en 2019, nous, les Ateliers de Moscou ICPC, en novembre, nous organiserons le dixième camp de préparation à la Coupe du monde dans différentes parties du monde, ils ont déjà passé à Singapour, en Europe et en Amérique du Sud et en Russie - de Vladivostok à Moscou. Au début du mois d'octobre, le concours de programmation de Moscou s'est tenu à Moscou, auquel 2284 personnes ont participé sur 18 sites des universités de Moscou - un record absolu pour l'ampleur du concours, organisé avec le soutien de Rosmolodezh.
Nous sommes très heureux de l'intérêt vif des gars et sommes prêts à le soutenir de toutes les manières - par exemple, pour les étudiants des universités de Moscou, nous organisons une formation gratuite pour l'ICPC avec la participation des meilleurs formateurs. Et, bien sûr, il est toujours utile pour les participants de consolider le matériel, de démonter les tâches et d'améliorer leurs connaissances. Par conséquent, je suis très heureux que votre livre soit paru et je vous en félicite tous. Nous espérons qu'à la finale de l'ICPC à Moscou en juin 2020, il y aura déjà ces gars qui le liront et deviendront les héros de la deuxième édition complétée. »
Alexey Maleev, directeur de la finale de la Coupe du monde ICPC 2020 à Moscou, vice-recteur du MIPT, fondateur du projet ICPC des ateliers de Moscou.
«Guide de programmation compétitive» a été traduit en russe de l'anglais. En plus de l'anglais et du russe, la publication en coréen a été publiée.
L'auteur du livre est Antti Laaxsonen, enseignant et chercheur à l'Université d'Helsinki Aalto (Finlande) [3] avec une vaste expérience dans l'enseignement de la programmation et des algorithmes, et entraîneur de l'équipe finlandaise lors de compétitions internationales de programmation. Il a une cote élevée de 2347 et le statut de «maître international» sur le portail Codeforces sous le surnom de «pllk» [4]. En 2008, il A. Laaxsonen est devenu l'un des organisateurs de l'Olympiade informatique dans son pays. En 2016 - superviseur scientifique de l'Olympiade baltique en informatique.
Le public cible du livre est intéressé et / ou travaille dans le domaine de la programmation des Olympiades. Mais, pour l'assimilation complète du matériel, la connaissance des principes fondamentaux de la programmation est requise, tandis que l'auteur n'exige pas que le lecteur expérimente la conception d'algorithmes et la participation à des olympiades. Tout cela nous permet de recommander ce travail à un large éventail de lecteurs intéressés. Pour les débutants, il deviendra une introduction à la programmation moderne des olympiades, des spécialistes expérimentés aideront à systématiser les connaissances, deviendra un outil de référence pour eux.
La soumission du matériel dans le livre est effectuée du simple au complexe. Tout d'abord, il se familiarise avec les buts et objectifs du livre, avec la programmation de l'Olympiade, la collection de tâches CSES [5] et d'autres livres pertinents sur la programmation de l'Olympiade.
Ayant reçu la base théorique nécessaire, le lecteur sera prêt à passer à la pratique. La technique de programmation est le sujet suivant. L'auteur y a inclus les bases du langage C ++ (norme C11), qui implémente tous les exemples du livre; analyse d'algorithmes récursifs et d'opérations au niveau du bit.
Dans les chapitres de l'ouvrage, le lecteur pourra trouver des informations sur la plupart des sujets «standards» et des exemples de mise en œuvre d'algorithmes proposés aux participants à la programmation des olympiades: structures de données, programmation dynamique, algorithmes graphiques et algorithmes d'arborescence, requêtes de plage et manipulation de lignes.
Séparément, je voudrais souligner un certain nombre de chapitres du livre. Par exemple, le chapitre «Problèmes de conception sélectionnés pour les algorithmes». Il comprenait des algorithmes avec visualisation parallèle des rejets, analyse de la dépréciation et recherche des valeurs minimales. Le lecteur se voit proposer des algorithmes pour trouver la distance de Hamming, la solution du problème d'atteignabilité dans les graphiques, la méthode à deux points, la recherche ternaire, la minimisation des sommes et d'autres sujets intéressants pour «l'Olympiade» et leurs entraîneurs.
À titre d'exemple, je donnerai un exemple de tâches du chapitre «Questions choisies de conception d'algorithmes».
Considérons des algorithmes avec visualisation parallèle des bits dans lesquels des opérations au niveau du bit sont utilisées pour un traitement efficace des données. Dans un cas typique, nous pouvons remplacer la boucle for par des opérations au niveau du bit, ce qui réduit considérablement le temps d'exécution de l'algorithme.
Algorithmes de navigation parallèle
Les algorithmes avec visualisation parallèle des chiffres sont basés sur le fait que les chiffres individuels d'un nombre peuvent être manipulés en parallèle en utilisant des opérations au niveau du bit. Par conséquent, l'une des méthodes de conception d'algorithmes consiste à présenter les étapes de l'algorithme de manière à ce qu'elles puissent être efficacement mises en œuvre à l'aide d'opérations au niveau du bit.
Distance de Hamming Distance de Hamming
hamming (a, b) entre les lignes a et b de même longueur est le nombre de positions auxquelles ces lignes diffèrent. Par exemple:
hamming (01101, 11001) = 2.
Considérez la tâche suivante: étant donné n chaînes de bits de longueur k, calculez la distance de Hamming minimale entre deux chaînes. Par exemple, pour les lignes [00111, 01101, 11110], la réponse serait 2, car
- hamming (00111, 01101) = 2;
- hamming (00111, 11110) = 3;
- hamming (01101, 11110) = 3.
Le problème peut être résolu "de front" en calculant la distance de Hamming entre toutes les deux lignes. La complexité temporelle d'un tel algorithme est (n
k). Pour calculer la distance entre les lignes a et b, utilisez la fonction suivante:
int hamming(string a, string b) { int d = 0 for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; }
Mais comme les chaînes sont constituées de bits, la solution peut être optimisée en stockant les chaînes sous forme d'entiers et en calculant la distance entre elles à l'aide d'opérations au niveau du bit. En particulier, si k ≤ 32, alors les chaînes peuvent être stockées en tant que valeurs de type int et pour calculer la distance, utilisez cette fonction:
int hamming(int a, int b) { return __builtin_popcount(a^b); }
Ici, l'opération OU EXCLUSIF construit une ligne dans laquelle les unités sont dans les positions où a et b sont différents. Le nombre de chiffres unitaires est ensuite calculé par la fonction __builtin_popcount. Le tableau montre les résultats de la comparaison de l'algorithme d'origine et de l'algorithme avec une vue parallèle des bits en termes de temps d'exécution sur un ordinateur moderne. L'algorithme avec visualisation parallèle des bits s'est avéré environ 20 fois plus rapide.
Tableau: Durée d'exécution des algorithmes calculant la distance de Hamming minimale pour n chaînes de bits de longueur k = 30
Les chapitres «Mathématiques» et «Géométrie» ne méritent pas moins d'attention. Comme le lecteur l'a déjà deviné, ils se consacrent à la résolution de problèmes mathématiques et géométriques au moyen du langage de programmation C ++ et à la construction d'algorithmes appropriés. Dans le chapitre «mathématique», cinq grands sujets nous attendent: «Théorie des nombres», «Combinatoire», «Matrices», «Probabilité» et «Théorie des jeux». Et dans le «géométrique»: «Moyens techniques en géométrie», «Algorithmes basés sur la ligne de balayage». Ainsi, la présentation complexe de la construction d'algorithmes pour résoudre des problèmes mathématiques et géométriques fait du livre une «trouvaille» pour les «olympiadniki», car dans le contexte d'une pénurie de livres sur ce sujet, c'est une rareté.
Un certain nombre de problèmes, l'auteur a décidé de mettre dans le chapitre "Sujets supplémentaires". Leur développement «peut parfois aider à résoudre les problèmes d'olympiades les plus difficiles». C'est «La racine carrée dans les algorithmes», «Et encore une fois sur les arbres de segments», «Duchi», «Optimisation de la programmation dynamique» et «Divers». Sur la base du nom de l'explication supplémentaire, ils nécessitent des sous-titres sur les arbres de segments et sur différentes choses.
Quant aux arbres de segments, le lecteur se familiarisera avec la propagation paresseuse, les arbres dynamiques, les structures de données aux sommets, les arbres bidimensionnels. Et dans «Divers», il attend: une réunion au milieu (divisant l'espace de recherche en deux parties, à peu près égales, effectuant une recherche dans chaque partie, puis combinant les résultats), comptage des ensembles, recherche binaire parallèle, connectivité dynamique.
Complétez les informations de référence du livre sur les mathématiques et une bibliographie complète (32 sources).
Ainsi, le livre «Programmation Olympiade» d'Antti Laaxsonen est une excellente introduction au monde de la programmation sportive. En même temps, un merveilleux guide de référence. Le livre convient aux débutants "olympiadnikov" et aidera à organiser les connaissances expérimentées. Ce sera utile pour les entraîneurs.
Encore une fois, nous notons que tous les exemples du livre sont implémentés dans le langage de programmation C ++. Il est le plus demandé aux Jeux olympiques. Mais quelqu'un peut trouver cela un inconvénient du livre, car d'autres langages sont populaires - Python, Java. Ceux qui préfèrent ces langages de programmation peuvent résoudre les problèmes proposés dans un livre dans leur langue préférée. Ce sera un bon entraînement. En fin de compte, c'est précisément dans la recherche de la solution optimale que les tâches de l'Olympiade sont terminées.
L'article a été préparé par: Igor Shtompel, auteur et présentateur de la section "Career \ Education" dans la revue
"System Administrator"