В статье вводятся и решаются новые задачи эффективного восстановления неизвестной последовательности фиксированной длины с помощью ее образцов, искаженных ошибками заданного типа. Эти образцы могут рассматриваться как выходные последовательности при многократной передаче исходной последовательности по комбинаторному каналу с максимальным допустимым числом одиночных ошибок или по дискретному вероятностному каналу. Эффективность восстановления понимается в смысле минимизации числа N ошибочных образцов, которые достаточны для однозначного восстановления любой неизвестной последовательности или ее восстановления с допустимой точностью и/или вероятностью. Здесь также учитывается существование простого алгоритма восстановления. Приводятся полные решения для комбинаторных каналов при некоторых типах ошибок, характерных для теории кодирования, а именно, замены, транспозиции, выпадений и вставок символов. В общем случае эта задача для комбинаторных каналов сводится к новой задаче восстановления вершины графа с помощью минимального числа вершин в ее метрическом шаре заданного радиуса. Для дискретных каналов без памяти найдено асимптотическое поведение минимального числа повторных передач, которое достаточно для восстановления любой последовательности длины n в пределах расстояния Хэмминга d с вероятностью ошибки ε, когда d/n и ε стремятся к 0 при n → ∞ . Подобный результат для непрерывного канала с дискретным временем и белым гауссовым шумом также получен.
