ML Class близок к идеалу. Именно таким должен быть настоящий учебный курс — невероятно простым, невыносимо нудным, но при этом дающим твердое понимание того, что происходит и как это работает. Рижским бальзамом на душу льются слова Andrew Ng: «Если вы это не понимаете, не переживайте, сейчас я расскажу, поймете» или «Если вы это не понимаете, не переживайте, я тоже не понимаю, это вам не нужно«. Ну и прочие подобные высказывания и шутки вроде «Если вы эксперт в линейной алгебре и знаете, что такое собственные вектора, то …» доставляют. Столько студентов сразу почувствовали себя экспертами в линейной алгебре! Отдельная благодарность за возможность ускорить лекции в 1.2 и 1.5 раза.

AI Class имеет гораздо больший охват материала, но при этом он менее проработанный. Куча несогласованной терминологии, много недосказанного, вопросы иногда расплывчаты и имеют слабое отношение к тексту. Постоянно происходят какие-то технические накладки, то сроки отодвигаются, то публикуются уточнения к вопросам, то еще какая напасть. Это не говоря уже об очаровательном немецком акценте Prof. Sebastian Thrun, которого я, в отличие от ускоренного Andrew Ng, понимал только процентов на 95 — некоторые фразы не могли понять даже native speakers. Но, несмотря на все недостатки, получился очень неплохой обзорный курс.

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

В целом нисколько не жалею, но курсы будущего семестра — разве что в пассивном режиме посмотрю.

Черт, да что же это за месяц такой…

Категорически не соглашусь. Лично для меня курс философии науки стал, не побоюсь этого слова, откровением. Можно сказать, поворотным пунктом. Когда в школе и в вузе проходят различные науки, совершенно не затрагивают тему того, насколько мы можем быть уверены в предлагаемом знании. И у каждого слушателя формируется своё весьма наивное представление о сущности истины и человеческого знания. Кто-то, например, освоил какой-то метод в какой-то области, сидит и только его применяет, а всё остальное считает ересью. А кто-то, скажем, любое порождение своего мозга принимает за великое открытие. Кто-то считает математику непогрешимой, а кто-то – что математика вообще ни на что не способна. Немалая доля людей вовсе науку не признаёт, а верит в различное НЛО и т. п.

Курс же философии науки знакомит нас с тем, как различные (не самые глупые) люди подходили к решению означенной проблемы. А проблема очень серьёзная – можем ли мы доверять научному или какому-либо ещё знанию? Как нынче принято говорить, краткий ответ – нет. Но если мы углубимся ещё немного, то оказывается, что лучше всё же доверять научному знанию, чем не доверять. В общем, там очень много весёлого, так в двух словах не перескажешь. Скажу лишь, что современной науке по моему представлению наиболее соответствует эволюционная эпистемология, а современному общественному сознанию – постмодернизм. Разумеется, сей курс не даёт правильного ответа – именно в силу невозможности абсолютного познания истины. Но он заставляет задуматься над тем, правильно ли то, что ты делаешь. Я категорически утверждаю, что философия науки необходима любому человеку, претендующему на то, что он занимается наукой, а не просто наливает раствор А в раствор Б.

Возможно, автору просто не повезло с преподавателями оного курса.

Я вам тоже могу открыто признаться, что не мог терпеть философию до тех пор, пока не прослушал курс философии науки в аспирантуре. В том числе когда проходил «философию» на четвёртом курсе.

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

> В этой области множество людей столетиями придумывали термины, «законы» и «принципы».

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

> до какого-нибудь Витгенштейна

Витгенштейн, равно как и вся философия науки двадцатого века, совершенно напрямую связан с математикой и проблемами построения искусственного интеллекта. Ещё раз повторю, что ни его, ни любого другого философа не следует принимать на веру. Просто полезно на минуту представить себя в его шкуре.

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

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

> Нет, я согласен, что при наличии хорошего преподавателя это может быть даже интересно, но нужно ли?

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

Ежели спрашивать лично меня – то я бы исключил литературу и русский язык из школьной программы за полной бесполезностью. Оставил бы только чтение-запись в начальной школе.

Кстати, вот ещё вспомнил. Одна из основных задач философии науки – это отличать науку от ненауки. В связи с нынешним засильем мракобесия и «альтернативной» науки это становится как никогда актуально. Грубо говоря, учёный, занимавшийся только наукой и не занимавшийся философией, скорее всего, правильно определит, кто есть кто, по крайней мере в своей области. Но вот убедить другого человека, что это так – это уже задача посложнее. Скорее всего, его аргументы сведутся к «это же очевидно любому здравомыслящему человеку» и «пойди ещё раз поучись в школе». Тогда как знакомство с философией и методологией науки даёт некоторые критерии (прежде всего фальсифицируемость) и приёмы убеждения. Хотя, к сожалению, переубедить «адепта» всё равно почти никогда не получается, но по крайней мере ты сам от такого спора не будешь погружаться в состояние отчаяния от осознания своего бессилия оправдать научную точку зрения.

Из конкретных философских трактатов могу порекомендовать разве что статью Карла Поппера об эволюционной эпистемологии http://www.keldysh.ru/pages/mrbur-web/philosophy/popper.html . Также не совсем по теме, но всё же – Ричард Докинз «Эгоистичный ген».

Что интересно, мой вариант более чем вдвое короче, чем представленный в Википедии.

main(){char*p="main(){char*p=%c%s%c,c='%c',s[256];sprintf(s,p,c,p,c,c);puts(s);}",c='"',s[256];sprintf(s,p,c,p,c,c);puts(s);}

Изобрел я его совершенно случайно как побочный эффект своих рабочих дел. Опечатавшись, указал в printf() форматную строку как один из подставляемых аргументов, подставив тем самым форматную строку саму в себя. Сразу появились ассоциации с квайнами, повозился минут 15 — и готово. Заодно запостил в соответствующий раздел Codegolf@Stackexchange.

Добавлено

Оказывается, этот подход уже сто лет назад как придумали, и программа намного короче:

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

В общем, я изобрел велосипед, ура.

1
2
3
4
5
6
7

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
}
cout << "Your input: " << value << endl;

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

Беглый гуглеж приводит меня к функции istream::sync(), которая, как говорит один источник, делает именно то, что нам нужно:

Synchronizes the buffer associated with the stream to its controlled input sequence. This effectively means that the unread characters in the buffer are discarded.

Что ж, попробуем:

1
2
3
4
5
6
7
8

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
    cin.sync();
}
cout << "Your input: " << value << endl;

Хм. В моей системе результат не изменился, код работает точно так же, как и первый. Беда в том, что функция istream::sync() в некоторых реализациях стандартной библиотеки таки отбрасывает непрочитанные символы. Но не в моем случае.

А я человек простой — лезу в код своей стандартной библиотеки и смотрю что да как. Выходит, что istream::sync() вызывает stdio_sync_filebuf::pubsync(), которая вызывает stdio_sync_filebuf::sync(), которая, наконец, вызывает fflush(stdin). Понятно, что fflush(stdin) не может оказать никакого влияния на входной буфер cin.

Так что упомянутый выше «один источник» не стоит считать истиной в последней инстанции. Но надо сказать, что попытки найти истину в стандарте — еще более неблагодарное занятие.

В общем, правильное решение заключается в использовании функции istream::ignore() таким вот образом:

1
2
3
4
5
6
7
8

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
cout << "Your input: " << value << endl;

Надо отметить, что вызов ignore() неплохо бы вставлять даже после успешного ввода, так как при вводе строки «123qwe» первые три символа будут прочитаны и распознаны как число, а «qwe» останутся во входном буфере и будут портить жизнь при следующем чтении. Еще одна тонкость — обработка конца файла. Если пользователь в ответ на приглашение к вводу нажмет Ctrl+D или что там в вашей системе для этого предназначено, то программа вместо того, чтобы завершиться, сообщит о неверном формате и предложит ввести число еще раз. Поэтому по-хорошему код должен быть вроде этого (вся программа):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <limits>
using namespace std;
template <typename Type>
bool read_value(const std::string &prompt, Type &value)
{
    bool repeat = true;
    bool eof = cin.eof();
    while (repeat and not eof) {
        cout << prompt << ": ";
        cin >> value;
        eof = cin.eof();
        repeat = cin.fail() and not eof;
        if (repeat) {
            cout << "***Invalid data format!" << endl;
            cin.clear();
        } else if (eof) {
            cout << "(EOF)" << endl;
        }
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }
    return not eof;
}
int main()
{
    int value = 0;
    while (read_value("Input integer", value))
        cout << "Your input: " << value << endl;
}

Но и в этом, казалось бы, безошибочном, коде затаилась пара граблей. Например, что если функцию read_value() использовать для ввода символов или строк? Сумеем мы ввести символ пробела? Сумеем ли ввести строку из нескольких слов, разделенных пробелами? Хрен! С вводом символа пробела еще несложно — надо только использовать манипулятор noskipws, а вот ввод строк с пробелами потребует перегрузки read_value() и использования getline() вместо оператора >>.

В общем, писать на C++ — сплошное счастье.
Note: There is a rating embedded within this post, please visit this post to rate it.

• Объектно-ориентированный bash.
• Bash on Balls — web-framework на bash.

1. На младших курсах все студенты изучают математический анализ. Это очень непростой для неокрепших умов предмет, и самое непростое в нем то, что когда его изучаешь, ты абсолютно не понимаешь, зачем все это нужно. Понять доказательство теоремы Вейерштрасса или разложение в ряд Тейлора в принципе можно, но должно пройти немало времени, прежде чем может быть у кого-то возникнет дежа вю — «Кажется, что-то такое я учил на первом курсе… Но уже нифига не помню». Хуже всего, если эти знания действительно нужны, и приходится открывать учебники и учиться заново. Во второй раз изучать получается быстрее, но все равно время жалко.
2. На младших курсах многие студенты изучают еще и разнообразную физику. Это вообще труба, потому что используемый в лекциях матаппарат студенты еще не проходили. В результате физику никто не знает, а когда приходит время изучать тот матаппарат, то параллели провести тоже не получается — едва ли кто-то воскликнет «Так вот что, оказывается, имел в виду наш физик год назад, когда говорил о линейных операторах!».

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

Мне придумалась образное объяснение, почему так происходит — теория крючков. Она состоит из следующих постулатов:

1. Поглощаемые человеком знания ищут в мозгу крючки, за которые могут зацепиться. Чем больше таких крючков, за которые зацепилось некоторое знание, тем дольше оно останется в мозгу.
2. Крючки типизированные: определенным знаниям нужны определенные крючки. Нельзя зацепить знания о языке Фортран за крючки, относящиеся к плаванию кролем.
3. Хотя некоторые уникумы умудряются нарушать типизацию крючков, проводя смелые аналогии в различных областях знаний.
4. Закрепленные в мозгу новые знания сами начинают создавать крючки. Больше знаний — больше крючков — проще усваиваются новые знания.

Попробую продемонстрировать эту теорию на ней же самой. Эти постулаты сами по себе не очень ценны — какие-то утверждения, сделанные неизвестно кем непонятно с какой целью. Если трактовать их именно так, то на следующий день после прочтения они из головы сотрутся. Но можно прицепить их крючками к уже известным фактам, наведя между ними «знания-мосты». Такими мостами могут быть, например, следующие факты:

• Когда знаешь много языков программирования (или иностранных языков), изучить еще один — гораздо более простая задача, чем изучить первый. Новый язык цепляется за множество крючков, выращенных уже изученными языками.
• Система крючков гуманитария кардинально отличается от оной у технаря. Поэтому технические понятия гуманитарии воспринимают с трудом — крючки не подходят!
• Проводить аналогии между программированием и постройкой домов, литературой, живописью, вышиванием крестиком или выращиванием цветов — нарушение типизации крючков. Но кто сказал, что это плохо?
• Теория, пересыпанная примерами, изучается куда проще, чем сначала куча теории, а потом куча примеров. Поглощая знания маленькими кусочками, мы цепляем их друг к другу, не давая им успеть забыться. С большими кусками сложнее. Это все равно как есть очень длинную колбасу — пока доедаешь ее конец, начало уже давно переварилось и путешествует по канализации.
• В этом посте неимоверное, зашкаливающее количество употреблений слова «крючок».

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

Написать программу на C, компилирующуюся без ошибок (warning-и не в счет), которая при запуске выводит «YES», если вложенные комментарии поддерживаются, и «NO», если это не так.

Механизм, вокруг которого должна строиться такая программа, очевиден — вложенные комментарии:

/* всегда в комментарии /* всегда в комментарии */ какой-то-код */

Если вложенность поддерживается, какой-то-код — всего лишь часть комментария. Но если вложенности нет, то комментарий кончается на первом же «*/», а какой-то-код будет выполнен. Проблема только в одном: что делать с остающимися в хвосте «*/»? Наверное, нужно где-то раньше поместить парные «/*», но тогда код станет некорректным в случае, если вложенность поддерживается. Нетрудно видеть, что написание комментариев с еще большей глубиной вложенности лишь усугубляет проблему.

(Здесь самое время прекратить читать и попытаться придумать решение самостоятельно.)

Ключ к решению — различная лексическая трактовка символов в зависимости от контекста. Я придумал три способа:

1. Использовать двойные кавычки. Символы между парными кавычками становятся частью строкового литерала. Конечно, придется использовать два набора вложенных комментариев.
2. Использовать символ «*», в зависимости от ситуации, как оператор разыменования или оператор умножения. Опять нужно два набора комментариев.
3. Поглотить «*/», сделав эту строку содержимым символа препроцессора. Здесь нужно также вспомнить, что комментарии обрабатываются препроцессором до обработки макродиректив.

Код выглядит немного странно, но разобраться несложно:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// file: nestcomm.c?
#include <stdio.h>
void method1(){
    printf("Method 1: ");
    printf("%s\n", /*/**/"  NO\0*/"/*YES\0"/**/"*/"+2);
}
void method2(){
    int a = 1;
    printf("Method 2: ");
    printf("%s\n", /*/**/2*/*(&a)+/**/2==4?"NO":"YES");
}
void method3(){
    printf("Method 3: ");
    /*/**/#define A */
    printf("%s\n",
           #ifdef A
               "NO"
           #else
               "YES"
           #endif
            );
}
int main(){
    method1();
    method2();
    method3();
    return 0;
}

Компилятор с поддержкой вложенных комментариев уже не найдешь, но можно его сымитировать, написав на flex небольшой препроцессор:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  // file: snc.lex
%option noyywrap
%{
int comm = 0;
%}
%x STRING COMMENT
%%
<INITIAL>{
    \"         { BEGIN(STRING); ECHO; }
    "/*"       { comm++; BEGIN(COMMENT); }
    .          { ECHO; }
}
<COMMENT>{
    "/*"   { comm++; }
    .      { }
    "*/"   { comm--; if (!comm) BEGIN(INITIAL); }
}
<STRING>{
    \"     { BEGIN(INITIAL); ECHO; }
    .      { ECHO; }
}
%%
int main()
{
    yylex();
    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

.PHONY: all
all: nest_yes nest_no
	@echo "With nested comments support:"
	./nest_yes
	@echo "Without nested comments support:"
	./nest_no
 
nest_yes: nestcomm.c snc
	./snc < $< > tmp.c
	cc -o $@ tmp.c
	rm -f tmp.c
 
snc: snc.lex	
	flex -o $(subst .lex,.c,$<) $<
	cc -o $@ $(subst .lex,.c,$<)
 
nest_no: nestcomm.c
	cc -o $@ $<
 
.PHONY: clean
clean:
	rm -f snc.c snc nest_yes nest_no

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

А первые две задачи во втором дивизионе вот уже второй матч подряд совсем простые. Или дело во мне?..

В сносках были ссылки на научные статьи. Такие дела.

Я аж всплакнул от счастья.

• Ghosts of Unix Past, part 1
• Ghosts of Unix Past, part 2
• Ghosts of Unix Past, part 3
• Ghosts of Unix Past, part 4

Вкратце о содержимом. В ранние годы Unix были приняты некоторые архитектурные решения, которые определили то, что сейчас принято называть «Unix Way». Над этими решениями думали не самые глупые люди, но предусмотреть, что будет через 40 лет, никто не в силах. Поэтому в свете современных требований некоторые ключевые решения и паттерны до сих пор остались красивыми и согласованными, а некоторые породили проблемы разной величины. В статьях как раз про второй тип: какие выявились проблемы, как их можно решать и как они решаются сейчас.

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

Как часто бывает на LWN, комменты не менее ценны, чем сами статьи.

1. Входные данные — последовательность строк; каждая строка начинается с прописной буквы, остальные буквы строчные.
2. Входную последовательность всегда можно переупорядочить в допустимую последовательность, в которой у каждой пары смежных строк первая буква второй строки, переведенная в нижний регистр, совпадает с последней допустимой буквой первой строки. Допустимая буква — это буква, с которой начинается хотя бы одно слово последовательности.
3. Требуется написать кратчайшую программу, находящую любую допустимую перестановку входной последовательности.

Как это часто бывает, есть два очевидных способа решения этой задачи: один быстрый, другой простой.

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

Быстрый алгоритм хорош тем, что он быстрый. И плох тем, что трудно его реализовать компактно. Такое случается с быстрыми алгоритмами, ничего не поделаешь… Из-за этого многие им предпочитают медленные и простые, но ради справедливости код все равно пишут длинный и сложный.  И комментарии к нему не пишут. А потом увольняются, а новый разработчик все переписывает заново. Используя тот же алгоритм. Да… О чем я говорил?

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

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

От алгоритма перебора всех перестановок требуется только одно: как можно более короткая реализация. Концептуально наиболее просто способ — перемешивать последовательность случайным образом, как карты в колоде. При идеальном генераторе случайных чисел случайный перебор потребует столько же времени, сколько и «честный». К сожалению, в стандартной библиотеке C нет функций вроде shuffle, поэтому напишем честный перебор руками. Я взял кнутовское «Искусство программирования», том 4, выпуск 2, главу 7.2.1.2 и нашел там на странице 71 (в русскоязычном издании) алгоритм генерации перестановок с помощью циклических сдвигов. Автор уверял, что алгоритм отличается чертовски простой реализацией. Итак, имея исходную последовательность $x_1\ldots x_n$:

1. Установить $a_i = x_i$, $1 \leq i \leq n$.
2. Посетить перестановку $a_1 \ldots a_n$ и установить $k = n$.
3. Заменить $a_1a_2\ldots a_k$ на $a_2\ldots a_ka_1$ (циклический сдвиг). Если $a_k \neq x_k$, перейти к п. 2.
4. Уменьшить $k$ на 1. Если $k > 1$, вернуться к п. 3 (мы будем возвращаться на п.3 без выполнения этой проверки, т.к. знаем, что одна из перестановок нам точно подойдет).

Проверка перестановки на допустимость выполняется элементарно. Построим множество первых букв всех слов. Для каждой пары соседних слов в перестановке:

1. Отбрасываем с конца первого слова буквы до тех пор, пока последняя буква не будет присутствовать в множестве первых букв. Такая буква всегда существует: в худшем случае это будет первая буква слова.
2. Сравниваем последнюю оставшуюся букву первого слова с первой буквой второго слова.

Поскольку первые буквы — прописные, их надо преобразовать в строчные. Проще всего это делается для букв в кодировке ASCII или CP1251: нужно просто прибавить к коду буквы 32.

Итак, первый вариант программы:

#include <stdio.h>
#include <string.h>
 
int main(int argc, char** argv){
    int k, i, match, first[256];
    char *r, *permut[256];
    int maxidx;
 
    // обнуляем множество первых букв
    for (i = 0; i < 256; i++)
        first[i] = 0;
 
    // входная последовательность задана в командной строке, поэтому
    // пропускаем находящееся в начале массива argv имя программы
    argv++;
 
    // проходим по входным словам (argv завершается нулевым указателем)
    for (i = 0; argv[i]; i++) {
        permut[i] = argv[i]; // начальная перестановка равна исходной
        first[permut[i][0] + 32] = 1; // добавляем первую букву слова в множество
    }
    maxidx = i - 1; // максимальный индекс слова в последовательности
    k = maxidx;
    // когда match станет 1, допустимая последовательность найдена
    for (match = 0; !match;) {
        // циклический сдвиг элементов массива permut с 0 по k-1
        r = permut[k];
        memmove(permut + 1, permut, k*sizeof(char*));
        permut[0] = r;
        // см. алгоритм сдвига
        if (permut[k] == argv[k])
            k--;
        else
            k = maxidx;
        // проверка перестановки на допустимость
        for (i = 0, match = 1; i < maxidx - 1 && match; i++) {
            // получим указатель на последнюю букву первого слова
            r = permut[i] + strlen(permut[i]) - 1;
            // сдвигаем указатель, пока не найдем букву из множества первых букв
            while (!first[*r])
                r--;
            // проверяем совпадение
            match = (*r == *permut[i + 1] + 32);
        }
    }
 
    for (i = 0; i <= maxidx; ++i)
        printf("%s\n", permut[i]);
 
    return 0;
}

А дальше дело техники — надо сжимать программу:

1. Всем переменным — кратчайшие имена.
2. Убираем включения заголовочных файлов, оператор return (компилятор сам вставит), все упоминания типа int (это тип по умолчанию, его можно не указывать).
3. Вспоминаем, что глобальные переменные инициализируются нулями.
4. Заменим sizeof(char*) на 4 или 8, если компилируем, соответственно, на 32- или 64-разрядной системе.
5. Используем argc в качестве одной из нужных нам переменных, например, maxidx.

Получим:

k, i, b, f[256];
char *r, *q[256];
main(int l, char** x){
    x++;
    for (i = 0; x[i]; i++) {
        q[i] = x[i];
        f[*q[i] + 32] = 1;
    }
    l = i - 1;
    k = l;
    for (; !b;) {
        r = q[k];
        memmove(q + 1, q, k*4);
        q[0] = r;
        if (q[k] == x[k])
            k--;
        else
            k = l;
        for (i = 0, b = 1; i < l - 1 && b; i++) {
            r = q[i] + strlen(q[i]) - 1;
            while (!f[*r])
                r--;
            b = (*r == *q[i + 1] + 32);
        }
    }
 
    for (i = 0; i <= l; ++i)
        printf("%s\n", q[i]);
}

Ну, и остается только

1. Избавиться от strlen — указатель на последнюю букву можно найти и короче.
2. Выполнить кое-какие перестановки присваиваний и инкрементов, использовать разыменование вместо индексации.
3. Убрать пробелы и переводы строк.

Получим итоговый вариант (разбиение на строки оставлено для читабельности):

k,i,b,f[256];
char*r,*q[256];
main(int l,char**x){
    for(x++;q[k]=x[k];f[*q[k++]+32]++);
    for (l=--k;!b;){
        r=q[k];
        memmove(q+1,q,k*4);
        *q=r;
        k=q[k]==x[k]?k-1:l;
        for (i=0,b=1;i<l&&b;){
            for(r=q[i++];*r++;);
            while(!f[*--r]);
            b=*r==*q[i]+32);
        }
    }
 
    for (i = 0; i <= l; ++i)
        printf("%s\n", q[i]);
}

Вот и все. Должен только заметить, что даже если все допустимые буквы — последние, все равно время работы алгоритма будет что-то вроде $O(n\cdot n!)$, где $n$ — количество строк во входной последовательности. Время работы сильно зависит от порядка слов во входной последовательности и от порядка перебора. На моем компьютере на 14 словах алгоритм работал более 10 минут! Добавить 15-е слово я не решился. Так что с общечеловеческой точки зрения это очень плохой алгоритм.

Кстати, в предыдущем посте у меня в код закралась неиспользуемая переменная, что позволяет сократить решение еще на 2 символа.

Победило в конкурсе решение, кто бы сомневался, на Перле в 62 символа (и фиг с ним). Меня поразило решение на C, в котором вся программа состоит из 229 символов. На такое я спокойно смотреть не мог. Несколько часов работы — и получилось то же самое выразить в 225 символах! Давненько я не получал такого удовольствия от возни с кодом!

k,i,t,b,f[256];char*r,*q[256];main(int l,char**s){
for(s++;q[k]=s[k];f[*q[k++]+32]++);for(l=--k;!b;){r=q[k];memmove(q+1,q,k*8);*q=r;k=q[k]==s[k]?k-1:l;
for(i=0,b=1;i<l&&b;){for(r=q[i++];*r++;);while(!f[*--r]);b=*r==*q[i]+32;}}}

А если оставить только код, решающий задачу, то получится 174 символа:

for(s++;q[k]=s[k];f[*q[k++]+32]++);for(l=--k;!b;){
r=q[k];memmove(q+1,q,k*8);*q=r;k=q[k]==s[k]?k-1:l;for(i=0,b=1;i<l&&b;){
for(r=q[i++];*r++;);while(!f[*--r]);b=*r==*q[i]+32;}}

Переводы строк, как наверное многие догадались, перед подсчетом надо убрать.

Имена городов передаются в командной строке через пробел. Первая буква каждого имени должна быть прописная. Кодировка cp1251 (если русскими буквами) или ASCII. Компилировать gcc на 64-битной системе. Например:

$ ./cities Kaliningrad Vologda Dalmatovo Dmitrov Arkhangelsk Vladivistok Krakov
Dalmatovo
Vladivostok
Kaliningrad
Dmitrov
Vologda
Arkhangelsk
Krakov

Чтобы программа выводила результат, нужно вставить в main код вывода:

for (i = 0; i <= l; ++i)
        printf("%s\n", q[i]);

Если интересно, как это работает, напишу отдельным постом.

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 для отображения формул. Если не работает, пишите в комменты вместе с версией браузера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавлено

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