Свойства программ
От: ON  
Дата: 04.07.05 17:05
Оценка:
Чем отличаются программы?
Существуют ли какие-нибудь признаки или свойства?
Чтобы не части текста и не шаблоны. Неформальные какие-нибудь.

Допустим есть программа сортировки строк пузырьком. Один программист излагает все свои мысли об этой программе на 5 страницах и передает их другому. Тот читает эту "загадку", и где-то на 3 странице его осеняет, что это сортировка пузырьком. Читает дальше и убеждается, что угадал правильно.
Posted via RSDN NNTP Server 1.9
Re: Свойства программ
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 05.07.05 05:09
Оценка: 2 (1)
Здравствуйте, ON, Вы писали:

ON>Чем отличаются программы?

ON>Существуют ли какие-нибудь признаки или свойства?
ON>Чтобы не части текста и не шаблоны. Неформальные какие-нибудь.

ON>Допустим есть программа сортировки строк пузырьком. Один программист излагает все свои мысли об этой программе на 5 страницах и передает их другому. Тот читает эту "загадку", и где-то на 3 странице его осеняет, что это сортировка пузырьком. Читает дальше и убеждается, что угадал правильно.

Насчет неформальных не знаю. Любой даже тривиальный алгоритм можно запрограмировать так, что никто никогда не поймет, что он делает. Лучше все же анализировать по формальным признакам. Для этого крайне желательно найти и прочесть:
1. Э.Дейкстра "Дисциплина программирования"
2. Д.Грис "Наука программирования"
3. Ч.Э.Р.Хоар "Взаимодействующие последовательные процессы"

Все книги труднодоставаемые, но поискать можно
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re: Свойства программ
От: Ranger_XL  
Дата: 05.07.05 05:44
Оценка:
Можно придумать для каждого алгоритма "канонический" вид. Формальный — в виде обобщенной записи (типа той, что использовал Дейкстра), неформальный — в виде графического изображения процесса. И обмениваться этими каноническими формами.

ЗЫ. вероятно, не для каждого алгоритма легко составить графическую аналогиию, но для некоторых алгоритмов-задач они существуют и широко известны (тот же пузырек, шейкер, двоичный поиск, ханойские башни, перестановка частей массива, генерация года Грея и т.д.)
Re: мотивы анализа алгоритмов
От: ON  
Дата: 05.07.05 10:03
Оценка:
1. Программисты вносят ошибки в программы т.к. элементы языка избыточны и остаются неучтенные свойства. На языке без избыточности ошибок будет меньше, но писать на нем будет не возможно, придется как-то угадывать единственно возможную правильную формулировку. Поэтому более естественно сделать максимально избыточный язык, чтобы программист совсем не напрягаясь свалил бы в кучу все свои идеи, а компилятор бы собрал код. Сейчас таких возможностей мало, приходится многое заносить в комментарии которые компилятор не читает, а отладочную логику нужно явно отделять от рабочей.
2. Помощь в кодировании. Если накопить базу свойств и алгоритмов, можно будет "понимать", что пишет программист. Сейчас создана масса кода, практически все уже переписано много раз, программисты просто не знают о его существовании. Система наблюдала бы что пишет человек и предлагала готовое. Типа intellisense, но поумнее.
3. Автоматическая генерация программ. Меня вот именно это интересует. Пользователь что-то делает, система наблюдает и пишет макрос. Как правило работа осмысленна и у человека существует вполне определенная задача и в море кода существует программа, которая эту работу выполняет. Если он не программист, не может написать программу, которая за него все сделает, он сможет начать работать вручную, а система распознает в его действиях логику, найдет соответствующую программу, прогонит ее и предложит человеку утвердить результат.

Я понимаю, что в целом программы анализу не поддаются. В основе лежит теория про Машину Тьюринга с ее проблемой остановки. Поэтому, единого теоретического метода теория МТ не дает. И в целом, для формальных систем по Геделю универсальных методов не может быть.

Но в реальных случаях все программы вполне можно понять, исправить, переписать на другом языке.
Видимо программисты мыслят более приземленными категориями. Либо вся суета происходит в каком-то подклассе программ, в котором нет теоретических проблем. И объем этого класса всех устраивает. Вероятно он может быть формализован, вот это будет настоящая революция в программировании.
Posted via RSDN NNTP Server 1.9
Re[2]: мотивы анализа алгоритмов
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 05.07.05 12:25
Оценка:
Здравствуйте, ON, Вы писали:

ON>3. Автоматическая генерация программ. Меня вот именно это интересует. Пользователь что-то делает, система наблюдает и пишет макрос. Как правило работа осмысленна и у человека существует вполне определенная задача и в море кода существует программа, которая эту работу выполняет. Если он не программист, не может написать программу, которая за него все сделает, он сможет начать работать вручную, а система распознает в его действиях логику, найдет соответствующую программу, прогонит ее и предложит человеку утвердить результат.


ON>Я понимаю, что в целом программы анализу не поддаются. В основе лежит теория про Машину Тьюринга с ее проблемой остановки. Поэтому, единого теоретического метода теория МТ не дает. И в целом, для формальных систем по Геделю универсальных методов не может быть.


Это вам в сторону искусственного интеллекта надо тогда глядеть. Но К.Геделя вместе с А.Тьюрингом, Э.Постом и С.Клини — действительно обойти не удастся: проблема неразрешимости рано или поздно выплывет во всей красе
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[3]: мотивы анализа алгоритмов
От: ON  
Дата: 05.07.05 12:56
Оценка:
> Это вам в сторону искусственного интеллекта надо тогда глядеть. Но К.Геделя вместе с А.Тьюрингом, Э.Постом и С.Клини — действительно обойти не удастся: проблема неразрешимости рано или поздно выплывет во всей красе

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

У меня пока 3 неформальных класса. Внутри них уже просто признаки-функции.

1. Подобие текстов.
2. Подобие лога работы. К примеру берем одну переменную и видим, что два алгоритма за время работы выполняли с этой переменной совершенно одинаковые действия.
3. Подобие результатов. То есть функции f1 и f2 подобны, если есть функция g такая, что для всех х g(f(x))=g(f2(x)).
Posted via RSDN NNTP Server 1.9
Re[4]: мотивы анализа алгоритмов
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 05.07.05 16:33
Оценка:
Здравствуйте, ON, Вы писали:

>> Это вам в сторону искусственного интеллекта надо тогда глядеть. Но К.Геделя вместе с А.Тьюрингом, Э.Постом и С.Клини — действительно обойти не удастся: проблема неразрешимости рано или поздно выплывет во всей красе


ON>Так я оттуда и гляжу

ON>Неразрешимость это теорема Успенского-Райса?
ON>Имхо, там все слишком обобщенно. Программисты в частных случаях это как-то обходят.

ON>У меня пока 3 неформальных класса. Внутри них уже просто признаки-функции.


ON>1. Подобие текстов.

ON>2. Подобие лога работы. К примеру берем одну переменную и видим, что два алгоритма за время работы выполняли с этой переменной совершенно одинаковые действия.
ON>3. Подобие результатов. То есть функции f1 и f2 подобны, если есть функция g такая, что для всех х g(f(x))=g(f2(x)).
Знаете, я сейчас, честно говоря, не готов обсуждать эти вещи — во-первых порядком все подзабыл, а во-вторых к сожалению никому это в общем не нужно, кроме таких любознательных как мы с вами Хотя тема интересная.
Я бы поглядел в сторону функционального программирования (всякие там lambda-исчисление, рекурсивные функции, одним словом — LISP). В сети можно найти статьи Дж.МакКарти по этой теме.
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[5]: мотивы анализа алгоритмов
От: ON  
Дата: 06.07.05 08:54
Оценка:
> Знаете, я сейчас, честно говоря, не готов обсуждать эти вещи — во-первых порядком все подзабыл, а во-вторых к сожалению никому это в общем не нужно, кроме таких любознательных как мы с вами Хотя тема интересная.

А по-моему это нужно всем, даже тем, кто компьютерами не пользуется, потому, что не умеют. Но в первую очередь программистам. И я еще не встречал человека, который готов это обсуждать
Posted via RSDN NNTP Server 1.9
Re: УСП программ
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 06.07.05 11:19
Оценка:
Здравствуйте, ON, Вы писали:

ON> Чем отличаются программы?


Хороший вопрос. Не Вы один думаете над этим.

Унифицированное семантическое представление программ
Unified Semantic Representation (USR)

http://www.inf.ethz.ch/personal/zueff/USRProjectRUS.htm

Re[6]: мотивы анализа алгоритмов
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 06.07.05 11:29
Оценка:
Здравствуйте, ON, Вы писали:

>> Знаете, я сейчас, честно говоря, не готов обсуждать эти вещи — во-первых порядком все подзабыл, а во-вторых к сожалению никому это в общем не нужно, кроме таких любознательных как мы с вами Хотя тема интересная.


ON>А по-моему это нужно всем, даже тем, кто компьютерами не пользуется, потому, что не умеют. Но в первую очередь программистам. И я еще не встречал человека, который готов это обсуждать

Ну, тогда вот вам цитата из книги Р.Пенроуза "Тени разума":
"... я решительно выступаю против широко распространенного мнения, согласно которому нашу сознательную мыслительную деятельность — во всех ее разнообразных применениях — можно, в принципе, адекватно описать в рамках тех или иных вычислительных моделей".
И далее:
"... сознательное мышление и в самом деле должно включать в себя процессы, которые с помощью одних лишь вычилительных методов невоможно даже адекватно смоделировать... Разум, по всей видимости, представляет собой такую сущность, которую никоим образом невозможно описать посредством каких бы то ни было вычислений".
Т.е. Пенроуз утверждает, что даже человеку недоступно истинное понимание механизмов мышления. Куды уж там научить этому компьютер
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[7]: мотивы анализа алгоритмов
От: ON  
Дата: 06.07.05 13:57
Оценка:
> из книги Р.Пенроуза "Тени разума"

Кроме механизмов и вычислений есть еще просто информация. Эти фразы Пенроуза означають лишь что нельзя приготовить вкусный обед из одних только тарелок и вилок. Говоря его языком. А в понятиях интуиционизма, неразрешимости и т.п. это действительно трудно понять, а тем более сделать практически из одних лишь проблем что-то полезное. Но я уверен это единственное направление в котором будет развитие, если оно вообще будет.

да мне всего-то хочется занять компьютер чем-то полезным для программиста...
Posted via RSDN NNTP Server 1.9
Re[2]: УСП программ
От: ON  
Дата: 06.07.05 13:57
Оценка:
> Унифицированное семантическое представление программ
> Unified Semantic Representation (USR)


Вы собираетесь сохранять базу "знаний" или все преобразования будут "на лету"?
Мне интересно как ее строить, просто с чистого листа.
Posted via RSDN NNTP Server 1.9
Re[3]: УСП программ
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 06.07.05 19:41
Оценка:
Здравствуйте, ON, Вы писали:

ON>Вы собираетесь...


Это не я, честное слово

ON>Мне интересно как ее строить, просто с чистого листа.


Мне тоже интересно.
Re[4]: УСП программ
От: ON  
Дата: 07.07.05 02:10
Оценка:
> Мне тоже интересно.

У меня есть идея, довольно очевидная.
А наука что говорит, как хоть это называется? Если в обычную сторону это выполнение, то в обратную — "заполнение", что ли...

А! понял, это называется программирование
Posted via RSDN NNTP Server 1.9
Re[7]: мотивы анализа алгоритмов
От: buriy Россия http://www.buriy.com/
Дата: 10.07.05 06:37
Оценка:
Здравствуйте, fplab, Вы писали:

F>Здравствуйте, ON, Вы писали:


>>> Знаете, я сейчас, честно говоря, не готов обсуждать эти вещи — во-первых порядком все подзабыл, а во-вторых к сожалению никому это в общем не нужно, кроме таких любознательных как мы с вами Хотя тема интересная.


ON>>А по-моему это нужно всем, даже тем, кто компьютерами не пользуется, потому, что не умеют. Но в первую очередь программистам. И я еще не встречал человека, который готов это обсуждать

F>Ну, тогда вот вам цитата из книги Р.Пенроуза "Тени разума":
F>"... я решительно выступаю против широко распространенного мнения, согласно которому нашу сознательную мыслительную деятельность — во всех ее разнообразных применениях — можно, в принципе, адекватно описать в рамках тех или иных вычислительных моделей".
F>И далее:
F> "... сознательное мышление и в самом деле должно включать в себя процессы, которые с помощью одних лишь вычилительных методов невоможно даже адекватно смоделировать... Разум, по всей видимости, представляет собой такую сущность, которую никоим образом невозможно описать посредством каких бы то ни было вычислений".
F>Т.е. Пенроуз утверждает, что даже человеку недоступно истинное понимание механизмов мышления. Куды уж там научить этому компьютер

Марвин Мински сказал следующее (где-то 70е годы):
"Разумность это химера, мы считаем данное действие разумным до тех пор, пока нам его не объяснили"
(http://rsdn.ru/Forum/Message.aspx?mid=660773&only=1
Автор: BUran
Дата: 01.06.04
)

Ну а объясненная последовательность действий — чем не алгоритм?
/bur
Re[8]: мотивы анализа алгоритмов
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 10.07.05 08:08
Оценка:
Здравствуйте, buriy, Вы писали:

B>Здравствуйте, fplab, Вы писали:


F>>Здравствуйте, ON, Вы писали:



B>Марвин Мински сказал следующее (где-то 70е годы):

B>"Разумность это химера, мы считаем данное действие разумным до тех пор, пока нам его не объяснили"
B>(http://rsdn.ru/Forum/Message.aspx?mid=660773&only=1
Автор: BUran
Дата: 01.06.04
)


B>Ну а объясненная последовательность действий — чем не алгоритм?


Алгоритм, конечно, кто же спорит ? Только речь изначально (насколько я понял) шла не о том, чтобы человек что-то объяснял машине, а чтобы машина сама могла наблюдать явление, находила ему объяснение (т.е. обладала свойством осознания) и автоматически генерировала некую программу. Вот простенький пример.
Возьмем такое абстрактное понятие как число, допустим "5". Человек довольно быстро обучается и ОСОЗНАЕТ (это — ключевое понятие — именно ОСОЗНАЕТ), что число "5" может означать разные вещи, например, "5-й дом от угла", "5 кубиков", "5 часов до поезда", "5 — это оценка за сочинение". Во всех этих случаях (контекстах) абстрактное понятие пятерки выполняет совершенно различные функции. Так вот вопрос состоит (ИМХО) в том КАК научить машину понимать, что во всех этих случаях абстрактное понятие числа выполняет конкретные (и различные) функции ? А таких случаем — множество. Вы что, предлагаете предварительно описать все возможные случаи использования пятерки, какие только можно вообразить и "засунуть" эти знания в машину ? Согласитесь, это не разумно, поскольку так вся жизнь уйдет на описание этиого и других математических понятий.
Возьмите другое понятие — "красный". Это может означать "красный цветок", "красную армию", электромагнитную волну с определенной частотой, "красну девицу". И опять — не описывать же это все !!!
Впрочем, это, кажется, уже из другой оперы
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[9]: мотивы анализа алгоритмов
От: buriy Россия http://www.buriy.com/
Дата: 10.07.05 09:37
Оценка:
Здравствуйте, fplab, Вы писали:

B>>Ну а объясненная последовательность действий — чем не алгоритм?


F>Алгоритм, конечно, кто же спорит ? Только речь изначально (насколько я понял) шла не о том, чтобы человек что-то объяснял машине, а чтобы машина сама могла наблюдать явление, находила ему объяснение (т.е. обладала свойством осознания) и автоматически генерировала некую программу.

При попытке описать поведение гениальных людей в направлении психологии под названием НЛП придумали для этой цели термин "когнитивная стратегия". С учетом этого термина, "наблюдение явления", "нахождение объяснения", и "программирование" — это классы алгоритмов, отличающиеся у разных людей но тем не менее обладающие некоторой общностью — они с некоторой отличной от нуля вероятностью добиваются цели, указанной в их названии
Ссылки дать?
F>Вот простенький пример.
F>Возьмем такое абстрактное понятие как число, допустим "5". Человек довольно быстро обучается и ОСОЗНАЕТ (это — ключевое понятие — именно ОСОЗНАЕТ), что число "5" может означать разные вещи, например, "5-й дом от угла", "5 кубиков", "5 часов до поезда", "5 — это оценка за сочинение".
Да не так уж и быстро, не в любом возрасте и не в любой ситуации. Кстати, есть африканские племена индейцев, которые не умеют понимать абстрактные понятия вообще. Зачастую это отражено и в их языке.
Так что не согласен с тем, что умение распоряжаться абстрактными понятиями есть нечто, изначально присущее человеку.
И что у вас означает "ОСОЗНАЕТ"? Понимает что-ли, что у него есть такое понятие, как "5" и что это именно "понятие"?

Давайте теперь проведем следующее интересное рассуждение.
Раз это умение (распоряжаться абстрактными понятиями) возникло в результате научения, значит, вероятно, его можно разложить на более простые умения, которые можно легко формализовать. А если вопрос стоит "повторить с некоторой точностью", то "вероятно" превращается в "почти всегда можно".
>Во всех этих случаях (контекстах) абстрактное понятие пятерки выполняет совершенно различные функции. Так вот вопрос состоит (ИМХО) в том КАК научить машину понимать, что во всех этих случаях абстрактное понятие числа выполняет конкретные (и различные) функции ? А таких случаем — множество. Вы что, предлагаете предварительно описать все возможные случаи использования пятерки, какие только можно вообразить и "засунуть" эти знания в машину ? Согласитесь, это не разумно, поскольку так вся жизнь уйдет на описание этиого и других математических понятий.
Два вопроса:
1) А вы что, других способов задания множества придумать не можете, кроме как перечисление объектов?
Более общий вопрос — почему ваш программистский ум отключился при переходе в другую область знаний?
2) А зачем все подряд "засовывать" в машину? Или вы хотите сказать, что человек знает все-все, и вопрос только в том, как это все теперь "запихнуть в память машины"?
F>Возьмите другое понятие — "красный". Это может означать "красный цветок", "красную армию", электромагнитную волну с определенной частотой, "красну девицу". И опять — не описывать же это все !!!
Детсад прямо. Если вы не представляете, как это сделать по-другому, это не значит, что других способов сделать это не существует.

F>Впрочем, это, кажется, уже из другой оперы

Да, полностью согласен.
/bur
Re[10]: мотивы анализа алгоритмов
От: fplab Россия http://fplab.h10.ru http://fplab.blogspot.com/
Дата: 10.07.05 10:05
Оценка:
Эти наши с Вами рассуждения уже, как мне кажется, не по делу После НЛП мы плавно перейдем к "Толкованию сновидений" З.Фрейда, "Рождению трагедии из духа музыки" Ф.Ницше, толкованию Апокалипсиса и пр., что, конечно, очень интересно, но все же в стороне от темы, поднятой автором топика. Мы говорим о программировании, как о математической дисциплине или о программировании, как о роде интеллектуальной деятельности ? Иными словами, вопрос стоял примерно так: "можно ли научить машину анализировать ?". Об этом (или почти об этом) и А.Тьюринг писал, и М.Минский, и Дж.МакКарти.
Вот интересный вариант обсуждения примерно о том же, но гораздо шире (http://forum.ixbt.com/0040/000691.html), которого хватит не на один день чтения
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[11]: мотивы анализа алгоритмов
От: buriy Россия http://www.buriy.com/
Дата: 10.07.05 11:03
Оценка:
Здравствуйте, fplab, Вы писали:

F>Эти наши с Вами рассуждения уже, как мне кажется, не по делу После НЛП мы плавно перейдем к "Толкованию сновидений" З.Фрейда, "Рождению трагедии из духа музыки" Ф.Ницше, толкованию Апокалипсиса и пр., что, конечно, очень интересно, но все же в стороне от темы, поднятой автором топика. Мы говорим о программировании, как о математической дисциплине или о программировании, как о роде интеллектуальной деятельности ? Иными словами, вопрос стоял примерно так: "можно ли научить машину анализировать ?". Об этом (или почти об этом) и А.Тьюринг писал, и М.Минский, и Дж.МакКарти.


Можно ли научить машину анализировать...

В общем случае задача "анализировать" не имеет смысла, поскольку у нее нет конкретного результата.
В более конкретных случаях:
Есть различные методы анализа данных, или, например, методы распознавания образов.
В SETI@home, думаю, накоплен большой багаж методов анализа числовых последовательностей.
Пожалуй, все программы, написанные через Pattern Recognition ("узнавание по шаблонам"), в более частном случае, через if-then правила, занимаются анализом.
Так что компьютер уже сейчас многое анализирует. И, пользуясь этим, каталогизирует новости, подправляет грамматику, управляет космическими кораблями.
Что из этого ваш "анализ"?
Я вам предлагаю выделять более конкретный класс задач, который предстоит решать.
Если вы хотите включить самообучение или автоподстройку алгоритмов (т.е. "самоанализ") в задачу анализа, то этот самоанализ тоже подразумевает некоторый класс задач. И в этом случае могу вас только направить на "Теорию языковых игр" Л. Витгенштейна, кратенько здесь

F>Вот интересный вариант обсуждения примерно о том же, но гораздо шире (http://forum.ixbt.com/0040/000691.html), которого хватит не на один день чтения

Не нужны мне эти тонны словесной руды. В свое время "наобсуждался".
/bur
Re[8]: мотивы анализа алгоритмов
От: VladD2 Российская Империя www.nemerle.org
Дата: 10.07.05 20:10
Оценка:
Просьба, уменьшить объем цитирования.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.