"Космический извозчик" - разбор и решение олимпиадной задачи по программированию

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

«Космический извозчик» - разбор и решение олимпиадной задачи по программированию

Слинкин Дмитрий Анатольевич

кандидат педагогических наук, доцент

ФГБОУ ВО «Шадринский государственный

педагогический университет»

В статье рассматривается возможность применения инженерных подходов к решению олимпиадных задач по программированию. Для этого анализируется условие одной из графовых задач по нахождению кратчайшего пути, предложенной для студентов на олимпиаде по программированию в Шадринском государственном педагогическом институте в 2015 году, обосновывается невозможность ее классического однопроходного решения, с учетом заявленных в условии задачи ограничений на время работы программы. В то же время в условии задачи отсутствуют ограничения на объем исходного кода программы, что позволяет считать решением проблемы многопроходный алгоритм, первая часть которого является вспомогательной и наиболее трудозатратной, обрабатывает константную часть исходных данных и формирует набор преобразованных данных в виде исходного кода для второй части алгоритма. Вторая часть алгоритма осуществляет поиск кратчайшего пути по заранее подготовленному графу и формирует искомый результат. Таким образом, у студентов в процессе решения соответствующим образом сформулированных олимпиадных задач появляется возможность не только продемонстрировать высокий уровень математической подготовки и знаний в области программирования, но и освоить важные инженерные умения и навыки.

Ключевые слова: программирование; язык программирования; задачи на графах; PHP; олимпиада; олимпиадная задача

«Space cabby» - analysis and solution of problems in programming olympiad

Slinkin Dmitry Anatolyevich, Shadrinsk state pedagogical university

The article discusses the possibility of applying engineering approaches to solving Olympiad programming tasks. We analyzed the condition of one of the graph task of finding the shortest path suggested for students Olympiad on programming Shadrinsk State Pedagogical Institute in 2015, substantiates the failure of the classical single-pass solution, taking into account the stated in the problem of restrictions on the time of the program. At the same time, in the problem there are no restrictions on the amount of source code, which makes the decision of problems of multi-pass algorithm, the first of which is a subsidiary and the most labor-intensive processes the constant part of the original data and generates a set of converted data in the form of source code for the second part algorithm. The second part of the algorithm searches for the shortest path on a pre-prepared graph and generates the desired result. Thus, students in the process of solving suitably formulated Olympiad problems an opportunity to not only demonstrate a high level of mathematical training and knowledge in the field of programming, but also to learn important engineering skills.

Keywords: programming; programming language; graph problems; PHP; olympiad; olympiad problems

Олимпиадное программирование - это высокоинтелектуальное соревнование по разработке за ограниченное время алгоритмов решения сложных, специальным образом подготовленных задач. Школьные и вузовские олимпиады по программированию Northeastern European Regional Contest: http://neerc.ifmo.ru. ^, The ACM International Collegiate Programming Contest, https://icpc.baylor.edu/. ^, Timus Online Judge http://acm.timus.ru. ^, Правила ACM ICPC 2014, http://www.icpc2014.ru/ru/competition/rules. позволяют выявлять и поддерживать одаренных обучающихся, обеспечивают им возможность саморазвития как будущим IT-специалистам [6, 9]. Классический подход к составлению олимпиадных задач по программированию подразумевает, с одной стороны наличие художественного сюжета, на основе которого участник олимпиады должен построить математическую модель, а с другой - максимальную формализованность содержательной части задачи, то есть четкую, не допускающую двояких толкований формулировку, жесткое определение форматов входных и выходных данных, ограничения на время работы результирующей программы, на объем исходного кода и на объем памяти, которую задействует программа во время своего выполнения. Однако реальные инженерные задачи, решаемые программистами, достаточно редко удовлетворяют всем озвученным условиям. В таких задачах обычно опускаются или смягчаются некоторые из вышеописанных ограничений, в результате чего не только увеличивается количество вариантов решений задачи, но и появляются такие подходы к решению, с которыми участники классических олимпиад сталкиваются достаточно редко.

В Шадринском государственном педагогическом университете ФГБОУ ВО «Шадринский государственный педагогический университет», http://shgpi.edu.ru/. (до 2016 года - институте) более 10 лет проводятся очные и заочные олимпиады по программированию, в которых испытывают свои силы школьники, студенты вузов, и даже наши выпускники, много лет проработавшие в IT-сфере. Предлагаемые олимпиадные задачи всегда уникальны [1, 2], их создает и прорешивает оргкомитет олимпиады. Обладая достаточно обширным опытом в разработке программных систем, мы стараемся формулировать задачи максимально приближенным к реальности таким образом, что, с одной стороны, является отступлением от канонов олимпиадного программирования, но с другой - позволяет участникам олимпиады приобретать востребованные в будущей профессии умения и навыки.

Рассмотрим формулировку и решение одной из таких задач, предложенной студентам на олимпиаде по программированию в Шадринском государственном педагогическом институте в 2015 году Олимпиада по программированию в ШГПИ, 2015 https://shgpi.edu.ru/forum/viewforum.php?f=128. . Задача приведена в сокращенном виде, игровая фабула опущена «КОСМИЧЕСКИЙ ИЗВОЗЧИК», условие задачи и архив тестовых примеров: https://shgpi.edu.ru/forum/ viewtopic.php?f=128&t=1270. .

Задача "Космический извозчик" Задание

Компьютерная игра Oolite Космический симулятор Oolite, http://oolite.org/, http://roolite.org/. ^, космический симулятор, современная свободная реинкарнация знаменитой Elite, позволяет игроку почувствовать себя в роли космического торговца, пирата или рейнджера.

Вселенная игры включает в себя 8 галактик, каждая из которых содержит 256 уникальных звездных систем. Гиперпрыжок (ГП) между двумя звездными системами ограничен 7 световыми годами, время, затрачиваемое на ГП, пропорционально квадрату расстояния между системами (1 световой год преодолевается за 1 час, 6 - за 36 часов, 0.5 - за 0.25 часа и т.д.). Межгалактический гиперпрыжок (МГП) возможен только из галактики с номером X в галактику с номером X+1 и из последней - в первую галактику. МГП занимает 50 часов и всегда приводит к звездной системе целевой галактики, ближайшей по координатной сетке к исходной звездной системе.

Задача заключается в доставке пассажира от одной звездной системы до другой за минимальное время.

Форматы данных

Программа должна загружать, обрабатывать файл input.txt и сохранять результаты работы в файле output.txt.

Файл input.txt в первой строке содержит четыре неотрицательных значения через пробел: G1 N1 G2 N2. G1, N1 - номер стартовой галактики и звездной системы в ней, G2, N2 - номер финишной галактики и звездной системы в ней. Последующие строки содержат полную информацию о Вселенной, в текстовом формате, используемом разработчиками Oolite (см. прикрепленный файл planetinfo.plist). Данные о Вселенной носят статичный характер и не будут изменяться от теста к тесту. Считается, что каждая звездная система содержит одну основную планету, поэтому идентификация звездной системы является одновременно идентификацией планеты и наоборот. Пример блока данных об одной из звездных систем:

"0 0" = {

air_color = "0.735411 0.597965 0.878678 1"; cloud_alpha = 1.000000;

cloud_color = "0.638672 0.409149 0.527497 1"; cloud_fraction = 0.300000; coordinates = "2 90"; corona_flare = 0.009911; corona_hues = 0.658028; corona_shimmer = 0.349376;

description = "This planet is most notable for Tibediedian Arma brandy but scourged

by deadly edible grubs.";

economy = 2; government = 1; inhabitant = "Human Colonial"; inhabitants = "Human Colonials"; land_color = "0.077525 0.0438281 0.66 1"; land_fraction = 0.650000; layer = 0; name = "Tibedied"; planet_distance = 507100.000000;

polar_cloud_color = "0.787402 0.610544 0.701737 1"; polar_land_color = "0.727927 0.716006 0.934 1"; polar_sea_color = "0.888758 0.932617 0.883801 1"; population = 36;

productivity = 11520; radius = 4610; random_seed = "74 90 72 2 83 183"; rotation_speed = 0.002623;

sea_color = "0.547074 0.673828 0.532745 1"; sky_n_blurs = 46; sky_n_stars = 5808; station = "coriolis";

station_vector = "-0.717 -0.668 0.201"; sun_color = "0.781 0.520397 0.402831 1"; sun_distance = 783700; sun_radius = 150815.429688; sun_vector = "0.484 -0.815 0.319"; techlevel = 8;

};

Каждая звездная система идентифицируется парой неотрицательных чисел - номером галактики (от 0 до 7) и номером системы в галактике (от 0 до 255). Наименование системы определяется полем name и в общем случае уникальным не является. Координаты звездной системы определяются ключевым полем coordinates, содержащим пару неотрицательных значений, первое из которых является смещением вправо по оси X, второе - смещением вниз по оси Y от левого верхнего угла карты галактики. Расстояние между двумя планетами определяется в световых кодах и рассчитывается по формуле , где dx и dy - разность соответственно координат X и Y двух планет. Например, расстояние между планетами Lave (20,173) и Leesti (13,186) по указанной формуле вычисляется в 3.82 световых года. Ближайшая звездная система при МГП вычисляется по той же формуле.

Внимание! В Oolite расчет расстояний между системами базируется на указанной формуле, но, по историческим причинам, во многих версиях игры в точности ей не следует (например, расстояние между Lave и Leesti в оригинальной версии игры равно 3.6 световых года). Поэтому использование Oolite для проверки части собственных решений является в общем случае некорректным.

Файл output.txt в первой строке содержит минимальное время в часах (с точностью до двух знаков после запятой), необходимое для путешествия от стартовой до финишной звездных систем. В следующих строках перечисляются идентификаторы звездных систем (номер галактики, номер системы, название системы через пробел), по одному в каждой строке, от стартовой системы до финишной. Если существуют несколько маршрутов за минимальное время, может быть указан любой из них.

Ограничения: Максимальное время работы программы - 1 секунда.

Алгоритм решения задачи

Центральный алгоритм решения задачи основан на [7]:

1) построении неориентированного графа путей между звездными системами одной галактики;

2) построении ориентированного графа путей между звездными системами соседствующих галактик и совмещении его с первым графом;

3) нахождении кратчайшего пути между исходной и целевой системами с использованием того или иного алгоритма поиска пути в графе.

Несмотря на достаточную очевидность указанного алгоритма, полное решение задачи обладает рядом "подводных камней", среди которых следует выделить:

- необходимость и достаточная сложность парсинга исходных данных;

- большой объем исходных данных.

Если первую проблему можно достаточно просто решить использованием интрепретируемых языков программирования (PHP, Perl, Python и др.) со встроенной поддержкой регулярных выражений [5, 10], то вторая проблема, с точки зрения канонов олимпиадного программирования, выглядит нерешаемой, так как уменьшить объем исходных данных участник олимпиады не имеет никакой возможности. В результате время выполнения программы скорее всего превысит 1 секунду, что вступит в противоречие с ограничениями, изложенными в условии задачи.

С другой стороны, использование классических компилируемых языков (С, С++, Pascal и др.), скорее всего позволит частично решить вторую проблему, так как скорость работы скомпилированной программы обычно в несколько раз превышает скорость работы интерпретируемой. Однако это, во первых, никак не повлияет на скорость чтения исходных данных, а во вторых усложнит решение первой проблемы, так как встроенная поддержка регулярных выражений в классических языках зачастую отсутствует (исключение составляет C++, однако и здесь поддержка обеспечивается далеко не всеми компиляторами) и реализуется обычно через различные внешние библиотеки (Boost Boost.Regex 5.1.1, http://www.boost.org/doc/libs/1_61_0/libs/regex/doc/html/index.html. ^, Posix Regular Expression IEEE Std 1003.1, 2004 Edition. Chapter 9, Regular Expressions, http://pubs.opengroup.org/onlinepubs/00969 6899/basedefs/xbd_chap09.html. и т.д.), применение которых часто затруднено или даже запрещено правилами олимпиад. Альтернативой регулярным выражениям может стать посимвольный парсинг, однако, в случае сложной структуры исходных данных, такой подход часто становится источником трудноуловимых ошибок.

Предпосылками к решению проблемы с большим объемом исходных данных может послужить два факта:

1) весь набор исходных данных, кроме первой строки, гарантированно не изменяется от теста к тесту, то есть является полностью детерминированным;

2) в условии задачи отсутствуют ограничения на объем исходного кода программы и объем оперативной памяти, который программа может занимать при исполнении;

Таким образом, появляется возможность разбить решение на две последовательные фазы:

1) обработка детерминированной части исходных данных, построение графа и генерация программного кода с описанием полученных данных на целевом языке программирования;

2) расширение полученного программного кода обработкой недетерминированной части исходных данных и поиском кратчайшего пути.

Первая часть решения не предоставляется на проверку, она носит служебный характер. Решением, предоставленным оргкомитету олимпиады, будет считаться вторая часть решения задачи. Оно будет достаточно объемным, так как содержит в исходном коде сформированный предварительной обработкой граф, но при этом скорость работы программы будет в несколько раз выше, чем скорость работы решения с полной обработкой исходных данных.

Дополнительным положительным моментом данного подхода является возможность использовать разные языки программирования, по мнению участника олимпиады наиболее подходящие для первой и второй частей решения. Кроме этого, при командной олимпиаде, решением первой и второй части могут заниматься два различных участника одновременно, при этом второй участник вместо сгенерированных первым участником данных может временно использовать произвольным образом сформированную шаблон-заготовку.

Решение задачи на языке программирования PHP

Выбор языка программирования для решения любой задачи всегда обусловлен несколькими причинам. Чаще всего - это уровень знаний и опыта в программировании на том или ином языке, реже - совместимая с решаемой задачей область применимости языка.

Для обеих частей решения мы воспользуемся языком программирования PHP [3]. Это разрешенный правилами олимпиады язык, и его недостатки как интерпретатора будут полностью нивелированы разбиением решения на две части, где низкая скорость работы первой (подготовительной) компенсируется достаточно высокой скоростью второй. Дополнительно, использование только одного языка позволит применять специфичные именно для него средства хранения данных. Еще одним фактором выбора данного языка являются его богатые возможности по работе с массивами, что позволит минимизировать объем кода программы.

В качестве инструментария для создания и проверки решения мы воспользовались операционной системой Simply Linux 7.0.5 Simply Linux, http://slinux.ru/. , PHP 5.5.24 PHP, http://php.net/. , средой разработки Geany 1.24.1 Geany, https://www.geany.org/. , терминалом xfce4-terminal 0.6.3 Xfce Desktop Environment, https://www.xfce.org/. и файловым менеджером Midnight Commander 4.8.14 Midnight Commander, https://www.midnight-commander.org/. .

Часть 1. Конвертер данных.

Первая часть решения (elite_first.php) фактически представляет собой конвертер информации о 8 галактиках, представленной в структурированном текстовом формате, в граф, представленный в виде ассоциативного массива PHP (листинг 1).

графовая задача кратчайший путь

Листинг 1. elite_first.php, часть 1: Загрузка

Сначала следует загрузить в память программы исходный файл input.txt, составить и применить регулярное выражение, которое одной операцией выгрузит из набора исходных данных необходимую информацию о всех звездных системах, а именно: 1) номер галактики и номер системы в ней; 2) координаты X и Y системы в галактике; 3) название звездной системы.

В результате выполнения указанного кода массив $result будет содержать четыре элемента, из которых мы будем использовать последние три, представляющие собой поднаборы регулярного выражения в скобках в виде массивов строк:

1. В $result[1] каждая строка содержит номер галактики и номер звездной системы через пробел.

2. В $result[2] каждая строка содержит координаты X и Y звездной системы в галактике через пробел.

3. В $result[3] каждая строка содержит название звездной системы.

Один и тот же индекс во всех трех массивах соответствует одной и той же звездной системе. Например, информация о звездной системе Tibedied содержится в $result[1][0], $result[2][0] и $result[3][0].

Теперь разработаем и предварительно заполним структуру, содержащую граф галактик (листинг 2).

Листинг 2. elite_first.php 2: Структура графа галактик

Для этой цели используем двумерный массив $planets (строка 8). Первый индекс массива отвечает за номер галактики (от 0 до 7), второй - за номер звездной системы (от 0 до 255). Имя массива достаточно адекватно сути игры, так как каждая звездная система содержит единственную планету, название которой совпадает с названием системы. Поэтому в дальнейшем будем использовать термины "планета" и "звездная система" как синонимы.

В результате работы вышеприведенного участка кода каждая звездная система инициализируется ассоциативным массивом, структура которого приведена в таблице 1.

Таблица 1 Структура ассоциативного массива для хранения графа галактик

Далее формируем все возможные пути в каждой галактике (листинг 3).

Листинг 3. elite_first.php 3: Генерация внутригалактических путей

Для этого последовательно перебираем все звездные системы, рассчитываем расстояние между текущей системой и остальными, еще не рассмотренными в данной галактике, и, в случае расстояния между системами, не превышающим 7 световых лет, связываем их, добавляя к массиву связей каждой системы массив, хранящий последовательно информацию о номере смежной планеты, названии планеты, расстоянии до нее и количестве часов, необходимых для достижения планеты.

Схожим образом формируем межгалактические пути (листинг 4):

Листинг 4. elite_first.php 4: Генерация межгалактических путей

В отличие от внутригалактических связей, где каждая планета может обладать несколькими двунаправленными связями с другими планетами, межгалактические связи односторонние, каждая звездная система любой галактики имеет одну межгалактическую связь с ближайшей звездной системой в следующей галактике и приведенный алгоритм формирует эту связь. Структура формируемого массива, содержащего межгалактическую связь, эквивалентна структуре внутригалактических связей.

В результате работы программы массив $planets будет описывать в виде графа структуру всех галактик со связями между звездными системами.

Проведенное тестирование на ноутбуке Dell Latitude E5520 (CPU Intel Core i5, RAM 4 ГБ) показало, что время работы программы варьируется от 1.5 до 3 секунд, что однозначно подтвердило исходные предположения низкой скорости обработки и невозможности уложиться в отведенные ограничения в случае однопроходного решения.

Для завершения работы первой части программы следует преобразовать массив $planets в вид, доступный для вставки в исходный код второй части программы. Для этого воспользуемся специфичным для PHP механизмом сериализации. В результате сериализации массива мы получим его текстовое представление, которое можно будет заключить в строку и вставить непосредственно в код (листинг 5).

Листинг 5. elite_first.php 5: Генерация исходного кода графа галактик

Результирующий шаблон кода с подготовленным графом галактик (elite_template.php) будет достаточно объемным (более 2 МБ), при этом фактически все содержимое файла будет сосредоточено в одной строке. Такая длина строки может вызвать сложности в обработке различными редакторами кода, поэтому во время разработки и тестирования второй части программы имеет смысл не впрямую редактировать указанный файл, а подключать его к целевой программе с помощью конструкций include или require. По окончании отладки можно будет объединить оба файла.

Часть 2. Обработчик графа галактик.

Листинг 6. elite_result.php 1: Загрузка исходных данных

Результирующая программа будет использовать два источника данных: 1) файл elite_template.php, содержащий переменную с графом галактик, либо (в конечном варианте программы) - содержимое файла elite_template.php без открывающего и закрывающего phpтегов; 2) первую строку файла input.txt, описывающую номера исходной и результирующей планет (листинг 6).

Результатом исполнения данного участка кода будут:

$planets - граф галактик со сформированными путями между звездными системами;

$sg,$sp - исходная звездная система (номер галактики, номер системы в галактике);

$cg,$cp - целевая звездная система (номер галактики, номер системы в галактике);

Далее нам следует определиться с алгоритмом поиска кратчайшего пути в графе галактик. Одним из наиболее эффективных решений данной задачи признан алгоритм Дейкстры Алгоритм Дейкстры, https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры, http://www-m3.ma.tum.de/ foswiki/pub/MN0506/WebHome/dijkstra.pdf. .

Воспользуемся указанным алгоритмом (листинг 7). В комментариях к коду будем использовать термин "планета" синонимично термину "звездная система" по озвученным ранее причинам.

Листинг 7. elite_result.php 2: Поиск кратчайшего пути

В результате работы данного алгоритма каждая звездная система кратчайшего пути будет содержать по индексу "hours" время полета от исходной системы, а по индексам "fg" и "fp" - номер предыдущей в пути системы. Указанной информации достаточно для генерации результата (листинг 8).

Листинг 8. elite_result.php 3: Вывод результатов

Запуск указанной программы на первом из данных в условии задачи тестов (0 0 0 255: исходная система: 0 0, целевая: 0 255), дает корректный результат за 0.2-0.4 секунды, однако время прохождения остальных тестов (системы 0 149 0 7, 0 149 7 162 и 7 162 7 163) укладывается в 0.75-1.8 секунды, что совершенно неприемлемо. Причины такого разброса результатов очевидны: завершение работы алгоритма происходит в момент, когда однозначно определяется кратчайший путь/пути до целевой системы (строка 30), что в большинстве случаев приходит до момента построения кратчайших путей до всех звездных систем игровой вселенной (строка 29).

Потенциал повышения скорости заложен в алгоритме поиска кратчайшего пути. Если на количество итераций внешнего цикла (строки 14-52) мы в повлиять фактически не можем, то поиск системы с минимальным временем полета до исходной (строки 17-28) реализован не слишком эффективно, так как на каждой итерации внешнего цикла обеспечивает перебор всех звездных систем, включая и недостижимые на данный момент, что является излишним.

Оптимизируем данный поиск с помощью создания массива достижимых в каждый конкретный момент звездных систем и выполнения организацию поиска только внутри данного массива (листинг 9).

Листинг 9. elite_result.php 4: Поиск кратчайшего пути (оптимизация)

Массив достижимых систем $ap первоначально содержит ссылку на исходную систему (строка 14) и заполняется во время минимизации расстояний до смежных внутри- и межгалактических звездных систем (строки 36, 46). Наличие данного массива позволяет значительно ускорить поиск системы с минимальным временем полета до исходной (строки 18-25), по сравнению с полным перебором всех звездных систем. Массив индексируется комбинацией номера галактики и номера звездной системы, что обеспечивает его минимальный объем, так как повторное внесение системы в массив просто перезаписывает соответствующую ссылку, без добавления нового элемента, что обеспечивает наличие в массиве только уникальных элементов.

Тестирование обработчика графа галактик, с внедрением указанной оптимизации, показало, что время его работы не превышает 0.85 секунды на любом тесте. Теперь решение задачи полностью соответствует исходным требованиям.

Заключение

В течение многих лет, проводя вузовские и школьные олимпиады по программированию, мы практикуем разнообразие подходов к формулировками олимпиадных задач, их максимальное приближение к реальным ситуациям, отменяя одни ограничения и строго фиксируя другие, минимизируя требования к языкам и технологиям программирования, комбинируя в условиях задач основы многих наук, компьютерные игры, реальные жизненные ситуации и IT-проблемы. Во главу угла мы ставим внимательность, гибкость мышления, умения искать и находить нестандартные решения. Такой подход позволяет в полной мере раскрыть свои возможности самому широкому контингенту участников олимпиад, вне зависимости от области их интересов и глубины узкоспециализированных знаний.

Литература

1. «Блондинка против технарей» или Разбор и решение олимпиадной задачи по программированию / Д.А. Слинкин // Информатика и образование, 2011. №8.-С. 42-48.

2. «Шахматные» олимпиадные задачи по программированию / Пирогов В.Ю. // Информатика в школе, 2011. №5. С. 55-57.

3. Котеров Д.В., Костарев А.Ф. PHP 5: В Подлиннике - СПб.: БХВ-Петербург, 2006 - 1120 стр.

4. Мансуров К.Т. Основы программирования в среде Lazarus [Электронный ресурс], 2010. - 772 с.: ил. Режим доступа: http://www.freepascal.ru/download/ book/lazarus_osnovy/osnovy_programmirovanija_v_srede_lazarus.pdf.

5. Мельников С.В. Perl для профессиональных программистов. Регулярные выражения. - М.: «Бином», 2007. - 190 с.

6. Олимпиадное программирование как эффективный инструмент подготовки профессиональных программистов / Крайванова В.А., Крючкова Е.Н. // Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2012. Т. 10. №4. С. 51-56.

7. Оре, О. Теория графов / О. Оре; пер. с англ. И.Н. Врублевской; под ред. Н.Н. Воробьева. - Изд. 2-е, стер. - Москва: Наука, 1980. - 336 с.: ил.

8. Прата, Стивен. Язык программирования С++. Лекции и упражнения: [пер. с англ.] / Стивен Прата. - Москва [и др.]: Вильямс, 2016. - 1244 с.; 24 см. - Предм. указ.: с. 1240-1244.

9. Система подготовки олимпиадных задач по программированию в УрГУ / Самсонов А.В., Ипатов А.В. // Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2012. Т. 10. №3. С. 92-104.

10. Фридл Дж. Регулярные выражения, 3е издание. - Пер. с англ. - СПб.: СимволПлюс, 2008. - 608 с., ил.

Размещено на Allbest.ru