Re[20]: Expression Tree для описания алгоритмов
От: BulatZiganshin  
Дата: 18.05.10 07:03
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>Кстати, ты будешь удивлен, но в хаскеле есть паттерн n+k и можно писать функции так


G>Так что там насчет далекости хаскеля от математики?


ты будешь смеяться, но хаскель 2010 от математики таки отдалился
Люди, я люблю вас! Будьте бдительны!!!
Re[21]: Expression Tree для описания алгоритмов
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 18.05.10 07:11
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

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


G>>Кстати, ты будешь удивлен, но в хаскеле есть паттерн n+k и можно писать функции так


G>>Так что там насчет далекости хаскеля от математики?


BZ>ты будешь смеяться, но хаскель 2010 от математики таки отдалился


Ну да, там убрали паттерн (n+k) мотивируя это тем, что оператор (+) может быть переопределен и паттерн не может это учитывать.
Re[15]: Expression Tree для описания алгоритмов
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.05.10 07:25
Оценка:
Здравствуйте, Mystic, Вы писали:

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


VD>>1. Не является описанием алгоритма Хоара.

M>Это одна и есть вариация метода быстрой сортировки, которая была предложена Хоаром. Вот его статья в том виде, в котором она появилась в 1962.

Ага, только ты процетировал даже не хоровский алгоритм. Посмотри внимательно, там идет речь об сортировке вставками (видимо как оптимизация).

M>Там алгоритм описан словами


Ага. Но не кнутовскими.

VD>>2. Не является математическим описанием, а является описанием на каком-то суржике с преобладанием русского языка.

M>А типа математическое описание только там, где нет слов?

Если 90% описания — это слова, то математики в нем чуть больше чем полностью нет.

M> Много лет алгоритмы описывались словами, а в случае необходимости формального описания приводился исходный текст программы. Чем это не математика? У тебя какое-то совсем узвое понимание


Дык я и говорил, что математика плохо пригодна для описания алгоритмов. Потому их словами и описывают. Причем если вообще обойтись без мат.символов, то станет только понятнее, а вот обратное не верно.

VD>>Так вот, описать алгоритм Хора средствами одной лишь математики практически невозможно. А если постораться это сделать, то у тебя получится запись очень близкая к записи получаемой на функциональных языках:

VD>>
VD>>

M>Нигде такой изврат не встречал.


Это говорит исключительно о тебе.

M> Алгоритмы очень часто встречаются в математических книгах. Для их описания часто используется словесная форма, используются (использовались) блок-схемы-алгоритмы, используется псевдокод.


Ага. Только вот псевдокод — это миф. Фактически используется выдуманный язык. Иногда даже (как в книгах Кнута) используется выдуманный ассемблер выдуманной машины.

M> Это можно найти довольно часто. А такого я не видел, может подкинешь ссылоку?


Можешь зайти тайти самоучитель по любому ФЯ. Там почти наверняка будет подобное описание.

M> Более того, это не алгоритм Хоара, по той причине, что алгоритм Хоара вполняет сортировку по месту.


Это алгоритм Хора. Алгоритм вообще не знает что такое место. Алгоритм — это абстракция.

M>Я бы не стал осквернять имя Хоара такой реализацией.


Ты бы лучше о своем имени думал. Несешь чушь с уверенностью достойной лучше применения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Expression Tree для описания алгоритмов
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 18.05.10 09:03
Оценка: 1 (1)
Здравствуйте, VladD2, Вы писали:

VD>Ага, только ты процетировал даже не хоровский алгоритм. Посмотри внимательно, там идет речь об сортировке вставками (видимо как оптимизация).


Да, оптимизация на последнем этапе. Хоар тоже об этом упоминал в своей работе.

VD>>>2. Не является математическим описанием, а является описанием на каком-то суржике с преобладанием русского языка.

M>>А типа математическое описание только там, где нет слов?
VD>Если 90% описания — это слова, то математики в нем чуть больше чем полностью нет.
VD>Дык я и говорил, что математика плохо пригодна для описания алгоритмов. Потому их словами и описывают. Причем если вообще обойтись без мат.символов, то станет только понятнее, а вот обратное не верно.

Описать алгоритмы можно, как можно описать машину Тьюринга. Можно ввести свои обозначения, описать любой язык программирования. Вопрос другой: а смысл? Часто словесного описания алгоритма более чем достаточно. Общепринятой формальной системы нет, и смысла в ней тоже нет. Ничто не мешает ее построить в соответствии с аксиоматикой, как те же конечные автоматы. Только это будет напрасный перевод бумаги: описание такой системы будет объемно и тривиально по содержанию Там гду нужна такая формализация появились языки программирования. Тем не менее, иногда они это чрезмерная детализация, которая не нужна.


M>> Алгоритмы очень часто встречаются в математических книгах. Для их описания часто используется словесная форма, используются (использовались) блок-схемы-алгоритмы, используется псевдокод.

VD>Ага. Только вот псевдокод — это миф. Фактически используется выдуманный язык. Иногда даже (как в книгах Кнута) используется выдуманный ассемблер выдуманной машины.
А в математике все выдумано, если на то пошло. Математика это плох воображения: если выдуманная система аксиом, в которой мы и работаем. В этой системе аксиом можно описать реальный ассемблер, а можно выдуманный. Можно описать Nemerle, C# и т. п.


M>> Это можно найти довольно часто. А такого я не видел, может подкинешь ссылоку?

VD>Можешь зайти найти самоучитель по любому ФЯ. Там почти наверняка будет подобное описание.
Там обычно идет исходник на этом ФЯ, не более того. Ибо возникает естественный вопрос: зачем математической символикой дублировать этот ФЯ? Любой язык программирования по сути может рассматриваться как математическая символика.


M>> Более того, это не алгоритм Хоара, по той причине, что алгоритм Хоара вполняет сортировку по месту.

VD>Это алгоритм Хора. Алгоритм вообще не знает что такое место. Алгоритм — это абстракция.
Еще как знает. Вся дисциплина "анализ алгоритмов" о том, как получать характеристики алгоритма, такие как затраты памяти, скорость выполнения, количество тех или иных операций и т. п. Если брать за оригинал статью самого Хоара, то все его формулы из нее ну никак не относятся к тому варианту, что ты привел. Например, там оценивается количество перестановок, которые выполняет алгоритм. Где они у тебя? Нет перестановок, значит это не Хоар, а другой алгоритм
Re[8]: Expression Tree для описания алгоритмов
От: nikov США http://www.linkedin.com/in/nikov
Дата: 18.05.10 09:25
Оценка:
Здравствуйте, VladD2, Вы писали:

N>>Потому что сейчас есть Curry.


VD>А ты сам то это чудо используешь?


На работе на нашем проекте используется только C# и VB.NET, так что нет.
Но у меня есть одна задачка, которой я собираюсь заняться в свободное время, и я как раз думал приспособить туда Curry.
Re[12]: Expression Tree для описания алгоритмов
От: Silver_s Ниоткуда  
Дата: 18.05.10 10:25
Оценка:
Здравствуйте, FR, Вы писали:

FR>Как язык пролог один из самых декларативных и читабельных, и вообще ближе к человеческому мышлению чем

FR>императивные и функциональные языки. Но при этом страшно неэффективен кроме очень узкой ниши.

Может эти прелести надо не Прологу приписывать, а списку правил т.е. списку импликаций?
Списки импликаций действительно вещь очень читабельная, хотя и недостаточная для создания всех промышленных систем.
Только вот стоит ли из этого пытаться делать самодостаточный язык. Если и возможно целиком на Прологе реализовать ERP или CAD систему, ве на Прологе от графики до логики, то читабельность будет просто ужасная.
А списки правил вида: если будет дождь -> взять зонт; если есть тучи ->будет дожь, оно конечно читабельнее чем код на C++ какой нибудь системы 3D моделирования.
Re[7]: Expression Tree для описания алгоритмов
От: vdimas Россия  
Дата: 18.05.10 19:44
Оценка:
Здравствуйте, nikov, Вы писали:


VD>>если говорить о Прологовском варианте (кстати, не пойму почему язык так не заслужено забыт!).


N>Потому что сейчас есть Curry.


Что-то я не нашел в туториале программирования в ограничениях и поиск решения. Наверно, он не совсем аналог Пролога.
Re[20]: Expression Tree для описания алгоритмов
От: Тролль зеленый и толстый  
Дата: 18.05.10 21:22
Оценка:
DM>См., например, обобщение математической индукции — структурную индукцию:
DM>http://en.wikipedia.org/wiki/Structural_induction

Нам в курсе математики структурную индукцию не давали. Я так понял, что структурная индукция — есть обобщение математической индукции на рекурсивные структуры данных, такие как деревья и списки.

В самой же математической индукции я ничего рекурсивного не вижу.
Re[20]: Expression Tree для описания алгоритмов
От: Тролль зеленый и толстый  
Дата: 18.05.10 21:28
Оценка:
ТЗИ>>Я не припоминаю, чтоб нас этому учили в рекуррентной форме.
G>Определения обычно не в рекурентной форме. А вычисления в рекурентной.

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

G>Да ну?

G>Вспоминаем как доказывать по индукции:
G>1)Определяем базовый (или несколько базовых случаев) при фиксированном N
G>2)Предполагаем что утверждение выполняется для N (формальность)
G>3)Доказываем для N+k, где k — константа и обычно равна 1

Ну вспоминаем. Че-то вы не то написали.

Для индукции нужно доказать истинность двух утверждений:

1) Истинность F(n),
2) Истинность импликации F(n) => F(n + k),

Тогда получаем истинность для всех F(n + k * i).

Вопрос: где тут рекурсия?

G>Так что там насчет далекости хаскеля от математики?


Я про далекость Хаскеля от математики не говорил.
Re[8]: Expression Tree для описания алгоритмов
От: Тролль зеленый и толстый  
Дата: 18.05.10 22:37
Оценка:
N>Можно написать и с деструктивным in-place обновлением (здесь, здесь), но будет уже не так коротко и понятно.

От. От это оно. Чего-ж спорить-то до усрачки, если сами все прекрасно понимаете?

Вот это он и есть самый квиксорт, о котором писал Хоар.

И не странно, что в этом алгоритме проступают знакомые императивные черты. А если еще фигурных скобочек добавить?

И, главное, какой "понятный" синтаксис! Какая легкость восприятия! Мммм... Переменные обозначены одной буквой, конечно ж, это от высокого функционального стиля. А функция processArray как-то слишком вульгарно-понятно называется — это фи, императивщина, надо было j или sigma.

import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
 
qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr
 
processArray :: (IArray a e, IArray b e, Ix i)
             => (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST $ do
    arr' <- thaw arr :: ST s (STArray s i e)
    f arr'
    unsafeFreeze arr'
 
quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = qsort' =<< getBounds arr
  where
    qsort' (lo, hi) | lo >= hi  = return ()
                    | otherwise = do
        p <- readArray arr hi
        l <- mainLoop p lo hi
        swap l hi
        qsort' (lo, pred l)
        qsort' (succ l, hi)
 
    mainLoop p l h  | l >= h    = return l
                    | otherwise = do
        l' <- doTil (\l' b -> l' < h  && b <= p) succ l
        h' <- doTil (\h' b -> h' > l' && b >= p) pred h
        when (l' < h') $ do
            swap l' h'
        mainLoop p l' h'
 
    doTil p op ix = do
        b <- readArray arr ix
        if p ix b then doTil p op (op ix) else return ix
 
    swap xi yi = do
        x <- readArray arr xi
        readArray arr yi >>= writeArray arr xi
        writeArray arr yi x
Re[21]: Expression Tree для описания алгоритмов
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 19.05.10 05:11
Оценка: +1
Здравствуйте, Тролль зеленый и толстый, Вы писали:

DM>>См., например, обобщение математической индукции — структурную индукцию:

DM>>http://en.wikipedia.org/wiki/Structural_induction

ТЗИ>Нам в курсе математики структурную индукцию не давали. Я так понял, что структурная индукция — есть обобщение математической индукции на рекурсивные структуры данных, такие как деревья и списки.

ТЗИ>В самой же математической индукции я ничего рекурсивного не вижу.

Осталось только понять, почему это обобщение: потому что натуральные числа — это частный случай рекурсивной структуры:
Nat = Zero | Succ Nat
(см. http://en.wikipedia.org/wiki/Peano_axioms )
В матиндукции из школьной программы мы доказываем истинность некого предиката Р(n) для всех натуральных n.
Зная, что n — это либо 0, либо k+1 некоторого натурального k, P превращается в рекурсивную функцию c двумя ветками: P(0) и P(n), выраженную через P(n-1). И наоборот — рекурсивную функцию над натуральными числами в приведенной форме можно рассматривать как индуктивное доказательство некоторого утверждения, справедливого для всех натуральных чисел.

Надеюсь, про прямую связь между функциями и доказательствами, а также типами и утверждениями вы знаете (изоморфизм Карри-Говарда).
http://thedeemon.livejournal.com/15889.html
Re[21]: Expression Tree для описания алгоритмов
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 19.05.10 05:58
Оценка:
Здравствуйте, Тролль зеленый и толстый, Вы писали:

ТЗИ>>>Я не припоминаю, чтоб нас этому учили в рекуррентной форме.

G>>Определения обычно не в рекурентной форме. А вычисления в рекурентной.

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


В средней школе и циклов, и рекурсии даже близко не было.

G>>Да ну?

G>>Вспоминаем как доказывать по индукции:
G>>1)Определяем базовый (или несколько базовых случаев) при фиксированном N
G>>2)Предполагаем что утверждение выполняется для N (формальность)
G>>3)Доказываем для N+k, где k — константа и обычно равна 1

ТЗИ>Ну вспоминаем. Че-то вы не то написали.


ТЗИ>Для индукции нужно доказать истинность двух утверждений:


ТЗИ>1) Истинность F(n)

Неверно, истинность F(n) предполагаем, доказывать надо для F(N0),F(N1)... — базовые случаи
ТЗИ>2) Истинность импликации F(n) => F(n + k),
Именно, и как это доказывается? Выражением F(n + k) через F(n) — вот тебе и рекурсия.
Re[9]: Expression Tree для описания алгоритмов
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 19.05.10 08:55
Оценка:
Здравствуйте, VladD2, Вы писали:

G>>
G>>let sum = fold (+) 0
G>>

VD>
VD>Func<List<int>, int> sum = lst => lst.Aggregate(0, (x, acc) => x + acc);
VD>


VD>так что некоторых фич нет.


О чём и речь.

VD>Так нет частичного применения, и вывод типов по хуже. Но базовые строительные блоки таки есть. И это позволяет писать на шарпе в функциональном стиле. Причем писать довольно не плохо.


Ну ты сравни строку на F# и C# Потом в C# операция определена только над списком целых, и я не знаю насчёт F#, а в Haskell тип схожего выражения будет

(Foldable f, Integral i) => f i -> i


Описание выделенного на C# будет ужасно
Re[10]: Expression Tree для описания алгоритмов
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.05.10 10:53
Оценка:
Здравствуйте, lomeo, Вы писали:

L>О чём и речь.


Цитировать надо добросовестно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Expression Tree для описания алгоритмов
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 19.05.10 10:59
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Цитировать надо добросовестно.


G>Даже в таком простом коде на F# используется несколько концепций, которых нету в C#.

VD> так что некоторых фич нет.
L>>О чём и речь.

Так пойдёт?
Re[12]: Expression Tree для описания алгоритмов
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.05.10 11:13
Оценка:
Здравствуйте, lomeo, Вы писали:

VD>>Цитировать надо добросовестно.


G>>Даже в таком простом коде на F# используется несколько концепций, которых нету в C#.

VD>> так что некоторых фич нет.
L>>>О чём и речь.

L>Так пойдёт?


Нет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Expression Tree для описания алгоритмов
От: Undying Россия  
Дата: 19.05.10 11:54
Оценка: :)
Здравствуйте, FR, Вы писали:

FR>Большинству людей как раз будет ближе функциональщина, так как они не программисты, а функциональщина ближе к математической нотации чем

FR>сиобразные.

Ты это всерьез считаешь, что большинству людей близка математическая нотация? Подавляющее большинство инженеров последний раз с математической нотацией сталкивается в ВУЗе, после чего с успехом ее забывает, т.к. практические задачи где она применима встречаются крайне редко.
Re[7]: Expression Tree для описания алгоритмов
От: FR  
Дата: 19.05.10 12:36
Оценка:
Здравствуйте, Undying, Вы писали:

U>Ты это всерьез считаешь, что большинству людей близка математическая нотация? Подавляющее большинство инженеров последний раз с математической нотацией сталкивается в ВУЗе, после чего с успехом ее забывает, т.к. практические задачи где она применима встречаются крайне редко.


А с нотацией или псевдокодом основанными на императивных языках программирвания они сталкиваются еще реже, и "изученный" бейсик или паскаль вылетает из головы гораздо быстрее чем математика.
Re[13]: Expression Tree для описания алгоритмов
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 19.05.10 12:59
Оценка:
Здравствуйте, VladD2, Вы писали:

L>>Так пойдёт?

VD>Нет.

Почему?
Re[14]: Expression Tree для описания алгоритмов
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.05.10 14:54
Оценка:
Здравствуйте, lomeo, Вы писали:

L>Почему?


Потому что цитата вырвана из контекста и ее суть искажена.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.