НГУ

Форумы НГУ
Текущее время: Чт июн 20, 2019 8:26 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 15 ] 
Автор Сообщение
 Заголовок сообщения: Определение алгоритма
СообщениеДобавлено: Ср июл 16, 2008 4:26 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
Алгоритму дают обычно примерно следующее определение:
Цитата:
Алгоритм - это конечный набор четких, недвусмысленных инструкций, следуя которым можно по входным данным определенного вида получать на выходе некоторый результат.

У меня вопрос - какое при этом подразумевается определение набора и инструкции? Набор, скорее всего, как-то можно определить через частично упорядоченные множества (помня о том, что алгоритмы бывают параллельными). Но не совсем понимаю - чем здесь отличается понятие инструкции от понятия алгоритма?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 4:30 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Да нет никакого определения алгоритма. Есть попытки формализации: конечные автоматы, формальные грамматики, машина Тьюринга и т.д.

Ваше определение точь-в-точь воспроизводит слова из первой страницы лекций С. Подзорова. Вы до конца дочитайте эти лекции, тогда поймете, что то, что автор назвал определением, -- это не определение, а пояснение.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 4:51 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
MaxVT писал(а):
Ваше определение точь-в-точь воспроизводит слова из первой страницы лекций С. Подзорова.

Да, оттуда я его и списал, был вариант из Википедии, но там оно какое-то рваное получилось.

Можно задать вопрос иначе: всякое ли преобразование является алгоритмом (и наоборот)?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 4:53 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Имярек писал(а):
Можно задать вопрос иначе: всякое ли преобразование является алгоритмом (и наоборот)?
Что значит "преобразование"?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 5:02 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
В моём понимании, преобразование - это некоторое отображение одного множества в другое. Множества допустимых входных наборов данных в множество выходных наборов (результатов).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 5:10 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Имярек писал(а):
В моём понимании, преобразование - это некоторое отображение одного множества в другое.
Всё-таки Вам следует дочитать лекции до конца. Тогда Вы узнаете про рекурсивные функции -- еще одну формализацию алгоритма. А Ваши множества будут называться конструктивные пространства.

А также познакомитесь с понятием вычислимая (в интуитивном смысле) функция -- это как раз наше интуитивное представление об алгоритме. Существут тезис Тьюринга о том, что всякая вычислимая (в интуитивном смысле) функция вычислима на машине Тьюринга. Тезис -- потому что доказывать его бессмысленно, ибо вычислимая (в инуитивном смысле) функция не определена точно так же, как не определено общее понятие алгоритма. Поэтому вычислимую в интуитивном смысле функцию формализуют до математически строгого понятия частично рекурсивной функции. Есть теорема о том, что любая чрф вычислима на машине Тьюринга. Естественно, от такой формализации мы кое-что теряем в плане общности, но зато у нас получается строгая математическая теория, а не игра в слова.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 5:16 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
Да читал я - Верещагин и Шень, что не понял, что забыл :). В лекциях не очень удобно, что оглавления нет. Посмотрю. Но если быстрей объяснят - не буду против :).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 5:19 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Верещагин, Шень -- это слишком просто. Если хотите хороших лекций по теории алгоритмов, и даже с оглавлением, то ищите в интернете лекции Березнюка, Когабаева (с оглавлением), Морозова (с оглавлением), Подзорова. У меня они все есть. Могу Вам их как-нибудь отправить.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 8:00 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
Цитата:
Конструктивным объектом называется такой объект, который может быть полностью описан при помощи конечной последовательности символов.

Пока читаю - такой глупый вопрос: рассматривались ли когда-нибудь модели, в которых такая последовательность символов является не конечной, а счётной? То есть - есть ли какие-то принципиальные ограничения на этот счёт, можно ли там ввести невычислимость и т.п.? Или такая модель вообще не имеет смысла?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 8:07 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
Имярек писал(а):
Цитата:
Конструктивным объектом называется такой объект, который может быть полностью описан при помощи конечной последовательности символов.

Пока читаю - такой глупый вопрос: рассматривались ли когда-нибудь модели, в которых такая последовательность символов является не конечной, а счётной? То есть - есть ли какие-то принципиальные ограничения на этот счёт, можно ли там ввести невычислимость и т.п.? Или такая модель вообще не имеет смысла?
Почему же глупый? Я с теорией вычислимости знаком не далее, чем по лекциям. Вот придет Коба и всё объяснит.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 8:13 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
MaxVT писал(а):
Почему же глупый? Я с теорией вычислимости знаком не далее, чем по лекциям. Вот придет Коба и всё объяснит.

Может сам докопаюсь к тому времени :)

MaxVT писал(а):
Хотя странно это как-то. Если последовательность символов не является конечной, то как алгоритм может завершить работу с объектом?

Не знаю пока, но хотелось бы описать конструктивный объект векторами [бесконечномерного] гильбертова пространства. Определение не позволяет :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Определение алгоритма
СообщениеДобавлено: Ср июл 16, 2008 8:49 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Имярек писал(а):
Алгоритму дают обычно примерно следующее определение:
Цитата:
Алгоритм - это конечный набор четких, недвусмысленных инструкций, следуя которым можно по входным данным определенного вида получать на выходе некоторый результат.


Это Вы процитировали "определение" из самой первой, вводной лекции моего курса.

Понятно, что оно нестрогое. Слова "набор" и "инструкция" здесь следует понимать в широком, неформальном смысле.

Если хотите строгости --- читайте дальше :)

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 8:52 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср июл 16, 2008 4:14 pm
Сообщения: 7
Да читаю я, читаю :)

Насчёт счётности вот вопрос интересный...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср июл 16, 2008 8:58 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
MaxVT писал(а):
Если хотите хороших лекций по теории алгоритмов, и даже с оглавлением, то ищите в интернете лекции Березнюка, Когабаева (с оглавлением), Морозова (с оглавлением), Подзорова. У меня они все есть. Могу Вам их как-нибудь отправить.


http://www.nsu.ru/education/podzorov/Alg/Course.pdf

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

http://www.nsu.ru/dmi/index.php?option= ... =0&limit=5

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 20, 2008 4:54 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт апр 01, 2004 9:20 pm
Сообщения: 19
Откуда: Евгений Павловский
В принципе можно и бесконечномерные пространства рассматривать. Например, возьмём пространство всех таких (x_0,x_1,...,x_n,...) "векторов" натуральных чисел, которые устроены конструктивно, т.е. для каждого такого вектора существует вычислимая функция f, что f(0)=x_0, f(1)=x_1 и т.д. Тогда пространство всех таких векторов будет счетным, т.к. всех таких функций будет счетное число.

На самом деле это будет такое же конструктивное пространство, т.к. каждому "вектору" будет соостветствовать как минимум одно натуральное число (номер функции, кодирующей вектор), если включить в понятие "вектор" и наборы значений частичной функции (где-то неопределенной).

Но если не рассматривать "неопределенные векторы", то получится не вполне конструктивное пространство... Т.е. нет такой вычислимой нумерации, с помощью которой можно будет занумеровать все элементы этого пространства. А это уже вопрос интересный. Можно ли на таком пространстве задать функции, метрики, что-нибудь ещё?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB