Category: история

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

Как я в парадоксовые игры играл, часть 2/2

В Crusader Kings 2 я, каюсь, не доиграл. В отличие от симулятора европейского монарха, CK2 это симулятор интриг и династического вырождения. Вотчина протагониста-феодала ограничена 2-3 маленькими провинциями (в моем случае Павия и сопредельные, в Северной Италии), в нескольких дворах которых происходят многочисленные браки, имеющие последствиями споры хозяйствующих субъектов, в которых можно принимать чью-либо сторону. К вопросу дейтинга я подошел весьма ответственно и написал на PHP парсер сейва. Он позволял среди 60 тысяч неписей обнаружить умную и красивую невесту на выданье в какой-нибудь среднеевропейской глуши, блестящего саванта-преподавателя или управляющего, крутого военачальника или просто 53-го в очереди наследования персонажа, которого можно было бы пропихнуть в графья, поубивав 52 предыдущих (ну или дождавшись, пока они сами справятся).

Collapse )

Как я в парадоксовые игры играл, часть 1/2

Я сыграл в Europa Universalis 3 одну игру. Это заняло почти 100 часов одной безвылазной неделей в 2013. Все это время я был великим британским монархом и три столетия, с 1492 до 1793 года, шел к успеху. Этот текст написан по мотивам моих повествований в аське.

EU это отличный историко-политический тренажер: если действовать по истории, то и остальные события будут идти по истории. Если же нет, мир будет реагировать осмысленным образом, напоминая незабвенный цикл Пола Андерсона про Патруль Времени.

Мое расхождение с историей началось, видимо, с того, что я ухитрился купить заполучить титул императора Священной Римской Империи. Разумеется, собирать разобщенные немецкие земли настоящему англичанину не пристало, поэтому Германия так и не образовалась. Вместо Бранденбурга развилась Австрия, Австрия прижала Польшу, Польша не уничтожила Литву, Литва не была вынуждена склоняться перед русскими и русским в итоге так и не дали объединиться. К концу игры три маленьких русских княжества, кажется, Рязань, Новгород и кто-то еще, оказались маленькими островками в колоссальной Литве, поглотившей Московию и доросшей на восток до самого Китая.

Collapse )

Праздник для телепатов

С какой фамилией у вас ассоциируется эта картинка? (229186B, md5:2f39a75fe32ac2b0888eef3e5ab9ed8c)



UPD: Самый распространенный метод стеганографии в картинках успел уже всем надоесть.

Решено: _winnie одолел головоломку и верно назвал фамилию Колумб. Действительно, 12 октября 1492 года экспедиция Христофора Колумба достигла острова Сан-Сальвадор в Багамском архипелаге, что впоследствии было принято за официальную дату открытия Америки, и ее годовщина называется День Колумба.

Collapse )
  • Current Music
    Геннадий Белов — [Поёт Геннадий Белов #10] Дрозды
  • Tags

Тайны графена

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

(NH4)2Cr2O7 → N2 + C (графен) + 2 O2 + 3 H2O + 2 Rh (при нагреве)

Справедливости ради стоит отметить, что НАН Украины проводила ранее подобные эксперименты по получению кремния и кобальта.

UPD: Я подумал, что, возможно, не все еще знают, каким революционным методом были получены кремний (Si) и кобальт (Co):

\lim\limits_{x \to 0}\frac{\mathrm{si \not n} \not x}{\not n \not x} = \mathrm{Si} \\\lim\limits_{x \to 0}\frac{\mathrm{co \not s} \not x}{\not s \not x} = \mathrm{Co}
  • Current Music
    Kylie minogue — [Aphrodite #08] Better Than Today
  • Tags
    ,

ВМК-50

Цитирую А. П. Ершов, М. Р. Шура-Бура. Становление программирования в СССР. Новосибирск, 1967 г.. Группировка моя.

Вот как выглядел учебный план по вычислительной математике МГУ в начале 50-х годов (списан из приложения к диплому АЕ, выпуск 1954 г.):

Математический анализ
Аналитическая геометрия
Высшая алгебра
Дифференциальная геометрия
Теория функций комплексного переменного
Вариационное исчисление
Теория вероятностей и теория ошибок
Математическая логика

Астрономия
Физика
Теоретическая механика
Уравнения математической физики

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

Номография
Черчение

Основы марксизма-ленинизма
Политическая экономия
Диалектический материализм
Исторический материализм

Иностранный язык (английский)
Физическое воспитание и спорт
История математики

Курсовая работа
Производственная практика
Специальные курсы
Специальные семинары
Дипломная работа

Государственные экзамены: Основы марксизма-ленинизма, Вычислительная математика


Лучше бы нам радиотехнику и электронику читали вместо дифуров, а физкультура должна была отмереть вместе с номографией!

SRM 454

Автор сета — Gluk. Контест, к сожалению, был почти целиком технический. Боги Топкодера, судя по всему, разгневались на меня, иначе чем объяснить тот факт, что последние 3 контеста у меня падали 250? Падение продолжается с одним перерывом аж с апреля, так что я уже примеряю зеленую форму лузера (привет, shuffle_c :)).

↓1282

Collapse )

В заключение упомяну об интересном факте: оказывается, вплоть до 1976 года было неизвестно, существуют ли непрерывно изгибающиеся многогранники без самопересечений. Оказывается, существуют :) Пока не доказано, что минимальным (9 вершин) многогранником с таким свойством является полиэдр Штеффена. Вот он на видео. Я склеил его для проверки — действительно, изгибается :) Самым интересным связанным результатом является теорема Сабитова, доказанная в 1996, из которой следует верность гипотезы «кузнечных мехов» о том, что объем любого изгибающегося многогранника постоянен. Примеры изгибающихся многогранников для пространств с размерностью 5 и выше еще не построены :)

Попутно отмечу, что мало что может сравниться по омерзительности с подключением GMP под виндой, даже если он уже собран. Дьявольские байты вызывают Access violation, не имеют .lib-файлов, нормального C++-враппера и всячески демонстрируют си головного мозга у создателей, какбе призывая образ ржавой секиры ужаса в мысли несчастных программистов.

Ну и запишу-ка я Evenfall в список открытий этого года, а Eternal Tears Of Sorrow c альбомом Children Of The Dark Waters в свой ежегодный топ музыкальных альбомов.

Форматы времени

Количество компьютерных форматов представления времени поражает всяческое воображение. Видимо ввиду древности возникновения задачи хранить момент времени, область полна архаики. Вкратце перечислю некоторые из решений (рассматриваем наиболее популярную 32-битную архитектуру):

Unix time (POSIX-время, time_t) в 4 байтах хранит время в секундах, прошедшее с 1 января 1970 года, следовательно, может представлять время до 19 января 2038 года.

Unix time 64 — то же, что и предыдущее, только 64-битное. 8 байт, от 1 января 1970 года примерно 292 миллиарда лет.

Юлианские дни (JD) используется для указания дня в астрономии (для указания конкретного момента в дне используют дробную часть). Если ограничить его представление 4 байтами, он представит даты от полудня 1 января 4713 до н. э. примерно 12 миллионов лет. Именно эта дата была выбрана ввиду начала сразу нескольких неинтересных циклов и потому, что до нас не дошли упоминания о более ранних астрономических наблюдениях.

Модифицированные юлианские дни (MJD) используются для сокращения записи юлианских дней вычитанием 2400000.5, точкой отсчета становится ночь 17 ноября 1858 года.

BIOS-time измеряет время в тиках с частотой примерно 18.2 Гц с полуночи, занимает 4 байта.

struct tm используется для представления человеко-читаемой даты в стандартной библиотеке C.

struct tm {
    int tm_sec;
    int tm_min;
    int tm_hour;
    int tm_mday;
    int tm_mon;
    int tm_year;
    int tm_wday;
    int tm_yday;
    int tm_isdst;
};

Таким образом, эта структура размером 36 байт может представить дату от 1 января 1900 (и еще 4 миллиарда лет) с точностью до 1 секунды.

Радуют разнообразием форматы времени, используемые в Windows.

GetTickCount возвращает 4-байтовое число, равное количеству миллисекунд, прошедших с момента включения компьютера, представляя интервал до 49.7 суток. GetTickCount64 это ее 64-битный аналог, который позволяет представлять интервалы до 580 миллионов лет.

FILETIME это такой виндовый unix-time, только с БШ. БШ обеспечивается за счет 64-битности, позволяя указывать дату в 100-наносекундных интервалах, начиная с 1 января 1601 года на протяжении 58 тысяч лет.

SYSTEMTIME — БШ-tm от Microsoft.

struct SYSTEMTIME {
    WORD wYear;
    WORD wMonth;
    WORD wDayOfWeek;
    WORD wDay;
    WORD wHour;
    WORD wMinute;
    WORD wSecond;
    WORD wMilliseconds;
};

Экономит на размере полей, поэтому занимает 16 байт, и представляет с секундной точностью время от 1601 года почему-то до 30827.

Кроме вышеперечисленных бинарных форматов существуют текстовые, тысячи, тысячи их. Но еще один виндовый я все же упомяну:

CIM_DATETIME — в формате yyyymmddHHMMSS.mmmmmmsUUU в 25 байтах представляющий с точностью 1 миллисекунда время от 0-го до 9999-го года.


Такое разнообразие страшно раздражает, и я задался вопросом, а нельзя ли как-нибудь решить эту проблему раз и навсегда?

Отметим, что дискретизация самого точного представления (FILETIME), равная 100 наносекунд, совершенно недостаточна для представления длительности, скажем, фемтосекундных лазерных импульсов, которыми давно и успешно исследуют механизмы химических реакций, а диапазона самого «древнего» (JD) и самого «широкого» (tm) недостаточно для датировки древних горных пород или превращения Солнца в красного гиганта.

Согласно принципу квантовой неопределенности и теории относительности, измерить время точнее планковского времени, равного примерно 5.39x10−44 секунд, принципиально невозможно. Кроме того, время существования нашей Вселенной не превышает 13.85 миллиардов лет. Радостно делим одно на другое, берем двоичный логарифм и получаем, что хватит 203 бит. Округляем до 256 бит (32 байта, tm — и тот больше) и обнаруживаем, что любое обозримое событие и любой наблюдаемый интервал вполне может быть представлен таким числом.


Даешь 32-байтные таймстампы!!!

ICFPC-2008. Жизнь после сабмита.

Часть 2/2. Начало тут.

Первый день я посвятил поискам виртуальной машины, зарывшись в IDA. Бинарник сервера был скомпилирован то ли MLton, то ли SML/NJ, поэтому все выглядело непривычным. Были найдены три основные кандидата на паранойю:

1) зашитые строки /tmp/fileh66xwi.4.S, /tmp/filepBsTWf.3.S, /tmp/fileXajp7t.2.S, /tmp/filel5vY27.1.S (похоже это были ключи для ftok);

2) В двух местах бинарника KANAL обнаружил константу 0x9E3779B9 — это самое близкое к золотой середине среди int32 число (2^{32} \frac{\sqrt{5}-1}{2}). Оно используется во многих алгоритмах шифрования и хэширования (например, в TEA), но здесь, видимо, использовалось в garbage collector.

3) Еще была найдена строка "bogus command exceeds max length". Ознакомившись с http://en.wikipedia.org/wiki/Quantum_bogodynamics, я уж было обрадовался, что есть какие-то читы, но дальнейший безрезультатный поиск привел к мысли, что слово "bogus" употреблено в основном смысле.

Кроме того, кое-кто заметил на официальном канале #icfp-contest, что в бинарнике есть строка "June 1, 1996", а по его словам "this is a day when "Mars Attacks!" movie was ended filming...". Но поиски и в эту сторону результатов не принесли.

Тем более странно это было, учитывая, что организаторы в IRC сообщили, что контест готовился как минимум с января.

Поэтому я разочаровался в задании и подкинул сокомандникам (мы гордо поименовали себя The Little Collider Team) идею о том, как делать pathfinding. Для этого следует построить итеративную триангуляцию Делоне с вершинами в центрах препятствий, затем по ребрам триангуляции построить граф проходимости (вроде как подграф сопутствующей диаграммы Вороного), а на нем тупо искать быстрейший путь. Когда телеметрия присылает данные о новых препятствиях, достраивать триангуляцию. Сокомандники добавили в эту схему мультитредность и клиент с визуализацией на GLUT.

Итог контеста: 209 ревизий (всего 12 из них мои), 422 КБ кода, почти 398 КБ логов IRC... и ни одного сабмита на сервер :) Перед самым концом контеста все заглючило, засегфолтило, а в svn начался форменный бардак. Впрочем, мы не особо много потеряли :)

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

Тест по математике: разбор, часть 1

Часть 1/2, часть 2/2 в http://sharpc.livejournal.com/26120.html

Вывод, который можно сделать из статистики: да, все таки простые люди знают математику. Правда, немного настораживает, что большая часть этих простых людей — студенты и аспиранты математических факультетов МГУ и СПбГУ.

Collapse )

Collapse )
  • Current Music
    Epica — [The Divine Conspiracy #03] Menace of Vanity
  • Tags

IPSC 2008

IPSC (International Problem Solving Contest) — ежегодный открытый чемпионат по программированию, проводимый словацким Comenius University (misof и Kº). В целом он похож на ACM ICPC: 10-15 задач (в этом году 12), система штрафов, команды до 3 человек, но есть и отличия. Есть 4 зачета: командный и личный, среди всех и среди школьников. По каждой задаче предоставляется два теста (простой — 1 балл, сложный — 2), и отправлять на сервер нужно не решение на языке программирования, а ответ к этим тестам. Большая часть задач — традиционные ACM-подобные алгоритмические задачи (в этом году 8), размер тестов к которым не позволяет решить их на бумажке, но есть и необычные, в которых надо продемонстрировать компьютерную эрудицию, разгадать зашифрованное послание и даже сыграть с сервером. (Кто-нибудь, запостите это в википедию)

Результаты IPSC 2008, в личном зачете.

Collapse )

Контест ознаменовался весьма звездным составом (на финале ACM такого не встретить, разве что Petr почему-то забил) — место/баллов/штраф:

1. R+T+J 34 2240
Дримтим планеты Земля: Бартон Рейд из Гарварда, долгое время бывший таргетом и лучшим топкодером США; Томек Чайка (Польша), не нуждающийся в представлении трехкратный лидер TCO и многолетний лидер рейтинга TopCoder; Джон Детридж, таргет, сильнейший топкодер Австралии.
2. MSU MiSHa 31 2238
МГУшный дримтим: Шавлюгин, Халявин и Миняйлов.
3. SPbSU ITMO Various 28 1465
Дримтим ИТМО: Царев (чемпион ACM ICPC этого года), Исенбаев и их тренер — таргет Андрей Станкевич.
4. Three-headed Monkey 28 1974
Шведский дримтим.
5. uwr1 28 2612
Дримтим Вроцлава.
6. EigenValues 28 2645
Иранский дримтим.
7. Pointless 27 1955
Украинский дримтим (Гриненко, Симоненко и Нейтер).
8. MountainKing 27 2044
Китайский дримтим (во главе с таргетом ACRush).
9. JAM 27 2207
Команда таргетов bmerry и PaulJefferys.
10. Moo 27 2388
Дримтим МТИ во главе с Bohua Zhan (второе место на ACM ICPC этого года).
11. Moscow SU x13 26 1904
Легендарная ACM-команда МГУ последних лет.
14. MSU Unpredictable 25 2008
Самая перспективная молодая команда МГУ.

Контест показал подавляющее преимущество команд из трех человек над командами из одного человека: лидер среди индивидуалов Дмитрий Джулгаков (Украина, КПИ) набрал 24 балла и занял 20-е место в общем зачете.

Мои результаты существенно скромнее, 15 баллов, 15-е место среди индивидуалов (из 159) и 85-е в общем зачете (из 375). Однако мне удалось на 1-2 балла опередить таких сильных красных топкодеров, как Egor, asaveljevs, Ulan, rem; набрать столько же, сколько gawry; не больше, чем на 2 балла отстать от красных ardiankp, Olexiy и от ярко-желтых bjacoke001 и DmitryKlenov. В течение почти всего контеста мне удавалось быть впереди команды dfyz Dark Magic, но в конце им все-таки удалось переломить ход битвы в свою пользу и занять 77-е место :)

Thanks to misof for wonderful contest ;)

В последнее время башорг и френдлента полнится сообщениями о победах России в футболе, хоккее и на Евровидении. Мое мнение: это жалкая компенсация за второе место Пети Митричева на финале TopCoder Open.