Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Варпаховский Ф.Л. Элементы теории алгоритмов
 
djvu / html
 

§ 1. ПОНЯТИЕ АЛГОРИТМА
Понятие алгоритма не является точным математическим понятием и не допускает поэтому математического определения. Можно, следовательно, только описать и объяснить это понятие, и соответствующее «описательное определение» будет приведено в этом параграфе. Вначале, однако, полезно рассмотреть несколько примеров.
Введем прежде всего необходимое для дальнейшего понятие алфавита. Под алфавитом будем понимать конечный набор различимых символов (букв), причем запись A = {ai, . . . , as} означает, что алфавит А состоит из букв #1, . . . , as (s^l). Словами алфавита называются конечные последовательности букв алфавита. Например, для алфавита Л = {П, |, +} словами будут последовательности П++, (Ц ||||,+П+|,+, ПП|||| и т. д. Для удобства вводится также пустое слово, которое состоит из 0 букв и считается словом любого алфавита. Слова будем обозначать буквами греческого алфавита, пустое слово— символом Л. Переходим теперь к примерам.
Пример 1. Указать правило, которое для каждого натурального числа п позволяло бы установить за конечное число шагов, делится это число на данное натуральное число рХ) или нет1.
Можно, например, поступать следующим образом. Если п меньше р, то п делится на р в случае, когда м=0, и не делится в противном случае. Если же п не меньше р, то вычтем р из п и пусть п^ = п—р. Если HI меньше р, то п делится на р в случае, когда ni = 0, и не делится в противном случае. Если же HI не меньше р, то вычтем р из tti, получим n2=^i—р и т. д. Ясно, что после конечного числа вычитаний мы получим число /г&, меньшее р, и по тому,
1 Под натуральными числами здесь и в дальнейшем понимаются нуль и все целые положительные числа.

 

1 2 3 4 5 6 7 8 9 10 20


Математика