typedef

В теории графов я не силен, как, впрочем, и во всем остальном тоже. Но наткнувшись на этот метод поиска всех простых путей между двумя вершинами в графе, я немало удивился. А когда убедился, что метод работает, удивился еще больше. Приведу здесь наглядное описание метода.

1. Составляем структурную матрицу $A$ графа $G$. Элемент $a_{ij}$ матрицы содержит:
   • $0$, если в графе нет ребра $(i, j)$.
   • $1$, если $i = j$.
   • Имя булевской переменной, идентифицирующей ребро $(i, j)$. Если $i < j$, указывается сама переменная, а если $i > j$, то ее отрицание, например, $a_{ij}=x$ и $a_{ji}=\bar x$. Если между вершинами $i$ и $j$ несколько ребер, указывается их конъюнкция, например, $a_{ij}=x \wedge y$ и $a_{ji}=\bar x \vee \bar y$.
2. Для нахождения всех простых путей между вершинами $i$ и $j$ необходимо найти дополнительный минор $\bar{M}^j_i$ (вычеркнуть $j$-ую строку и $i$-ый столбец и найти определитель оставшейся матрицы) по следующим правилам:
   • вместо сложения/вычитания используется дизъюнкция;
   • вместо умножения используется конъюнкция;
   • $1$ выступает в роли истинного значения, а $0$ — ложного;
   • $x \wedge \bar x$ уничтожаются, ну и вообще, можно выполнять обычные булевские преобразования.
3. Получили булевское выражение в дизъюнктивной форме. Каждая конъюнктивная группа в нем соответствует маршруту между выбранными вершинами, а каждая переменная, входящая в группу, обозначает соответствующее ребро. Отрицания можно убрать, они показывают направление прохождения ребер.

Немного запутанно выглядит, да? Рассмотрим на конкретном примере. Возьмем полный граф с тремя вершинами. Ребрам сопоставим следующие переменные:

• $(1, 2)$ — $x$;
• $(1, 3)$ — $y$;
• $(2, 3)$ — $z$.

Структурная матрица тогда получится такой:

$$
A=\left( \begin{array}{ccc}
1 && x && y\\
\bar x && 1 && z \\
\bar y && \bar z && 1
\end{array} \right)
$$

Найдем все маршруты между вершинами 1 и 3. Вычеркнув третью строку и первый столбец, найдем значение минора:

$$
\bar M^3_1 = \left| \begin{array}{cc}
x && y \\
1 && z
\end{array} \right| = (x \wedge z) \vee y
$$

Вот и получилось, что есть два маршрута, один через ребра $x$ и $z$, а второй — через ребро $y$.

Красивый хак, а? Что интересно, как я ни старался, не смог найти описание этого метода в англоязычных источниках. Может, кто-то видел подобное?

P.S. Включите JavaScript для отображения формул. Если не работает, пишите в комменты вместе с версией браузера.

(2 голосов, средний: 5,00 из 5)
 Loading ...

Обновил движок блога, некоторое время могут быть глюки. Не обращайте внимания.

1. Программирование демократично (в отличие от, например, политики). В сообществе разработчиков нет выраженной иерархии. Нет «элиты», уровень которой недостижим для простых смертных. Общение с великими программистами доступно каждому — зайдите на любой популярный форум разработчиков и общайтесь, сколько влезет. Можете написать письмо Фаулеру или Степанову, и если письмо будет по существу, они скорее всего ответят.
2. Программирование справедливо. Все знаменитые программисты стали таковыми исключительно заслуженно. Шарлатаны моментально обнаруживаются и посему практически отсутствуют (или окучивают дилетантов).
3. Программирование доступно всем. За последние двадцать лет оно потеряло остатки своей элитарности, и теперь программистом себя называет каждый, кто написал «Hello, World» и знает несколько аббревиатур. Всем доступны среды разработки, компиляторы и вообще все необходимые инструменты для производства конечного продукта, в отличие от большинства «материальных» профессий (например, стеклодувов или специалистов по микроэлектронике).
4. Программировать сложно. Для разработки качественной программы нужно знать кучу разных вещей, и научиться этому за пару лет невозможно. Я вырос и перестал верить в Деда Мороза и малолетних разработчиков-гениев (олимпиады не в счет, они бесконечно далеки от реальности). Оптимистичным сроком обучения с нуля до уровня середнячка я бы назвал 6–10 лет. Тем не менее, подавляющее большинство считающих себя программистами таковыми не являются и никогда не будут.
5. Программирование требует наличия своеобразной манеры мышления. Об этом я уже писал.
6. Пользователи обычно не могут адекватно оценить качество программы. Всякий может посмотреть на результат труда писателя или художника и составить свое мнение. Но по поводу программы максимум, что можно услышать, — удобная она или нет; насколько программа корректно проверяет входные данные, насколько аккуратно обращается с памятью, продумана ли безопасность — все это невидимо. Зато когда вдруг исчезает квартальный отчет, все шишки падают на прибежавшего на крик сисадмина.

(Еще не оценили)
 Loading ...

Никакое человеческое исследование не может почитаться истинной наукой, если оно не изложено математическими способами выражения.

Леонардо да Винчи

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

---

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

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

Природа ценностей и их роль в социально-гуманитарном познании.

О да, трудно представить себе ученого, не имеющего понятия о роли ценностей в гуманитарном познании. Да такого нужно просто гнать из науки поганой метлой!

Меня всегда поражал подход социально-гуманитарных «наук»: прицепиться к какому нибудь определению или явлению (часто не понимая его сути) и навертеть вокруг этого целую теорию. Да, я могу назвать главную ценность гуманитарных наук. Их главная ценность — убедительность. Не важно что, не важно о чем. Если тебе поверили — твоя цель достигнута. К несчастью, многие ученые-естественники не умеют или не хотят говорить настолько же часто, много, убедительно и доступно для обывателей. В результате мнение о науке складывается не по выступлениям ученых и научным публикациям, а по интерпретации этой науки тружениками пера.

Например, все ли знают, что такое энтропия? Я был удивлен, что даже среди моих знакомых с техническим образованием многие считают что это некая таинственная «мера неупорядоченности», хотя энтропия —вполне конкретная термодинамическая величина, а мистический смысл она приобрела благодаря неверной интерпретации Больцмановского статистического ее определения.

Еще один пример — синергетика. Типа, теория самоорганизующихся систем. Да, название громкое. А начинаешь выяснять, чем занимается эта самая синергетика — выходит, что в общем-то ничем особенным. В основном, пытается оправдать собственное существование. Ну, типа физика с информатикой встретились, — бах! — новая наука. Фактически синергетика заключается в нескольких самоочевидных постулатах вроде такого:

Когда системы объединяются, целое не равно сумме частей.

Открытие века, блин! Каждый ребенок совершает такое открытие, собирая машинки из Лего. Куча запчастей сама по себе никуда не поедет, очевидно же. Синергетики это тоже в конце концов поняли, и решили еще заняться неравновесными состояниями. Вывели еще парочку постулатов:

Неравновесность в системе является источником появления новой организации (порядка).

В сильно неравновесных условиях системы начинают воспринимать те факторы, которые они бы не восприняли в более равновесном состоянии.

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

И ведь десятки тысяч людей что-то делают, пишут какие-то работы, получают деньги… Безо всякого полезного эффекта. И не только в синергетике, которая является международным помешательством. У нас хватает своих российских тараканов: торсионные поля, наношампуни «с экстрактами бриллиантов», разнообразные артефакты Петрика и прочая псевдонаука. Миллионы человеко-лет тратятся впустую. Так вот, философия сейчас — примерно такая же псевдонаука.

Всех аспирантов РАН заставляют приобретать книгу «Философия науки. Общие проблемы» Степина.  Объемом около 400 стр. Стоит она около 500 р. Автор книги, разумеется, сотрудник института философии РАН, где я и проходил обучение по оному курсу. Я такую тоже купил, куда деваться. Открываю, — а там первая глава «Предмет философии науки». Отлично, думаю, сейчас я наконец узнаю, чем же философия науки занимается. Глава занимает 7 страниц примерно такого текста:

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

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

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

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

• выделение отличительных черт науки — сложная задача;
• у науки есть множество различных определений;
• постоянно ведутся дискуссии о том, как бы, наконец, отделить науку от других форм познания.

Мда… Нет, я преувеличиваю, конечно, но в среднем так и есть — плотность информации в философских книгах (ладно бы книгах — учебниках!) исчезающе низкая. Нет бы написать, что, мол, такой-то мужик в таком-то веке думал так-то и так-то, вот список основных его тезисов, вот что ему возражали другие, вот что автор думает по этому поводу. Хрен!

И чему должна научить такая книга будущих ученых? Писать много и запутанно? Скрывать лживые утверждения за малопонятными выражениями? В реальности, похоже, цель этой книги — содрать 500 р. с каждого аспиранта. Пять старушек — рубль. Достойная цель для философа!

Впрочем, положительные впечатления от курса философии все же были. Первое — отличная лекция о математической аксиоматике, непонятно как попавшая в курс. Второе — семинары. Семинарская группа была маленькая и отбирали в нее исключительно математиков, физиков и CSов. Атмосфера соответствовала. Мы пили чай и читали друг перед другом доклады. Обсуждение любого доклада, скажем, о схоластическом образовании, довольно быстро сходилось к спорам по поводу постройки БАКа, обучения нейронных сетей или квантовой физики. Все попытки семинаристки вернуть нас в философское русло были обречены на провал — у нас была своя философия. Ее красноречие разбивалось о нашу логику. В конце концов, она осознала нашу безнадежность и свое бессилие.

На кандидатском экзамене все получили высший балл: семинары научили нас сводить любой вопрос к своей области науки. У экзаменаторов просто не было шансов.

После экзамена на меня внезапно снизошло просветление, и я постиг Главный Принцип Педагогики: «Чтобы хорошо делать X, нужно делать X. Разговоры об X такого эффекта не дают». Из этого Принципа я сразу же вывел следствие под номером один: «Чтобы человек стал ученым, нужно, чтобы он занимался наукой. Чтение книг по истории и философии науки ему не поможет».

---

Добавлено

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

(4 голосов, средний: 5,00 из 5)
 Loading ...

Утащил не помню где.

---

Бесконечное число математиков заходит в бар.
Первый заказывает полкружки пива, второй — четверть кружки, третий — одну восьмую…
Бармен:
— А-а-а… Не парьте мне мозг! Вот вам кружка пива!

---

Как физик доказывает, что все нечетные числа простые:
1 — простое,
3 — простое,
5 — простое,
7 — просое,
9 — ошибка эксперимента,
11 — простое,
13 — простое,
15 — ошибка эксперимента,
17 — простое,
19 — простое.
Доказано!

(5 голосов, средний: 5,00 из 5)
 Loading ...

А именно, XOrg 1.9 и несколько мониторов, сконфигурированные с помощью Xinerama, приводят к стабильному падению Qt- и некоторых Tk-приложений. Это подтвержденный баг. К сожалению, часто в репозиториях популярных дистрибутивов нужные фиксы появляются очень неторопливо, а жить с таким багом ну никак невозможно.

Исправляется баг элементарно: нужно накатить соответствующий патч на исходники иксов и пересобрать. Для арчеводов на форуме приведена подробная инструкция (подразумевает использование Arch Build System).

Обратите внимание на феерический комментарий к патчу:

This fixes a typo introduced in commit 80b5d3a3264d2c5167e5ac85a3b04af0f89cece1. The pointer pDst was changed unintentionally to pWin from a copy/paste error. This resulted in all QT-based apps and some tcl/tk ones (like fontforge) to crash X 1.9 on starting up, when Xinerama was enabled.

То есть, некто внес в код XOrg критическую ошибку в результате бездумного применения copy/paste. Для проекта такого уровня — эпический фэйл.