Category: история

Category was added automatically. Read all entries about "история".

китайский пазл, фиолетовый, игрушка, бегемот, lilo
  • beroal

абстрактные методы решения задач

Сразу оговорюсь, что это не вопрос, а тема для обсуждения. Метод «разделяй и властвуй» все мы знаем. Есть ещё что-то на таком же абстрактном уровне? Примеры от меня.

Нужно найти неподвижную точку функции f. Пусть x — такая последовательность, что x(succ(n)) = f(x(n)). Находим такое наименьшее n, что x(succ(n)) = x(n). Говоря неформально, вычисляем последовательность, пока она не стабилизируется.

Частный случай предыдущей задачи, где f определена на векторах. (Вектор — это функция, определённая на некотором множестве V.) Здесь тоже вычисляем последовательность «недорешений» x. Параллельно вычисляем такую последовательность с, что ∀n ∀v v∈c(n) ↔ x(n)(v) = f(x(n))(v). с показывает, в каких точках x(n) «решён». Комплемент к этому множеству называется «agenda». x(succ(n)) вычисляем следующим образом. Выбираем «нерешённый» (принадлежащий agenda) u. Для всех v, если v=u, то x(succ(n))(v) = f(x(n))(v), иначе x(succ(n))(v) = x(n)(v). Другими словами, на одном шаге «решаем» один элемент вектора. c(succ(n)) вычисляется хитро, потому что изменение элемента вектора может сделать другие элементы «нерешёнными». Полное и формальное описание алгоритма могу привести, если кому-то надо.

Прикладные варианты этой задачи — алгоритмы на графах (V — множество вершин графа) (reachability, наиболее короткий путь), дедукция «снизу» (chart parser).
virtual dj
  • smash3r

Новая проблема (ML)

Задание разбито на 3 части.

1. Написать функцию вида delete(x, xl) которая удаляет первый попавшийся элемент x в списке xl.

2. Написать функцию вида augument(x, xl) которая добавляет x ко всем спискам в списке xl. К примеру augument(42,[[1024,2048],[0]]) выдаёт [[42,1024,2048],[42,0]]

3. Написать функцию вида permutations(xl) которая из списка xl делает список всех возможных комбинаций. Например из [1,2,3] получается [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]. Причём даются следующие намёки:

  • Множество всех пермутаций разделяется на подмножества в каждом из которых все списки начинаются с одинакового элемента


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


  • Для реализации этой функции предполагается использование двух предыдущих функций.


  • Вот, собственно, и всё. Пункты 1 и 2 я сделал почти без проблем:

    fun delete(x, xl) =
      if(null xl) then []
      else if (x = hd(xl)) then tl(xl)
      else hd(xl)::delete(x,tl(xl));
    
    fun augument(x, xl) =
      if (null xl) then []
      else (x::hd(xl))::augument(x, tl(xl));


    А вот с функцией permutations у меня ступор. Не может мой мозг такой завёрнутый алгоритм выдать. Может кто помочь?
    anonym_mouse

    О глубокой философии программирования (серьезный разговор)

    .
    Есть на Интернете программист-блоггер, 7 лет проработавший в Амазоне. Зовут его Стив Егге, и славен он тем, что в блоге публикует свои "rants" на компьютерные темы. Каждая запись - страниц 5 убористого текста. Многое разумно (ему 39 лет и он достаточно много программировал), но хотя бы из-за объема, многое противоречит себе же. Стив Егге - прототипический п..бол.

    И однако одна из записей поразила меня глубоким проникновением в тему. Я давно о ней размышлял, именно в таких, грамматических, терминах. Представляю вам где-то 2/3 его записи в сокращенном несколько виде.


    Steve Yegge:
    ИСПОЛНЕНИЕ КОРОЛЕВСКИХ ПОСТАНОВЛЕНИЙ[*] В ЦАРСТВЕ СУЩЕСТВИТЕЛЬНЫХ

    [*] - игра слов. В оригинале заголовок одновременно означает "Казнь в Царстве Существительных" (execution).

    Hello, world!
    Здравствуй, мир! Сегодня мы послушаем рассказ о Злом Царе Явы и его борьбу за всемирное уничтожение глаголов.

    ПРЕДУПРЕЖДЕНИЕ: у этой сказки нет счастливого конца. Эта сказка не для слабых духом ни для критикующего гласа. Если вы легко обижаетесь или превращаетесь в противного парня в своих комментариях, немедленно перестаньте читать.

    Прежде чем начать, разберемся с одним концептуальным изгибом.
    Collapse )