Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Машина поста - Успенский В.А.

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 .. 38 >> Следующая

можно ответить, что корень уравнения существует. А что, если четна?
Проблема 3. Дано: произвольное алгебраическое уравнение с целыми
коэффициентами. Требуется: выяснить, существует ли у данного уравнения
решение в рациональных числах.
Искомый алгоритм: существует он или нет - неизвестно.
Просмотрите, как близки друг к другу формулировки наших проблем 1, 2 и 3:
эти формулировки различаются лишь в одном слове. И как, тем не менее,
различны ответы на вопрос, существует или нет соответствующий алгоритм.
Поистине, удивительное рядом!
Преобразование слов. В математике словами называются любые конечные
последовательности символов. Например, 1985 - слово длины 4. Слова не
только не обязаны обладать каким-либо смыслом, но даже быть
произносимыми. Так, БРДРОЬЪЩ - слово из русских букв (и притом длины 8),
хотя и не слово русского языка. Как правило, исходные данные для
алгоритмов - это слова. Когда алгоритм задан, определено и множество
букв, то есть символов, из которых составляются слова, подаваемые ему на
вход. Такое множество называется алфавитом. Алфавиты, в которых пишутся
тексты на естественных-языках и языках программирования, печатаются
книги, содержат не более нескольких сот букв. Многозначные числа,
участвующие в "школьных" алгоритмах - это слова в десятибуквенном
алфавите, состоящем из букв 0, 1, 2, ..., 9; эти буквы, как известно,
называются цифрами; а для записи десятичных дробей, помимо этих десяти
цифр, используется еще одна буква - запятая.
Современные вычислительные машины работают с двоичными словами,
состоящими из букв 0 и 1. Чтобы проиллюстрировать гибкость и емкость
понятия "слово", заметим, что пару слов можно закодировать одним словом,
например, поставив между членами пары букву, не входящую в алфавит, в
котором эти члены записаны. Таким образом, в качестве исходных данных для
алгоритмов достаточно рассматривать слова, а рассматривать в этом
качестве пары, тройки и т. д. слов нет нужды. Заметим еще, что часто
бывает удобно рассматривать слово длины ноль; оно называется пустым
словом, так как вовсе не содержит букв.
Многие из вас играли в следующую игру. Дается задание, на* нример,
"переделать волка в козу". Решение:
ВОЛК ПОЛК -> ПОЛА -> ПОЗА -> КОЗА
В чем состоит один шаг переделки? - В замене любой буквы уже полученного
слова на любую другую букву русского алфавита, йричем так, чтобы
получаемый объект (слово в математическом смысле этого слова) оказывался
снова осмысленным словом русского языка.
Теперь упростим игру - забудем о том, что среди всех последовательностей
букв выделены слова русского языка. Будем считать все (в математическом
понимании, то есть как осмысленные, так и бессмысленные) слова в русском
алфавите равноправными. Можно
92
ли тогда переделать волка в козу? Ну, теперь это совсем легко:
волк -*¦ кол к -> коз К -> КОЗА
Может быть, теперь любое слово можно переделать в любое? Конечно нет -
слова должны быть одинаковой длины. Но этого условия и достаточно!
Проблема. Дано: два слова в русском алфавите. Т р е б у е т -с я: узнать,
получается ли одно из другого последовательностью замен буквы на букву.
Искомый алгоритм: сравнить длины слов, если они совпадают, то ответ ДА,
если не совпадают, то ответ - НЕТ.
Заметим, что первоначальная проблема - переделать одно заданное слово
русского языка - также очевидно решима - для ее решения нужно только
иметь (конечный!) словарь всех слов русского языка, которые можно
использовать в игре, и достаточный запас времени и бумаги. Несложный
подсчет показывает, что эта задача может быть практически решена на
сегодняшних ЭВМ.
Теперь, опять забыв о русском языке (но не о русском алфавите) и под
словами понимая произвольные конечные последовательности русских букв,
усложним задачу в другом отношении. Вместо того, чтобы разрешать заменять
(в любом месте слова) любую букву на любую, выберем некоторый конечный
список разрешенных замен. Этот список может выглядеть, например, так:
А БББ БА
t I I
Б АА АБА
Преобразование слова за один шаг будет, как и раньше, состоять в том, что
в любом месте слова мы заменяем участок, который разрешено заменять, на
то, на что его разрешено заменять. При этом все разрешенные замены
двусторонние: если участок X разрешено заменять на участок У, то и
участок У разрешено заменять на участок X. Например, если список
разрешенных замен таков, какой мы только что выбрали, то преобразование
за один шаг может быть таким: БААБ - БББББ, или таким: БАБ - АБАБ, или
такимз БАБА - БААА.
Проблема. Дано: два слова в русском алфавите. Требуется'. узнать, можно
ли переделать одно в другое, пользуясь следующей системой разрешенных
замен:
АВ БВ АУ БУ ДВА ДУБ ВВА
t t t t I t t
BA ВБ У А УБ ВД УД ВВАД
Искомый алгоритм: не существует. В 1957 году это доказал советский
математик Г. С. Цейтин, придумавший указанную систему замен.
Подобную проблему в общем виде (то есть для любой системы разрешенных
замен) впервые поставил известный норвежский математик Аксель Туэ в 1914
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 .. 38 >> Следующая