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

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

В последнее время на Хабре появилось несколько статей про самодельные компьютеры, созданные из различных нестандартных компонентов. Я тоже решил рассказать о своем компьютере, созданном в далеком 1993 году. На волне всеобщего увлечения синклерами, мне захотелось иметь полностью оригинальный 8-ми битный компьютер на основе z80 и, кроме того, создать для него программное обеспечение, начиная от операционной системы и заканчивая игрушками. Что из этого получилось, читайте под катом.

Не так давно на Хабре была статья про графический калькулятор TI-83, и, поскольку я являюсь обладателем TI-89 Titanium — калькулятором следующего поколения от Texas Instruments, под катом я решил рассказать про него, и показать, как для этого калькулятора можно создавать свои собственные программы на С.

На Хабре было несколько статей по решению японских кроссвордов, где авторы придумывали различные способы как такие кроссворды решать. В комментарии к статье Решение цветных японских кроссвордов со скоростью света я высказал мысль, что, поскольку, решение японских кроссвордов является NP-полной задачей, то и решать их надо с использованием соответствующего инструмента, а именно SAT солвером. Поскольку моя идея была встречена весьма скептически, я решил попробовать ее реализовать и сравнить результаты с другими подходами. Что из этого получилось можно узнать под катом.

На Хабре было несколько статей про генерацию кроссвордов. В одной из них «Самый сложный кроссворд, составленный компьютером» говорилось про очень сложный кроссворд, составленный компьютером, которому «пришлось немного помочь» вручную. Во второй статье «Алгоритм формирования кроссвордов» рассказывается про алгоритм, созданный автором для составления кроссвордов, и отмечается, что этот «самый сложный кроссворд» остался непокоренным и говорится, что «может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!». Что же, можно принять вызов. Что из этого получилось, смотрите под катом.

Однажды попалась мне игра пентамино, где было необходимо уложить 13 фигурок в квадрат 8 на 8. После некоторого периода времени, в течение которого я безуспешно пытался решить эту задачу, я решил, что необходимо написать программу, которая бы делала это за меня. Для этого необходимо было выбрать алгоритм решения. Первое, что приходит на ум — это обычный алгоритм ветвей и границ, когда фигурки укладываются одна за другой примыкая друг к другу (алгоритм с танцующими ссылками здесь не подходит, поскольку фигурки разные). Для ускорения этого алгоритма обычно используются различные эвристики, например, предпочтение отдается ветвлению с наименьшим количеством вариантов. Можно придумать и реализовать и другие эвристики в этом алгоритме, но тут я подумал, что множество различных ухищрений для ускорения решения подобных задач уже реализовано в SAT солверах. Поэтому, необходимо перевести задачу на соответствующий математический язык и воспользоваться каким-либа SAT солвером. О том, как это было реализовано и какие получились результаты можно почитать под катом.

Все знают игру крестики-нолики 3x3. При правильной игре при первом ходе крестиков результатом является ничья. Можно вручную составить дерево ходов, где на любой ход ноликов, существует ход крестиков, который ведет к наилучшему результату (для крестиков), то есть к ничьей или выигрышу. Это дерево ходов исчерпывает все варианты, поэтому говорят, что игра «решена». Существует трехмерная разновидность крестиков-ноликов 4x4x4 для которой ответ на вопрос, кто победит при первом ходе крестиков, не очевиден. Более того, возникает вопрос, можно ли построить такое минимальное дерево, которое будет решать эту задачу.

Ответ на этот вопрос под катом.

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

Памяти моего папы, Плеханова Станислава Петровича, посвящается.

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

Простой ответ — для того-же, для чего нужно 29 февраля — чтобы Новый Год со временем не сместился на лето.
Но откуда они возникают? Ответ под катом.

Deutsches Museum — самый большой музей техники в Европе. В нем существуют практически все разделы современной техники и, в частности, история развития вычислительной техники. Я хочу представить несколько фотографий, которые могут быть интересны широкому кругу читателей.

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

Написать данную статью меня вдохновила следующая задача:

Как известно из теоремы Котельникова, для того, чтобы аналоговый сигнал мог быть оцифрован а затем восстановлен, необходимо и достаточно, чтобы частота дискретизации была больше или равна удвоенной верхней частоте аналогого сигнала. Предположим, у нас есть синус с периодом 1 секунда. Тогда f = 1∕T = 1 герц, sin((2 ∗ π∕T) ∗ t) = sin(2 ∗ π ∗ t), частота дискретизации 2 герца, период дискретизации 0,5 секунды. Подставляем значения, кратные 0,5 секунды в формулу для синуса sin(2 ∗ π ∗ 0) = sin(2 ∗ π ∗ 0,5) = sin(2 ∗ π ∗ 1) = 0
Везде получаются нули. Как же тогда можно восстановить этот синус?

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

Первая часть здесь

Вторая часть здесь

Третья часть здесь

Часть 4. Мастерские и лаборатории

Продолжу свой рассказ про посещение дня открытых дверей в CERN.

Первая часть здесь

Вторая часть здесь

Часть 3. Вычислительный центр.

Продолжу свой рассказ про посещение дня открытых дверей в CERN.

Первая часть здесь

Часть 2. Центр управления.

Большинство, конечно, знают о существовании Большого Адронного Коллайдера и видели его фотографии, но вот вероятность посмотреть на него своими глазами для обыкновенного человека, я думаю, меньше, чем вероятность появления бозона Хиггса на этом самом коллайдере. Поэтому, когда летом на элементах.ру появилась маленькая заметка о том, что CERN (Центр Европейских Ядерных Исследований) в конце сентября проводит день открытых дверей, у меня не было сомнений — надо ехать.