Переславль 2017
evatutin
(введение) Были в командировке на конференции. Кто не знает, обычно рабочий день на подобных мероприятиях заканчивается глубоко за полночь, обычно у нас в номере, обычно за рюмкой чаю и обсуждением чего-либо интересного. На следующий день как правило подъем в 7 утра, быстрый завтрак и снова на доклады. После недели в таком графике утром вставать довольно сложно (кто считает, что на конференциях мы отдыхаем? :), в состоянии близком к зомби.
(постановка задачи) В одно из таких утр я поднялся, в полусонном состоянии умылся, оделся до верхней одежды и сижу на кровати, жду пока соберется напарник, копаюсь в телефоне. Напарник в таком же состоянии неспешно ходит по номеру, собирает вещи. Сижу жду, читаю новости, про себя думаю: ну прям как моя жена с ребенком... Коллега неспешно собирается, вещи шевелит, и что-то про носки бормочет, потерял. Но мы же никуда не выходили (с), здесь где-то приказ (т.е. носки), найдутся. Дочитал новости, напарник по прежнему неспешно занимается поисками. Положил телефон в карман, наблюдаю, интересно же, куда носки пропали (мож стащил кто из вчерашних гостей?). Проходит еще минут 5, вдвоем понимаем, что времени уже впритык, а носков нет, начинаю ему помогать, одна пара глаз — хорошо, а две — лучше. Обсмотрели все его половину номера около кровати — нет носков и все тут. Все бы ничего, но научная конференция, на босу ногу в шлепанцах не пойдешь, да и на улице зима. Напарник продолжает искать, я перевожу взгляд в район двери, где стоит обувь, и вижу... свои носки, стоящие в ботинках, при этом сам я сижу в полной боевой амуниции, в том числе в носках! Немая сцена, я сообразил, кто виноват в пропаже, напарник еще нет... Что делать? Еще можно убежать, без носков он меня вряд ли догонит. А в Москву обратно на одной машине ехать, не прокатит... Придется сдаваться...
(выводы) Получилось так, что мой коллега поставил свои носки на стул, стоявший на нейтральной территории между кроватями, а я без задней мысли на автопилоте этим воспользовался. Дальше долго смеялись, от чего окончательно проснулись и пошли работать. Теперь будем вспоминать не только шею, но еще и носки :). За тем и проводятся конференции: чтобы было, что обсудить, и что потом вспомнить :).

***

В продолжение прошлой байки: в нашей компании был один участник, который каждый вечер встречал с нами, и не на сухую, но каждое утро просыпался на полчаса раньше нас, бодро шел на завтрак и по дороге стучал к нам в номер, напоминая, что секция стартует в 10 часов и надо поторапливаться. В один из вечеров я ему в шутку сказал, что на работе у меня есть коллега, которая "несет плохую весть" (программы рабочие надо переделать срочно, ФОСы составить и пр.), и он примерно так же. Он шутку юмора уловил, но виду не подал. На следующее утро традиционный стук в дверь. Поскольку моя кровать к двери ближе, открывать пошел я. Только вылез из-под одеяла, накраситься не успел, напарник вообще спит еще, открываю в полной уверенности, что знаю, кто пришел и зачем, а не тут то было: стоит на пороге номера девушка-студентка, которую наш ранний коллега с собой на конференцию привез, и мило приглашает нас на завтрак словами своего руководителя, а сам руководитель где-то вдалеке ржет. Что мне оставалось делать, надо идти в атаку, не краснеть же: пригласил девушку к нам в номер (мы еще даже свет не включили :), думал застану ее врасплох, ан нет. У нее бровь не дрогнула, еще раз повторила приглашение, пожелала нам доброго утра и пошла завтракать, а через полчаса и мы подтянулись. Вот это дрессировка в северной научной школе, смелые у них девушки: одна, впотьмах, в номер к малознакомым и малоодетым мужикам! А дверь теперь буду открывать только при полном параде :)

Процессоры "Горе"
evatutin
А вы слышали про новые процессоры "Горе"? Эльбрус был, Байкал был, шхуна Беда была, теперь вот процессоры Горе! На самом деле не Горе, а Gore, и не Gore, а Core, но не суть, раз в бухгалтерии они на балансе стоят как Gore, то ничего против не попишешь, теперь так и придется писать в рабочих программах: читаемый лектором курс должен быть обеспечен только компьютерами на базе процессора Горе! Готовимся к аккредитации, все формальные моменты должны быть соблюдены...

http://evatutin.narod.ru/humor.html
Tags:

Чем отличаются компетенции от компетентностей или болванский процесс по-русски
evatutin
Нам было рекомендовано ознакомиться с тем, иде же суть (в общем то известно где...) в компетентностном подходе, и студентам объяснить, что мы все без этого жить не можем, если аккредитующий нас эксперт спросит, да еще и аргументировать. В попытке разобраться предлагаю краткие выжимки из рекомендованной к ознакомлению статьи http://www.miep.edu.ru/uploaded/zvezdova_oreshkin.pdf (не единственная, не первая, не последняя, просто одна из, остальные примерно в том же ключе, ох уж эти педагоги, как мы без их науки учили раньше, даже и не знаю...). Трактовать будем с очень простой позиции: хочу научить студента программировать, несколько упрощая направление, по которому мы готовим студентов на кафедре. Теперь давайте посмотрим, что велит нам компетентностный подход... Для тех, кто далек от образования, поясню, что по рассмотренным в статье тезисам мы должны в своем ворохе бумажек (рабочие программы и т.п.) сделать отражение, и попробуй не сделать — обвинят в ереси и отправят на костер :). А потом еще убедить себя и окружающих, что сделанное отражение очень полезно! Итак, приступим...

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


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

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


Резюмируя: квалификация не важна, важная компетентность, умение решения принимать (руками водить, потребителей же готовим, не инженеров).

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


На фифа нам ваша квалификация, умение программы писать, объектно-ориентированное программирование знаеть, главное — динамизм и конструктивность!

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


Пилов формулы 1 готовим или пилотов истребителей, не иначе (это про перегрузки, если кто не понял). Не циклы надо знать как работают, а к перегрузкам быть готовым!

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


Не конструкции языков надо знать, а активность стимулировать! В нужном месте...

> ключевые компетентности характеризуются тем, что они позволяют решать сложные задачи (неалгоритмические)


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

> [ключевые компетентности] полифункциональны (позволяют решать разные задачи из одного поля)


"Поли-" — не от много, а от "поле" видимо. О каком поле идет речь? С подсолнухами? Или о векторном поле?

> [ключевые компетентности] требуют сложной ментальной организованности (включения интеллектуальных, эмоциональных качеств)


Есть ментальная организованность — программист, нет — двоешник!

> Учебные компетенции: Принимать на себя ответственность за получаемое образование.


Т.е. я должен учить не конструкции языков программирования, а ответственности! И не за использование конструкций, а за получаемое образование! Блеск!

> Исследовательские компетенции: Использование документов и их систематизация в самостоятельно организованной деятельности


В какой какой деятельности? Кем организованной? И зачем? Я подозревал, что у студента деятельность в вузе одна — учиться, ан нет...

> Социально - личностные компетенции: Видеть связи между настоящими и прошлыми событиями.


Ну событие (event) в программировании имеет вполне конкретный смысл. Между event'ами студент должен связи видеть? Сперва мышку пошевелили — событие OnMouseMove(), потом клавиатуру — OnKeyboardMove() :). Или я опять ничего не понял в компетентностном подходе?

> Оценивать социальные устои, связанные со здоровьем, потреблением и окружающей средой


Что за устои такие, связанные со здоровьем? Программирование тут причем? :) Из ведра, через край, а потом лекцию читать о культуре сексуальных отношений в сельской местности? (с)

> Социально - личностные компетенции: Справляться с неопределенностью и сложностью


Кто виноват и что делать? На вторую часть классического вопроса в нашей среде последнее время отвечают так: что делать, что делать, рабочие программы делай, учебно-методические комплексы делай, фонды оценочных средств делай!

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


Я памятник себе воздвиг нерукотворный: 15 строк в общественной уборной! (c) Так что ли? Только на языке программирования! :)

> Организаторская деятельность: Овладевать инструментарием моделирования


Каким таким инструментарием? А моделировать чего будем? Я знаю мат. апарат Q-схем, сетей Петри, цепей Маркова, но боюсь я узко мыслю, не креативно, по старому, а надо по новому, инновационно!

> Организаторская деятельность: Быть включенным в группу или сообщество и сделать вклад в него.


Твитология? Инстаграмия? Надо добавить соответствующую учебну дисциплину!

> Личностно-адаптивные компетенции: Быть упорным и стойким перед трудностями.


Так и вижу образовательный процесс: студенты приходят на лабу и начинают делать задание по массивам, а я им трудности как начну при этом создавать! А пусть попробуют не быть стойкими и упорными при этом! А если окажется не стойким? Как тут насчет доведения до самоубийства и пр.?

> опыт освоения учеником научной картины мира, расширяющейся до культурологического и всечеловеческого понимания мира


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

> По отношению к изучаемым объектам ученик овладевает креативными навыками продуктивной деятельности: добыванием знаний непосредственно из реальности, ..., эвристическими методами решения проблем.


Раз на этом делается акцент, значит существует и другие способы "добывания знаний": из нереальности, опосредованно из реальности, ...
Зато как я в тренд попал с моими эвристическими методами! Будет что в комбинаторике в рабочей программе указать! Правда боюсь тут не о муравьиных и генетических алгоритмах...

> Информационные компетенции: при помощи реальных объектов (телевизор, магнитофон, телефон, факс, компьютер, принтер, модем, копир) и информационных технологий (аудио- и видеозапись, электронная почта, СМИ, Интернет), формируются умения самостоятельно искать, анализировать и отбирать необходимую информацию, организовывать, преобразовывать, сохранять и передавать ее.


Раз делается акцент, значит скорее всего есть и нереальные объекты :). В чем суть посыла вообще понять сложно...

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


Что такое взаимодействие с удаленными событиями мне непонятно. Конечно можно вспомнить COM и RPC (не путать с РПЦ!), но тут кажется не об этом. Какими ролями должен владеть программист, мне непонятно, роли же у домен контроллера настраиваются, не? :) Отсюда и требования к нам организовывать на занятиях ролевые игры (с переодеваниями?) в количестве не менее 20% от общего объема времени

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


Половую грамотность тоже я развивать должен? На практиках по программированию? ОК, надо будет отобрать несколько симпатишных студенток и заняться этим вопросом :). А что такое "внутренняя экологическая культура"? :) Чем она от внешней отличается? :) Бактерии в толстом кишечнике? Так это флора и фауна внутри студента, при чем тут экология? :)

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


В общем такое подозрение, что нас аккуратно подводят в тезису о том, что мы неадекватны... Представления о нетрадиционной педагогической деятельности — это интересно! Тут гейропой пахнет :)

Вот такие инноваторы правят бал в современной системе образования! А мы пока молчим в тряпочку, скрипим зубами и в 50-й раз переделываем свои любимые бумажки, без которых наша образовательная работа — фикция по мнению минобра и иже с ними

Коротко о науке (08.2017)
evatutin

Давно у меня не было Internal Error'ов в Delphi :)
evatutin
uses
  Math;

type
  T = array of Double;

function AAA(const A: T; B: Integer): T;
var
  I, J, K: Integer;
begin
  for I := 1 to Byte(Odd(B)) do
    J := Min(I, 0);

  for I := 1 to High(A) do begin
    J := Max(I, 0);
    K := Min(I, 1);
  end;
end;

begin

end.


Компилятор Delphi 7 говорит, что "Internal Error: C1448" :)

Павлиний глаз в ноябре
evatutin
Tags:

Повышение квалификации
evatutin
Придя домой после трудового дня (4 пары, из них 2 лекции, 2 посещения административного корпуса на другом конце города соответственно до и после преподавания) я навел себе большую кружку кофе и задумался над тем, какие рабочие вопросы я буду решать сегодня в нерабочее вечернее время. Конечно же: необходимо сделать что-то максимально полезное, т.е. повысить собственную квалификацию в дистанционной форме! Чтобы облегчить подобную процедуру для других сотрудников университета, еще не сделавших этого и, соответственно, пока являющихся низко квалифицированной рабочей силой, ниже привожу мой вариант вопросов теста (с ответами, только никому не говорите!), незначительно отличающихся от официальных. Доскональное знание ответов (брейндамп) позволит вам с легкостью переквалифицироваться в категорию высококвалифицированных сотрудников и не получить нагоняй от заведующего кафедрой, дерзайте!

1. Основной обязанностью преподавателя вуза является:
* переделка УМК с периодичностью не реже несколько раз в год;
* (э)фиктивное повышение квалификации (как правильно писать, решайте сами);
* перевод рабочих программ на языки стран, студенты которых обучаются в университете;
* агитация и пропаганда ценностей высшей школы в младших классах школ;
* все перечисленное выше.

2. Балльно-рейтинговая система предназначена для:
* выставления баллов пропорционально объему сданной крови;
* формирования рейтинга студентов по уровню неуспеваемости;
* оценки спортивно-артистических способностей студентов.

3. За инновационное развитие университета отвечает:
* отдел инноваций;
* управление инноваций;
* центр инноваций;
* проректор по инновациям;
* кафедра инноваций;
* факультет инноваций;
* сотрудники университета.

4. Последние 2 цифры мобильного начальника управления научно-технологического форсайта…
* 00
* 12
* 66
* 0xFF

5. Отдел дистанционно-инновационного образования находится:
* в «колодце» за пластиковой перегородкой;
* слева от главного входа главного корпуса, где раньше была «хохлома»;
* на секретном –2 (минус втором) этаже главного корпуса между ядерным реактором и системой охлаждения фундамента;
* на чердаке нижнего корпуса на «челюстях», третья проходная аудитория по правой лестнице, ключи спросить у Валерия Ивановича.

6. Приложение Microsoft Office предназначено:
* для загрузки бумажной работой преподавателей;
* для сдачи отчетности в электронном виде в установленные подразделения в установленные сроки согласно установленной форме;
* для переделки УМК;
* для изучения информатики с использованием кейс-средств и в игровой форме.

7. Редактирование параметров абзаца в Office осуществляется:
* в меню Абзац;
* в меню Форзац;
* в меню Эрзац;
* учебно-вспомогательным персоналом кафедры;
* студентами в рамках закрытия «хвостов» с прошлой сессии.

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

9. Фамилия начальника подразделения, отвечающего за размещение выпускных работ на сайте университета, оканчивается на:
* Ъ
* Ё
* Я
* W

10. ООП – это
* объектно-ориентированное программирование;
* обще-образовательная педагогика;
* обще-объектный подход к формированию компетенций;
* нет правильного ответа;
* все ответы правильные по своему.

11. В случае поломки окон в аудитории следует обращаться:
* напрямую к ректору;
* в отдел госзакупок;
* в библиотеку, отдел комплектования;
* в центр по развитию имущественного комплекса;
* обращаться бесполезно, смиритесь.

12. Сбор тестов для студентов осуществляется следующим подразделением:
* центром научно-технического обеспечения;
* центром материально-методического контроля;
* центром дистанционно-космического зондирования знаний;
* нет таких центров в университете!

13. Обязанности сотрудников центра телекоммуникаций отличаются от обязанностей центра интернет-технологий:
* по методологическим аспектам;
* по принципу делегирования полномочий;
* не отличаются;
* по структуре положений о соответствующих центрах.

14. Прорыв трубы с водой в кабинете начальника учебно-вспомогательного управления обернется неприятностью для расположенного под ним:
* отдела трансфера форсайта и концептов в рамках инновационных конвентов;
* отдела инновационных управленческих решений;
* помещения морковеведов;
* не обернется, т.к. кабинет в подвальном помещении.

15. Третья с конца обязанность куратора в предпоследней версии трактовки от августа 2016 года, находящейся в данное время в стадии очередного переутверждения, звучит как:
* беспрекословно принимать участие в общественно-бесполезных мероприятиях;
* знать третью с конца функциональную обязанность куратора наизусть перед кадровой комиссией;
* курировать курируемую группу;
* оформлять ежедневные отчеты об итогах учебно-воспитательной работы в общежитии в свободное от учебной и вспомогательной работы время с отставшими студентами иностранцами.

16. Размещение информации на сайте университета осуществляется в … формате:
* произвольном;
* бумажном;
* exe;
* A4;
* электронном;
* дистанционном.

17. При проверке документа на плагиат в соответствующей системе справа от него появляется символ:
* поднятого вверх безымянного пальца;
* иконки с изображением одного из дорожных знаков;
* китайского иероглифа Бздынь;
* нет правильного ответа, символ зависит от числа заимствований и точки зрения проверяющего.

18. Приложение Microsoft Word отличается от Microsoft Excel:
* названием;
* возможностью редактировать таблицы;
* возможностью создавать документы;
* цветом иконки.

19. Название системы для работы с УМК в электронном виде на сайте университета:
* схоже с нехорошим словом в русском языке;
* транслитерируется на русский язык без перевода;
* является направлением, куда посылают преподавателей ответственные за УМК на кафедрах.

20. Положения с каким номером нет (еще нет?) в университете:
* ПУ-123546874.12444894764;
* ПУ-541654846.12354864456;
* МУ-84644248;
* УМУ-12354875;
* все перечисленные номера положений активно используются в образовательном процессе.

21. Компетенции – это
* бич современного инновационного образования;
* элемент, предназначенный для создания затруднений при составлении учебного плана;
* неизвестное русскому уху слово, взятое из западной системы образования в результате перехода на Болванскую систему;
* элемент, развивающий фантазию преподавателя при составлении рабочей программы.

22. Туалет на административном этаже административного корпуса является:
* мужским;
* женским;
* ни тем и ни другим, имеет специальное назначение.

23. Птичьей фамилией (не путать с медицинской!) обладает(ют):
* пара известных футбольных комментаторов;
* начальник одного из центров, расположенных на втором этаже главного корпуса;
* ведущий дворник экономического корпуса;
* победитель инновационного конвента по перспективным исследованиям.

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

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

Иерархия классов изомормизма для диагональных латинских квадратов
evatutin
Перед прочтением рекомендую ознакомиться:
1. http://forum.boinc.ru/default.aspx?g=posts&m=87519#post87519
2. http://forum.boinc.ru/default.aspx?g=posts&m=87532#post87532

Итак, несколько моих мыслей в продолжении постов whitefox'а про СНДЛК. Давно хотел проверить выкладки без применения перестановок, вот наконец-то руки дошли.
Первое, что мне было интересно проверить — сколько заполнений двух диагоналей существует для ДЛК порядка 10. При фиксированной первой строке ДЛК (брал для нормализованного ДЛК в виде 0 1 2 ... 9, но это тут не важно) у меня получилось, что существует 2 723 433 984 разных заполнения – на мой взгляд очень много и скорее всего многие из них изоморфны друг другу... Чтобы в этом убедиться, заполнение первой строки я убрал, зафиксировал первую диагональ в виде 0 1 2 ... 9 (нормализация по главной диагонали, оно же СНДЛК) и стал строить возможные заполнения второй – их получилось 440 192 (в точном согласии с результатом whitefox'а про двусторонние беспорядки). Далее к полученным 440 192 заполнениям диагоналей (далее X-образным заполнениям) применил процедуру канонизации (M1- и M2-перестановки, транспонирование, симметричное отражение), код которой пришлось немного адаптировать под частично заполненный ДЛК, – в итоге у меня получилось 67 различных заполнений, не приводимых друг у другу, – в точном соответствии с результатом whitefox'а, но другим, более понятным на мой взгляд способом (хотя это видимо кому как :).
X-образное заполнение диагоналей интересно тем, что при выполнении преобразований канонизации элементы диагоналей не могут с них «спрыгнуть» (точнее, даже не могут перепрыгнуть с диагонали на диагональ, но это сейчас не важно). Все остальные не диагональные элементы квадрата могут «прыгать» на любое место. О том, почему это плохо, ниже...
Аналогичные множества я построил для всех размерностей ДЛК от 4 до 10, пример для N=9 привожу ниже, их всего 20.

103246587 - 12 times
103246785 - 192 times
103247856 - 96 times
103247865 - 192 times
103642587 - 24 times
103642785 - 384 times
103647825 - 768 times
103647852 - 384 times
103746825 - 192 times
103746852 - 192 times
103748526 - 384 times
103748562 - 384 times
120647835 - 384 times
123048567 - 48 times
123640857 - 384 times
123647805 - 384 times
123648507 - 192 times
123840567 - 48 times
127648503 - 96 times
183642507 - 12 times

Первые 9 цифр – это заполнение побочной диагонали от верхнего правого угла к нижнему левому. Вторая цифра – это кратность X-образного заполнения, т.е. число X-образных заполнений из исходных, которые после канонизации приводятся к данной диагонали (например, к диагонали 1032674598 ДЛК порядка 10 приводятся 320 исходных X-образных заполнений). С использованием понятия кратности можно сравнительно легко пересчитать общее число ДЛК заданного порядка как Сумма[a(X)*t(X)] по всем не приводимым друг к другу X-образным заполнениям, где a(X) – число ДЛК, соответствующих начальному заполнению X, t(X) – кратность начального заполнения. Плюс от подобного подсчета очевиден: это существенное сокращение затрат вычислительного времени. Например, при подсчете числа ДЛК порядка 9 «в лоб», мы будем считать число заполнений для всех 192 видов побочной диагонали (число будет одинаковое), приводимой к диагонали 103246587, а можно посчитать число заполнений a(103246587) однократно, а затем умножить его на t(103246587)=192 – экономия вычислительного времени налицо. Для подтверждения работоспособности данного способа подсчета для N=8 был организован вычислительный эксперимент: подсчет по старому (со всеми фишками оптимизации) занял 8,6 часа при реализации в 1 поток на загруженном заданиями Gerasim'а Core i7 4770, в то время как подсчет по новому потребовал всего 6,7 минуты в тех же условиях, выигрыш составил 77 раз! Число ДЛК 7447587840 разумеется совпало! С ростом N выигрыш скорее всего также будет расти, запустил аналогичный подсчет для N=9 (напомню, на гриде мы это число считали около 3 месяцев при задействовании 500 машин кранчеров), но для одной машины он все равно видимо тяжеловат – за ночь найдено почти 6 млрд. дозаполнений только для одной X-образной начальной конфигурации и перебор продолжается.
Подводя итог под написанным выше: исходной множество X-образных заполнений удалось разбить на сравнительно небольшое число классов изоморфизма, что само по себе неплохо, но дальше – больше... :) А нельзя ли эти классы разбить на подклассы? Т.е. выстроить эдакую иерархию классов изоформизма – почти объектно-ориентированное программирование :). Чтобы понять идею, предлагаю попробовать построить дозаполнения, например, для начальных заполнений



и убедиться, что оно совпадает и равно 213 920. А раз так, значит скорее всего они изоморфны... Как в этом убедиться?
Первая идея, которая приходит на ум, заключается в попытке построения канонических форм для каждого из частичных заполнений. Для этого предположим, что в незаполненных ячейках ДЛК стоит заведомо большое число (бесконечность) и любая заполненная ячейка меньше незаполненной. Тогда соответствующие частичные канонические формы для приведенных выше примеров будут выглядеть так:



Т.е. они действительно совпадают и их можно не считать 2 раза! Минус заключается в том, что после построения такой КФ мы «сбили» исходное X-образное заполнение и теперь побочная диагональ не входит в число канонических. Этого можно избежать, если изменить условие сравнения квадратов на больше/меньше! Напомню, как производится канонизация: мы выполняем группу преобразований, дальше нормализуем их результат и смотрим, не получился ли квадрат лексикографически меньше исходного, если получился, то запоминаем. В результате выполнения всех преобразований находим самый лексикографически маленький квадрат, который и есть КФ. Лексикографическое сравнение квадратов подразумевает их выписывание в строку с последующим сравнением строк на больше/меньше. Выписать квадрат порядка N в строку можно (N^2)! различными способами, обычно берется построчное выписывание

a11 a12 ...a1N a21 a22 ... a2N ... aN1 aN2 ... aNN.

Чтобы диагонали не менялись, порядок выписывания придется изменить на следующий: сперва выписываются элементы диагоналей, а затем все остальные элементы построчно:

a11 a1N a22 a2(N-1) a33 a3(N-2) ... aNN aN1 | a12 a13 ... a1(N-1) a21 a23 ... a2N ... aN2 aN3 ... aN(N-1).

Для данного порядка диагонали сравниваются первыми и при построении КФ на этой базе они всегда остаются каноническими.



Теперь о том, как строить подклассы. Берется исходное X-образное заполнение, делается 3 вложенных цикла: два по координатам незаполненных ячеек и один по возможным значениям, если в ячейку a[I][J] можно поставить значение V, то так и делается, полученное начальное заполнение запоминается (для двух диагоналей ДЛК порядка 8 таких начальных заполнений получается где-то 450–500 – это фактически одна итерация поиска в ширину на дереве комбинаторного перебора). Далее для каждого начального заполнения строится частичная КФ, смотрится, сколько получилось уникальных и какая у них кратность – все в общем-то напоминает исходное разбиения на диагональные X-образные разбиения. Для выбранного в качестве примера X-образного заполнения существует всего 3 подкласса из 500 исходных заполнений:



Их кратности составляют 64, 16 и 128 соответственно. Дальше эти классы можно снова разбить на подклассы, что и будет формировать иерархию классов изоморфизма. На каком уровне при этом стоит остановиться? Ответ достаточно прост: когда на каком-либо ярусе разбиения пойдут все различные классы с кратностью 1. Примеры соответствующих частичных заполнений приведены ниже, у них 500 подклассов с кратностью 1 и 185 подклассов с кратностью 1 соответственно.



Использую подобное разделение на подклассы, как и с исходными X-образными классами, можно снизить время подсчета числа ДЛК соответствующего порядка с использованием аналогичной приведенной выше формулы с суммой. Для N=8 было организовано разбиение на один ярус вниз по отношению к 20 корневым X-образным диагональным заполнениям и соответствующий эксперимент по подсчету числа ДЛК, число получилось равным 41 072 640, т.е. не правильным :(. На самом деле данное значение завышено ровно в 48 раз по отношению к искомому, для N=7 завышение получается ровно в 36 раз, что очень подозрительно: идея вроде бы верная, но что-то здесь не так...
При подробном анализе выяснилась интересная деталь: число дозаполнений считается правильно, а вот кратности определяются неправильно. Причиной этому является то, что некоторые начальные заполнения (как с различной частичной КФ, так и с совпадающей) после дозаполнения приводят к одним и тем же семействам полностью заполненных ДЛК на выходе (т.е. другими словами некоторые ДЛК учитываются в разных подклассах повторно). Пример данной ситуации очень просто можно проиллюстрировать на следующем начальном заполнении:



На каждую из 8 незаполненных клеток можно поставить единственно возможный элемент, значение которого показано зеленой цифрой на белом фоне, т.е. вроде бы имеем 8 возможных дозаполнений с одинаковой частичной КФ (отличается от приведенной на рисунке значением a12=2), т.е. вроде бы есть 1 класс с кратностью 8. На самом деле X-образное начальное заполнение дозаполняется до полного ДЛК единственным образом, а не 8 различными (эти 8 – это части этого единственного результирующего дозаполнения).
Как учесть данную ситуацию я пока не придумал, если будут идеи, с радостью готов обсудить. Если данное разбиение на подклассы получится реализовать, то это теоретически должно сократить затраты времени на пересчет объектов еще где-то на порядок, чем оно и интересно...

Крошка и кондиционер
evatutin
К нам на работу пришли ставить кондиционер. Ребята просверлили дырку в стене, сложили инструмент на открытом окне и ушли на улицу к вышке. Я их караулить не могу постоянно, дай думаю телефон свой оставлю, вдруг что надо будет, подойду. А как? Я на четвертом, она на земле крутятся. Взял бумажку, написал свой мобильник, а как вниз сбросить? Надо завернуть во что-то тяжелое! Нашел в лаборатории старый советский конденсатор размером с кулак, завернул в бумажку, высунулся в окно, крикнул, что сейчас телефон сброшу и бросил. Парень внизу видимо не понял, зачем я ему свой телефон бросать собрался (видит же, что у меня в руке что-то увесистое). Подошел, поднял мой сверток из травы, развернул, бумажку выбросил и стоит смотрит, понять не может, что за телефон такой диковинный я ему бросил? Мы наверху с коллегами со смеху умираем, а он внизу стоит и не поймет, в чем прикол. Когда смех отпустил, я ему объяснил, что конденсатор можно выбросить, а вот выброшенную ранее бумажку поднять и как раз на ней и записан номер моего телефона. Дальше уже смеялись вместе, дошло :).

***


Крошка. Есть известная байка о том, что настоящий админ должен жить пивом, которое ему принесут, и крошками, вытрясенными из клавиатуры. На одной из лаб собирался показать студентам пример, взял свой нетбук, стал набирать – несколько кнопок не нажимается, как раз крошка под низ видимо попала под кнопки и мешает. Обычно крошки бывают небольшие, стоит нажать посильнее и она раскрошится, дальше можно работать. А тут нет, не нажимается и все. Значит надо ее вытрясти! Я взял нетбук и начал делать следующее: потрясу, поставлю, попробую, потрясу еще раз посильнее и по кругу. Студенты вокруг сидят, задания свои делают, на меня косятся, понять не могут, что я делаю. Видят, что у меня вижуалка запущена и часть программы написана, а что я делаю, не поймут. Наверное отлаживаю, что же еще… Потом один таки осмелился спросить, я ему объяснил, смеялись всей группой.

http://evatutin.narod.ru/humor.html
Tags:

Карфаген 2017
evatutin


































































Tags:

?

Log in

No account? Create an account