Связь математики и программирования. Новейший результат.

Тема в разделе "WASM.HEAP", создана пользователем Scholium, 20 фев 2012.

  1. Scholium

    Scholium New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2009
    Сообщения:
    96
    Здесь вот господин Касперский вольно или невольно распространяет тлетворное влияние Запада на русские умы. Чтобы переключиться в позитивное, конструктивное русло, представлю вам новейший результат из еще неопубликованной математической статьи, имеющей отношение, к программированию, точнее к его «родным» операторам: xor, or и and.

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

    Всем вам должны быть известны, действительные числа и их прямое обобщение – комплексные числа. Более начитанные возможно слышали об их дальних родственниках: кватернионах и октанионах (октавах или числах алгебры Кэли-Грэйвса). Все эти числа относятся к классу гиперкомплексных чисел либо, более конкретно, алгебрам Кэли-Диксона. Алгебры Кэли-Диксона строятся по принципу математической индукции. В качестве начальной обычно выбирается алгебра действительных чисел. Затем из алгебры порядка n с помощью итерационной процедуры Кэли-Диксона получается алгебра порядка n+1. Размерность каждой новой алгебры удваивается. Действительно, размерность действительных чисел равна 1, комплексных чисел – 2, кватернионов – 4, октанионов – 8, седенинов – 16 и т.д., до бесконечности. Интересующиеся подробностями могут прочитать в Интернете популярную статью: В.В. Сильвестров. «Системы чисел».

    Заметим, что числа Кэли-Диксона из соответствующей алгебры размерности 32 и выше не имеют даже названия.

    Короче, проблема состоит в том, что умножение базисных элементов в этих числах, в соответствии с процедурой удвоения Кэли-Диксона (КД), определяется соответствующими таблицами умножения, которые вы свободно можете найти в википедии для алгебр КД малой размерности. Многие математики пытались выявить связь между индексами i, j и k этих базисных элементов в формулах типа e_i * e_j = e_k, где индексы i, j и k пробегают значения от 0 до 2^n-1, в n-ой алгебре КД. Пока только получены мнемонические правила. Скажем для кватернионов базисные элементы e_0 = 1, e_1, e_2 и e_3 образуют таблицу умножения по принципу циклического сдвига элементов, положительного в порядке возрастания индексов 1, 2, 3, 1 и отрицательного в обратном порядке. Для алгебры октав, с числом базисных элементов 2^3=8, подобных циклических групп будет уже 7, которые, кстати, образуют аналогичную систему троек Штейнера. А соответствующее мнемоническое правило умножения определяется с помощью известной диаграммы (матроида) Фано (ищите в википедии). Для седенионов нет даже мнемонического правила. Хотя соответствующие тройки Штейнера для индексов базисных элементов седенионов, могут, теоретически, быть уже системой троек Киркмана, но так это или нет, никто не знает.

    Так вот, наконец-то мы можем сформулировать наш результат, который, частично, публикуется впервые. Вопрос, как индекс k в формуле умножения базисных элементов для алгебры КД, порядка n:

    e_i * e_j = e_k

    зависит от индексов i и j?

    Ответ. Первая его часть. С точностью до знака: k = i xor j. Отметим, про себя, коммутативность этой операции.

    Вторая часть ответа, которая определяет сам знак умножения, формулируется значительно сложнее и мне его трудно сформулировать здесь без возможности поддержки формул. Опишу только суть формулы. Это минус единица в некоторой степени, которая определяется всеми частичными бинарными представлениями индексов i и j и тремя операторами между ними, выбор которых зависит определенным образом от значений этих частичных представлений. Сами эти операторы такие. Два из них коммутативные: and и or один некоммутативный со следующей таблицей умножения: 0*0 = 0; 0*1 = 0; 1*0 = 1; 1*1 = 0. Именно этот оператор определяет некоммутативность чисел алгебры КД(n), а точнее антикоммутативность произведения любых базисных элементов, не включающих их нулевой элемент, равный 1 (который коммутативен). Соответственно, ассоциация произведения трех базисных элементов может быть как положительной так и отрицательной, другими словами, одни произведения базисных элементов ассоциативны, а другие антиассоциативны. И всю эту нерегулярность определяет представленный некоммутативный оператор без названия. Может, кто знает о его применении в программировании либо алгебре логики?
     
  2. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
  3. neutronion

    neutronion New Member

    Публикаций:
    0
    Регистрация:
    31 мар 2010
    Сообщения:
    1.100
    Все не так.
    Это новый Штирлиц в стане потенциального врага размножается и увиличивает армию наших агентов
    и имплантирует им пасхальные яйца. :)
     
  4. Scholium

    Scholium New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2009
    Сообщения:
    96
    Спасибо за информацию. Понятно, что любой оператор подобного типа можно вычислить исходя из базовых отношений. Однако названия инвертированной импликации я не знал, так же как и то, как можно использовать внешние формулы, поэтому Ваше сообщение весьма кстати [​IMG].

    Что ж, теперь можно сформулировать полученный результат более точно.

    Формулой умножения базисных элементов в алгебрах Кэли-Диксона, определенных с помощью процедуры удвоения Кэли-Диксона для начальной алгебры [​IMG] над полем [​IMG] и начальной инволюцией [​IMG] будет выражение:

    [​IMG],

    где

    [​IMG].

    Поскольку формула определения знака достаточно сложна, то я представлю ее чуть позже.
     
  5. rpy3uH

    rpy3uH New Member

    Публикаций:
    0
    Регистрация:
    14 сен 2006
    Сообщения:
    503
    в чём суть? какая польза мне, как программисту?
     
  6. MMIX

    MMIX New Member

    Публикаций:
    0
    Регистрация:
    9 дек 2011
    Сообщения:
    385
    rpy3uH
    Никакой, обыкновенная академическая заумь и нудятина, годная лишь для математиков-теоретиков. Исследования ради исследований. Переливание из пустого в порожнее, толчение воды в ступе етц. В математике разделов хоть жеппай жуй, а толку с них, кому они представляют интерес кроме как самих математиков ?

    Вона Перельман доказал некую научнаю куйню, его доказательство группа лиц проверяла чото там два года -- и что ? Толку с этих решенных надуманных "проблем" все равно не будет. Чистая математика есмь пустобрехство.
     
  7. sn0w

    sn0w Active Member

    Публикаций:
    0
    Регистрация:
    27 фев 2010
    Сообщения:
    948
    *офф
    вот за это я люблю васм))
     
  8. rpy3uH

    rpy3uH New Member

    Публикаций:
    0
    Регистрация:
    14 сен 2006
    Сообщения:
    503
    вот если бы ещё не было модераторов с вахтёрским синдромом в последней стадии, которые удаляют неиллюзорно доставляющие топики, васму цены бы не было!
     
  9. Blackbeam

    Blackbeam New Member

    Публикаций:
    0
    Регистрация:
    28 дек 2008
    Сообщения:
    965
    кватернионы нашли полезное применение при написании программного обеспечения для системы управления одним ... летательным аппаратом. без них все было очень плохо... задачи динамики полета сложны и в цифре решаются недостаточно быстро для некоторых практических целей.

    рекомендую необычайно интересную книжку: "Простая одержимость", Дербишир
    есть на инфаната.орг
     
  10. NeuronViking

    NeuronViking New Member

    Публикаций:
    0
    Регистрация:
    29 окт 2004
    Сообщения:
    480
    Адрес:
    где-то в Сиднее
    суть в том, что математика, это как известно не наука, но инструмент. иногда бывает, что инструмент несколько опережает свое время и многим непонятна его практическая применимость. вот мне например тоже не понятно - где и как это можно использовать. но самый главный вопрос - что это вообще такое ;) (риторический вопрос)
    вот кстати возможно найдется человек, который с помощью гиперкомплексных чисел докажет большую теорему Ферма в две строчки на полях тетрадки. тогда вопросы про пользу сразу же исчезнут и каждый начнет сожалеть о том, что именно он не смог увидеть очевидное.
     
  11. SEC70R_VA

    SEC70R_VA New Member

    Публикаций:
    0
    Регистрация:
    6 ноя 2011
    Сообщения:
    79
    Scholium
    тут подробнее и понятнее, чем у В.В. Сильвестрова:
    http://www.scientific.ru/journal/western/mislink.html
    http://www.kirsoft.com.ru/freedom/KSNews_179.htm

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

    P.S. и опишите, плз., поподробней, откуда взялись xor, or и and;
    ведь не всем математика даётся так просто.
     
  12. Dmitry_Milk

    Dmitry_Milk Member

    Публикаций:
    0
    Регистрация:
    20 ноя 2007
    Сообщения:
    535
    Scholium, а разве все написанное не выводится из символа Леви-Чивиты через четность перестановок индекса как частный случай для размерностей степени двойки?
     
  13. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.331
    забавно слышать это от человека со статусом "СуперМодератор" [​IMG], а за что, интересно, перебанили половину обитателей форума?
     
  14. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    1
    Регистрация:
    11 июн 2004
    Сообщения:
    3.500
    Адрес:
    Russia
    Mikl___
    Они наверно в курсе, за что )
     
  15. _JD_

    _JD_ New Member

    Публикаций:
    0
    Регистрация:
    3 июн 2011
    Сообщения:
    2
    они тут вместе с MMIX, sn0w и Malfoy устраивают срачи с регулярностью раз в 3-4 дня и троллят всех подряд. можно посмотреть историю. если тема перемещена или закрыта, то скорее всего эти они потрудились.

    а что греха таить, за это и любим васм!
     
  16. Scholium

    Scholium New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2009
    Сообщения:
    96
    У Сильвестрова изложено не только популярно, но и достаточно математически строго. Даются определения, указываются конкретные свойства гиперкомплексных чисел. В первой статье математического формализма нет вообще, зато показана диаграмма Фано:

    [​IMG]

    - мнемоническое правило вычисления произведения базисных элементов в восьмимерной алгебре октанионов. Сравните ее с нашей универсальной формулой:

    [​IMG] (*)

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

    Эта статья достаточно интересна, в смысле популяризации гиперкомплексных чисел. Правда, там присутствует общее заблуждение, что следует остановиться на изучении восьмимерной алгебры Кэли-Грэйвса. В математике вообще не должно быть каких-либо ограничений. Опыт показывает, что это неконструктивный путь. Что касается пассажей насчет «теории всего» с привлечением пяти исключительных групп G2, F4, E6, E7 и E8 алгебры Ли, многомерного пространства со «свернутыми» размерностями и так называемой М-теории, то пока это все физическая утопия. Математика этой модели очень сильно оторвалась от реальности и «живет» только за счет избыточных степеней свободы. Философы обычно говорят в таких случаях: «Это слишком общее, чтобы быть полезным, (конструктивным, эффективным)».

    Вторая статья это всего лишь небольшой экскурс в историю математики, не более того.

    Остаются все арифметические операции над любыми гиперкомплексными числами. Только в алгебрах размерности 16 и выше появляются делители нуля. Т.е. существуют числа, каждое из которых не равно нулю, но их произведение равно нулю. Проще всего это продемонстрировать на примере определения покомпонентного умножения чисел вида:

    (a, b) * (c, d) = (a*b, c*d).

    Для таких чисел

    (0, 1) * (1, 0) = (0, 0).

    В этом случае делителями нуля выступают, грубо говоря, «частичные» нули, которые появляются во многих алгебрах.

    «Новые отношения» заключаются, прежде всего, в некоммутативности и неассоциативности операции умножения. Но это всего лишь плата за обобщение. Кстати, в октанионах существует семь неизоморфных подалгебр кватернионов.

    Я готовлю полную статью на эту тему с подробными доказательствами. После публикации ее в Интернете, я дам ссылку. Кроме трех названых коммутативных операторов там еще присутствует один некоммутативный оператор: «инвертированная импликация» (спасибо за наводку l_inc) которая равна комбинации двух операторов and not, либо тоже самое: & ~ .

    «Откуда взялись»? Я так полагаю из фундаментальности процедуры удвоения Кэли-Диксона (КД). Связь фундаментальных чисел с фундаментальными операциями естественна, хотя и не очевидна.

    Еще один интересный момент, все числа q алгебр КД, начиная с комлексных, обладают следующим свойством:

    [​IMG] ,

    где [​IMG] – действительная часть числа q.

    [​IMG] ,

    причем, самое главное,

    [​IMG] .

    Тем самым все числа КД, начиная с кватернионов, индуцируют в себе обычный комплексный анализ. Это позволяет, например, вычислять аналитические функции кватернионов, октанионов, седенионов, . . . Смотрите, скажем, мою статью Интегральная формула Коши для кватернионов.
     
  17. Scholium

    Scholium New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2009
    Сообщения:
    96
    Нет, символ Леви-Чивиты определяется по-другому. У меня символ

    [​IMG] .

    для любых индексов i и j.
     
  18. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Scholium
    Я бы не советовал исходить из общепринятости данного термина. Импликация — известный оператор в алгебре логики. А инвертированной уже я её назвал исходя из тождества:
    [​IMG]
     
  19. SEC70R_VA

    SEC70R_VA New Member

    Публикаций:
    0
    Регистрация:
    6 ноя 2011
    Сообщения:
    79
    Scholium
    1. Если используете xor, надо бы задать ОДЗ для i,j;
    2. Универсальная + формула для знака будет выглядеть не так элегантно;
    3. Вероятно, комп.реализация будет эффективнее по диаграмме Фано.

    В рамках терминологии АЦП-ЦАП, Философия, как наука утратила всякую ценность. Математика предпочтительна.

    1. На множестве комплексных чисел пропадает отношение порядка;
    2. Кватернионы утрачивают коммутативность умножения;
    3. Умножение октонионов антикоммутативно и неассоциативно;
    Эти алгебры известны как "нормированные алгебры с делением", дальше операция умножение отсутствует как таковая.
    Делители нуля появляются в алгебре размерности 16. Если Вы настаиваете на алгебрах больших порядков, придётся объяснять потерянные свойства их операции сложение, или появление каких-либо новых свойств или ?операций?

    ИМХО, проще всего продемонстрировать на примере таблицы Кели для операции умножение, там где на пересечении строки и столбца стоит 0.

    Надеюсь касательно операторов xor, or и and, не покомпонентное сложение?
     
  20. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    SEC70R_VA
    ОДЗ вообще-то задано. На словах в посте #1. Формулой в посте #2.