Поляков Константин Юрьевич, доктор тех. наук, профессор кафедры судовой автоматики и измерений, факультет корабельной энергетики и автоматики, учитель информатики
Санкт-Петербург
Konstantin Yu. Polyakov, Doctor of Sciences (Engineering), Professor at the Department of Ship Automation and Measurements, Faculty of Ship Power Engineering and Automation, informatics teacher
Saint Petersburg
В настоящей обзорной статье рассмотрены существующие подходы к решению задач на обработку символьных строк, включенных в контрольно-измерительные материалы (КИМ) Единого государственного экзамена (ЕГЭ) по информатике. Среди них можно выделить метод перебора, конечные автоматы, однопроходные алгоритмы, метод замен, динамическое программирование, регулярные выражения. Некоторые из этих инструментов недостаточно освещены в школьных учебниках информатики, хотя владение ими может существенно улучшить эффективность решения задач в условиях ЕГЭ. Для каждого из рассмотренных методов приведены характерные задачи, для решения которых этот метод эффективен. Все решения приводятся на языке программирования Python. Статья может быть полезна для учителей информатики, а также для школьников с высоким уровнем подготовки в области программирования.
This review article considers various approaches to solving problems for processing character strings included in the materials of the Unified State Examination (USE) in informatics. Among them are the brute force method, finite automata, one-pass algorithms, substitution method, dynamic programming, regular expressions. Some of these tools are insufficiently covered in school textbooks, although mastering them can significantly improve the efficiency of solving problems on processing character strings in the conditions of USE. For each of the considered methods we present characteristic problems that can be effectively solved by this method. All solutions are given in Python. The article can be useful for informatics teachers, as well as for pupils with an advanced level of programming skills.
The authors declare that there are no conflicts of interest present.