Первый язык программирования.

[e2e4]

lim0n писал(а):

По-моему, хороший пример "конечного набора" из трех правил. Сравните:
...

Извините, не понял Вас. Ну и что из того, что Вы развернули цикл? Поясните пожалуйста?

venco писал(а):

Кстати, тогда и считать ничего не надо - сразу выводим 10-ую цифру.

А если $10^{10^{10^{10}}}$ цифру?
Кстати, скорее всего, запись алгоритма, вычисляющую достаточно n-ую цифру числа пи с какого-то n становится менее длинной, чем сама запись этой цифры. Т.е. алгоритм может служить альтернативой записи очень больших (но тем не менее, совершенно определенных и интересных нам) чисел.

[venco]

e2e4 в сообщении #346549 писал(а):

А если $10^{10^{10^{10}}}$ цифру?

Т.е. номер цифры таки входной параметр?

e2e4 в сообщении #346549 писал(а):

Кстати, скорее всего, запись алгоритма, вычисляющую достаточно n-ую цифру числа пи с какого-то n становится менее длинной, чем сама запись этой цифры.

Запись цифры - одна цифра.

e2e4 в сообщении #346549 писал(а):

Т.е. алгоритм может служить альтернативой записи очень больших (но тем не менее, совершенно определенных и интересных нам) чисел.

О каких больших числах Вы говорите? Одна цифра всегда меньше 16 (мы ведь говорим о шестнадцатеричных цифрах, судя по приведённому алгоритму).

[e2e4]

venco, Вы не поняли.

Цитата:

Т.е. номер цифры таки входной параметр?

Зачем? Просто алгоритм, вычисляющий заранее определенную n-ую цифру.

Цитата:

Запись цифры - одна цифра.

Хорошо, запись числа $10^{10^{10^{10}}}$

Остальное, думаю, понятно :).
------------------------------------------
Хух. Решил не удалять предыдущее... Конечно, я подразумевал, запись числа пи с точностью до $10^{10^{10^{10}}}$ чисел после запятой :). Да, чего-то перемкнуло в голове.

В общем тезис: алгоритм, вычисляющий (и выводящий в cout) число пи с точностью $10^{10^{10^{10}}}$ цифр после запятой занимает меньше места (байт, если угодно), чем само число пи с $10^{10^{10^{10}}}$ знаками после запятой. Так пойдет?

И тезис №2: зададимся n-ой очень далекой цифрой числа пи. Легче (быстрее) обозначить ее неким алгоритмом вычисления, чем вычислить и написать. Так? Имеет такой "алгоритм" право называться алгоритмом (он конечен)?

[Ринат]

Maslov в сообщении #346312 писал(а):

10 вводить надо только в случае, если алгоритм должен уметь считать любую цифру . А если достаточно уметь считать только 10-ю, то ничего вводить не надо; этот параметр (10) у него внутри. Так же, как остальные константы (1, 2, 4, 6, 8, 16).

Не важно, как Вы вводите константы: с командной строки или из самого кода - все это и есть ввод.

e2e4 в сообщении #346318 писал(а):

Насчет конечности - а почему она собственно должна быть? Алгоритм автомата пожаротушения как пример:

Вполне реальный пример конечного алгоритма. Во-первых, он имеет конечный набор правил, во-вторых, решает поставленную задачу за конечное время (тушит огонь). И вовсе не важно, если Вы разжигаете огонь вновь. Если Вы запрограммировали алгоритм, находящийся в режиме прослушивания, это вовсе не значит, что он - бесконечный, так как при этом с главной задачей он справляется за конечное время (например, запись в журнал сообщений об ошибках).

e2e4 в сообщении #346318 писал(а):

Насчет эффективности - а что вообще под этим термином подразумевал Кнут?

Он подразумевал оценку способности алгоритма справляться с поставленной задачей за определенное конечное время. Если это время больше заданной оценки, то алгоритм считается малоэффективным.

Вообще, конечно, грамматически алгоритм может быть каким угодно: бесконечным, неэффективным, недискретным. Но это приравнивается контексту "люди умеют летать".

[lim0n]

e2e4 в сообщении #346549 писал(а):

Извините, не понял Вас. Ну и что из того, что Вы развернули цикл? Поясните пожалуйста?

Ринат уже пояснил это более подробно. Мой пример, возможно неудачный, - попытка показать "бесконечный набор правил".

По поводу эффективности... Это слово также имеет значение - "Предназначенный для выполнения полезной работы; производительный." Не перекликается ли это с требованием конечности алгоритма? Если неизвестно время получения результата, о какой эффективности можно говорить.

[Maslov]

Ринат в сообщении #346637 писал(а):

Не важно, как Вы вводите константы: с командной строки или из самого кода - все это и есть ввод.

Интересная мысль. Рассмотрим алгоритм решения квадратного уравнения с заданными коэффициентами ($a, b, c$):
$x_{1,2} = \dfrac {-b \pm \sqrt {b^2 - 4 a c}} {2 a}$
Что, по-вашему мнению, является "входом" этого алгоритма?
$<a, b, c >$ или $<a, b, c, 1, 2, 4>$?

По поводу эффективности. Оригинальные статьи найти не найти не удалось, но возможно, здесь более точная цитата, чем в Википедии:

Цитата:

Knuth (1968, 1973) has given a list of five properties that are widely accepted as requirements for an algorithm:
1. Finiteness: "An algorithm must always terminate after a finite number of steps"
2. Definiteness: "Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case"
3. Input: "...quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects"
4. Output: "...quantities which have a specified relation to the inputs"
5. Effectiveness: "... all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil"

Кстати, если верить тому, что написано, это вовсе не определение алгоритма, это важные свойства.

[Ринат]

Maslov в сообщении #346661 писал(а):

Ринат в сообщении #346637 писал(а):

Не важно, как Вы вводите константы: с командной строки или из самого кода - все это и есть ввод.

Интересная мысль. Рассмотрим алгоритм решения квадратного уравнения с заданными коэффициентами ($a, b, c$):
$x_{1,2} = \dfrac {-b \pm \sqrt {b^2 - 4 a c}} {2 a}$
Что, по-вашему мнению, является "входом" этого алгоритма?
$<a, b, c >$ или $<a, b, c, 1, 2, 4>$?

Второе, ибо константы 1, 2, 4 равнозначно "вводятся" (в коде программы).

Maslov в сообщении #346661 писал(а):

Кстати, если верить тому, что написано, это вовсе не определение алгоритма, это важные свойства.

Совершенно верно, но выделяю в написанном предложение:

Цитата:

Knuth (1968, 1973) has given a list of five properties that are widely accepted as requirements for an algorithm.

lim0n в сообщении #346655 писал(а):

По поводу эффективности... Это слово также имеет значение - "Предназначенный для выполнения полезной работы; производительный." Не перекликается ли это с требованием конечности алгоритма? Если неизвестно время получения результата, о какой эффективности можно говорить.

Часто такое время заранее известно и устанавливается верхней оценкой (а также условиями сходимости к решению).

[Dandan]

Ринат в сообщении #346695 писал(а):

Maslov в сообщении #346661 писал(а):

Ринат в сообщении #346637 писал(а):

Не важно, как Вы вводите константы: с командной строки или из самого кода - все это и есть ввод.

Интересная мысль. Рассмотрим алгоритм решения квадратного уравнения с заданными коэффициентами ($a, b, c$):
$x_{1,2} = \dfrac {-b \pm \sqrt {b^2 - 4 a c}} {2 a}$
Что, по-вашему мнению, является "входом" этого алгоритма?
$<a, b, c >$ или $<a, b, c, 1, 2, 4>$?

Второе, ибо константы 1, 2, 4 равнозначно "вводятся" (в коде программы).

Это какой-то бред, не морочьте людям голову.

[Ринат]

Dandan в сообщении #346727 писал(а):

Это какой-то бред, не морочьте людям голову.

По-моему Вы уже достаточно спалились со знаниями алгоритмов в своём топике. Хотите обсуждать алгоритмы? Обсуждайте, а захватом темы любой дурак заниматься умеет.

[lim0n]

Ринат в сообщении #346695 писал(а):

Второе, ибо константы 1, 2, 4 равнозначно "вводятся" (в коде программы).

Конечно же для решения квадратного уравнения достаточно ввода его коэффициентов.

По поводу констант...
При вычислении числа $\pi$ с точностью до $n$ знаков после запятой, разве число $n$ не подходит под определение:

Цитата:

3. Input: "...quantities which are given to it initially before the algorithm begins...

А, например, при генерации псевдослучайной последовательности, не является ли "затравка" (seed) вводом для алгоритма?

[Maslov]

Ринат в сообщении #346695 писал(а):

Maslov в сообщении #346661 писал(а):

Интересная мысль. Рассмотрим алгоритм решения квадратного уравнения с заданными коэффициентами ($a, b, c$):
$x_{1,2} = \dfrac {-b \pm \sqrt {b^2 - 4 a c}} {2 a}$
Что, по-вашему мнению, является "входом" этого алгоритма?
$<a, b, c >$ или $<a, b, c, 1, 2, 4>$?

Второе, ибо константы 1, 2, 4 равнозначно "вводятся" (в коде программы).

Надо сказать, я в первый раз сталкиваюсь с такой широкой трактовкой понятия "входа" алгоритма. В частности, тот же Кнут в книге "Искусство программирования для ЭВМ. Т.1 Основные алгоритмы." пишет буквально следующее:

Цитата:

3) Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т. е. величин, заданных ему до начала работы. Эти данные берутся из некоторого конкретного множества объектов. В алгоритме Е [алгоритм Евклида], например, две входные величины, а именно $m$ и $n$, выбираемые из множества натуральных чисел.

Т. е. Кнут почему-то не включает число 0 (используемое при проверке окончания работы) во входные данные :)

lim0n в сообщении #346761 писал(а):

При вычислении числа $\pi$ с точностью до $n$ знаков после запятой, разве число $n$ не подходит под определение:

При вычислении числа $\pi$ с точностью до $n$ знаков число $n$, конечно, является входом. А при вычислении числа $\pi$ с точностью до 10 знаков, 10 входом не является, ибо такой алгоритм вполне имеет право не уметь вычислять $\pi$ ни с точностью 9 знаков, ни с точностью 11 знаков.

Речь же не о том, что никакому алгоритму не требуются входные данные, а о том, что существуют алгоритмы, которым входные данные не требуются.

Не нравится пример с $\pi$, давайте рассмотрим поиск первого полусовершенного числа, являющегося, одновременно, точным квадратом. Ну какие входы у такого алгоритма?

[Dandan]

Ринат в сообщении #346742 писал(а):

Dandan в сообщении #346727 писал(а):

Это какой-то бред, не морочьте людям голову.

По-моему Вы уже достаточно спалились со знаниями алгоритмов в своём топике. Хотите обсуждать алгоритмы? Обсуждайте, а захватом темы любой дурак заниматься умеет.

В том топике я объяснил то, что имел ввиду и никаких замечаний или несогласий не увидел. Если вы с чем-то не согласны - напишите там, обсудим.

А на счет примера $x_{1,2} = \dfrac {-b \pm \sqrt {b^2 - 4 a c}} {2 a}$ - может еще и маленькую двоичку над буквой b запишем во входные данные ? Ах, есть же еще квадратный корень, а не, например, кубический. Тоже считаем как входные данные. Можем пойти дальше. У нас в алгоритме есть операция деления . А что если мы и ее запишем во входные данные? Мы ж в алгоритме именно делим, а не перемножаем или складываем числитель и знаменатель. Ну и т.д.

В каком-то смысле это всё правильно. Можно сказать, что весь алгоритм есть "входные данные" для универсальной вычислительной машины, коей является компьютер, например. Но сам по себе алгоритм из примера не имеет входных данных, если a,b,c - фиксированы. Хотя это все равно всё не строго, так как мы не определились, что мы называем алгоритмом (машина тьюринга, частично-рекурсивная функция и т.п.) и что мы называем его входом.

[arseniiv]

Ринат в сообщении #346695 писал(а):

Второе, ибо константы 1, 2, 4 равнозначно "вводятся" (в коде программы).

А если вместо $4ac$ взять $ac + ac + ac + ac$?

-- Вт авг 24, 2010 22:53:49 --

Dandan в сообщении #346793 писал(а):

Ах, есть же еще квадратный корень, а не, например, кубический. Тоже считаем как входные данные. Можем пойти дальше. У нас в алгоритме есть операция деления . А что если мы и ее запишем во входные данные? Мы ж в алгоритме именно делим, а не перемножаем или складываем числитель и знаменатель. Ну и т.д.

+1!

[lim0n]

Maslov в сообщении #346782 писал(а):

давайте рассмотрим поиск первого полусовершенного числа, являющегося, одновременно, точным квадратом. Ну какие входы у такого алгоритма?

Почему бы не сказать проще: "рассмотрим поиск числа 36"? А если серьёзно, ключевое слово - "первого", и это уточнение, как и в примере с количеством знаков числа $\pi$, сводит алгоритм к банальному выводу константы.

Да что мы всё о математике. Вот пример алгоритма не требующего ввода ("т.е. величин, заданных ему до начала работы"):

// Как узнать имя собеседника?
1. Задать вопрос: "Как тебя зовут?"
2. Получить ответ.

[Ринат]

Maslov в сообщении #346782 писал(а):

Т. е. Кнут почему-то не включает число 0 (используемое при проверке окончания работы) во входные данные :)

Точно, не заметил :)

Dandan в сообщении #346793 писал(а):

В том топике я объяснил то, что имел ввиду и никаких замечаний или несогласий не увидел. Если вы с чем-то не согласны - напишите там, обсудим.

Ну Вы же здесь пафосничаете, с чего ж тогда я в Вашем топике должен обсуждать память, алгоритмы и оценку O(1)? :)
К примеру,

Dandan в сообщении #346793 писал(а):

может еще и маленькую двоичку над буквой b запишем во входные данные ? Ах, есть же еще квадратный корень, а не, например, кубический. Тоже считаем как входные данные. Можем пойти дальше. У нас в алгоритме есть операция деления . А что если мы и ее запишем во входные данные? Мы ж в алгоритме именно делим, а не перемножаем или складываем числитель и знаменатель. Ну и т.д.

А почему бы и нет? Мы же можем записать алгоритм в виде

pw = 2;
rt = 2;
k = 4;

x1 = (-b + pow(pow(b, pw) - k*a*c, 1/rt)) / (2*a);

pw - вот Вам и двоечка, которую я могу поменять.
rt - вот Вам и показатель корня, который я могу поменять.

Так вот, прав, конечно, Maslov, так как для данного алгоритма значения постоянны и по сути являются частью самого алгоритма. А Вам просто хочу показать, что двоечки и корешки легко переправить под входные данные. А вот операции сложения, деления и др. сюда впутывать не стоит.