Палиндром — слово, читающееся одинаково в обе стороны¶

Палиндром — последовательность символов (букв, цифр, знаков), которая одинаково читается в прямом и обратном направлении. Термин происходит от греческих слов palin («снова, обратно») и dromos («бег»), то есть буквально «бегущий назад». Палиндромами являются и отдельные слова («шалаш», «топот»), и целые фразы («А роза упала на лапу Азора»), и числа (12321), и строки кода.

¶История

Первые известные упоминания палиндромов относятся к античности. В Древней Греции палиндромические надписи наносили на кольца и печати — считалось, что такое сочетание букв обладает магической силой. Латинский пример — «Sator Arepo tenet opera rotas» («Сатор Арепо держит дела в движении»), квадратная палиндромическая надпись, обнаруженная в Помпеях и на других археологических объектах Римской империи.

В средневековой Европе палиндромы использовали в религиозном контексте: на них строили латинские молитвы и гимны. В русской традиции палиндромы известны как загадки и словесные игры; классическим примером служит фраза «А роза упала на лапу Азора», приписываемая И. С. Тургеневу (достоверность авторства не подтверждена).

¶Виды палиндромов

• Пословные палиндромы — фраза, читающаяся одинаково по буквам с учётом пробелов и пунктуации. Пример: «Коту ток».
• Словесные палиндромы — последовательность слов, одинаковая при чтении в обратном порядке (слова не переворачиваются, меняется только их порядок). Пример: «Я иду — иду я».
• Числовые палиндромы — числа, одинаковые при чтении в обратном порядке: 12321, 99, 20255202.
• Бинарные палиндромы — строки из нулей и единиц, симметричные относительно центра. Применяются в теории кодирования и проверке ошибок.
• Палиндромические строки — произвольные последовательности символов, включая код и генетические последовательности.

¶Математические свойства

Палиндромы изучаются в комбинаторике и теории чисел. Количество палиндромов длины n над алфавитом из k символов равно k^⌈n/2⌉ — симметрия полностью определяется половиной строки. Сумма палиндромных чисел, делится ли число на 11, проверяется по правилу чередования знаков — палиндром с чётным числом цифр всегда делится на 11.

В компьютерных науках проверка строки на палиндромность — стандартная задача на алгоритмы и структуры данных; она решается за линейное время с использованием двух указателей или стека. Задача имеет прикладное значение в биоинформатике: палиндромические последовательности ДНК важны для работы рестрикционных ферментов, расщепляющих молекулу в симметричных участках.

¶Палиндромы в языке

В русском языке известны палиндромы-слова: «шалаш», «топот», «репер», «якорь» (при определённом написании), «не реви, ревенек». Английские примеры: kayak, level, rotor, civic. Сложность составления палиндромов на естественном языке связана с неравномерным распределением букв: в русском языке буквы «а», «о», «е» встречаются чаще, чем «ф», «щ», «ъ», что облегчает построение симметричных фраз.

Палиндромы используются в литературе как приём: они создают эффект зеркальности, замкнутости текста. В современной культуре палиндромы стали объектом рекордов — существуют книги, полностью составленные из палиндромических фраз, и музыкальные произведения, читающиеся одинаково в обе стороны.

¶Применение

• Криптография и теория кодов — палиндромные последовательности используются в построении кодов с обнаружением ошибок.
• Биоинформатика — палиндромические мотивы ДНК распознаются рестрикционными ферментами и участвуют в регуляции генов.
• Проверка алгоритмов — задача о палиндроме служит учебным примером в программировании.
• Информатика — палиндромные хеш-функции и симметричные структуры данных применяются в сжатии информации.

Источники:

• Википедия: «Палиндром»
• Кнут Д. «Искусство программирования»
• Сборник «Задачи и упражнения по комбинаторике»
• Научные статьи по биоинформатике о палиндромических последовательностях ДНК