Войти
ФлеймФорумНаука

Теорема о бесконечных обезьянах в мире программирования или алгоритмов

#0
15:35, 17 июля 2018

Не стану мусолить что это за теорема, можно найти и прочитать.

Я лишь хотел экстраполировать на любой алгоритм, в любом коде, любого языка программирования (в частности языка C++). В теории, у любого текстового (пока что оттолкнемся от него) файла, при количестве символов, скажем, сотня, есть невероятно огромное количество возможных вариантов и комбинаций, другое дело что более осмысленные слова и тексты это капля в этом море по сравнению с этим хаосом из ASCII или Юникода. И предположим у нас есть язык программирования. Сразу отметаем океаны не совместимых синтаксически вариантов, и оставим только те что могут так или иначе скомпилироваться, запуститься и сработать. Понятное дело что даже удачных комбинаций не меньший океан чем может показаться на первый взгляд. Но, допустим, нам нужно реализовать какой-нибудь сверх сложный, и сверх-оптимизированный алгоритм. Задача, казалось бы, стоит довольно простая - создать самый оптимизированный и быстрый "алгоритм", но при этом чтобы не было никаких компромиссов (и уперлось только в абсолютный хардварь). Если так перебирать решения всеми коллективными разумами, какова вероятность того что "данный алгоритм" будет самым быстрым и самым оптимизированным в мире x86?


#1
16:09, 17 июля 2018

elviras9t
> Если так перебирать решения всеми коллективными разумами, какова вероятность
> того что "данный алгоритм" будет самым быстрым и самым оптимизированным в мире
> x86?
Зависит от алгоритма перебора.

#2
16:11, 17 июля 2018

elviras9t
> какова вероятность того что "данный алгоритм" будет самым быстрым и самым
> оптимизированным в мире x86?
Нулевая.

#3
16:35, 17 июля 2018

Я такую штуку делал: https://github.com/azhirnov/ProgramSynthesis
Только не через генерацию исходного кода, а через подобие ассемблера генерировать программу и потом дизасемблить в исходный код.
Если правильно оценивать сложность программы, то можно выбрать и сверхоптимизированный алгоритм, у меня пока просто задаются такты на каждую операцию, для сложных алгоритмов большее значение имеет кэш и прочее.
Ну и с поиском наилучшего результата проблемы - все оптимизирующие алгоритмы поиска находят кучу локальным минимумов и в итоге сводятся к брутфорсу.

Есть еще такой эксперимент с генетическим алгоритмом для написания кода на бейнфаке
https://github.com/primaryobjects/AI-Programmer

#4
17:44, 17 июля 2018

elviras9t
> Если так перебирать решения всеми коллективными разумами, какова вероятность
> того что "данный алгоритм" будет самым быстрым и самым оптимизированным в мире
> x86?
Вероятность конечно есть, но я думаю все люди задохнутся раньше, чем это произойдет. :)
Видишь ли в чем дело. Все молекулы воздуха движутся хаотически, и есть мааааленькая вероятность, что все молекулы окажутся например в другой части комнаты, и ты задохнешься.

#5
19:15, 17 июля 2018

Люблю побыть капитаном Очевидность.
Пусть существует возможность определить, что конкретный алгоритм самый оптимальный, как бы там ни задавался критерий оптимальности.
Тогда можно задействовать алгоритм перебора:
Проверить все алгоритмы, состоящие из одного бита,
Из двух,
Трёх,
И т. д.
Тогда вероятность для данного алгоритма оказаться самым оптимальным равна 1 / ((2 в степени (N+1))-2), где N - длина в битах для самого оптимального алгоритма.

#6
3:23, 18 июля 2018
+ баянчик в тему
#7
11:38, 18 июля 2018

Когда обезьяну учат программировать, получаются примерно вот такие алгоритмы:

/*
 * Increment the size file of the new incorrect UI_FILTER group information
 * of the size generatively.
 */
static int indicate_policy(void)
{
  int error;
  if (fd == MARN_EPT) {
    /*
     * The kernel blank will coeld it to userspace.
     */
    if (ss->segment < mem_total)
      unblock_graph_and_set_blocked();
    else
      ret = 1;
    goto bail;
  }
  segaddr = in_SB(in.addr);
  selector = seg / 16;
  setup_works = true;
  for (i = 0; i < blocks; i++) {
    seq = buf[i++];
    bpf = bd->bd.next + i * search;
    if (fd) {
      current = blocked;
    }
  }
  rw->name = "Getjbbregs";
  bprm_self_clearl(&iv->version);
  regs->new = blocks[(BPF_STATS << info->historidac)] | PFMR_CLOBATHINC_SECONDS << 12;
  return segtable;
}
А ещё обезьяну учили писать по Шекспиру и математические статьи... Получилось интересно, в общем. :)
#8
12:42, 18 июля 2018

elviras9t
> Если так перебирать решения всеми коллективными разумами

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

ФлеймФорумНаука

Тема в архиве.