Marcus Darnley (darnley) wrote,
Marcus Darnley
darnley

  • Mood:

Немножко про работу

Немножко про работу. Пара шуток для посвящённых.

В одном маленьком, но полезном экселевском файлике живёт табличка, в которой записана вычислительная сложность нескольких маленьких, но полезных задач.

В течение последнего времени в некоторых графах этой таблички было чёрным по-белому написано: NPC, то есть NP-полные.

После одного разговора с kgeorgiy во всех этих ячейках появились записи о полиномиальном решении этих задач.

Всё-таки хороший научный руководитель — это хорошо!

И ещё одна профессиональная байка.

При написании программ плохим стилем считается (и правильно делается) использование «магических чисел» в коде. Например, вместо 2147483647 следует писать Integer.MAX_VALUE, а вместо 32 лучше подойдёт HEALTHY_ADULT_HUMAN_TEETH_AMOUNT.

Хороший стиль — это хорошо. И это относится не только к программистам.

Цитата из математической статьи; перевод мой, извините за корявость:

Лемма 5. При n ≥ 218000 существует разбиение вершин графа G на следующие три части:

  • Красная пара циклов из клик (U, P1, P2, V)
  • Синяя пара циклов из клик (X, Q1, Q2, Y)
  • Остаточное множество L1

Остаточное множество имеет размер не более 217990 + n/80 + 6(v + y) (где v = |V|, а y = |Y|), и все клики из циклов остаточного множества имеют размер между 8981 и 8989.
Более того, если обе цветных клики из циклов непусты, то |L| ≤ 217990 + n/120 + 6(v + y).
Tags: math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments