60 FPS? Легко! pointer-events:none!

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

.hover .element:hover {   box-shadow: 1px 1px 1px #000; }


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

Фишка тут в том, что при скроле вы просто удаляете класс .hover с тега body, тем самым отключая все ваши селекторы с :hover-ом. После окончания события, класс возвращается, и эффекты :hover опять в деле.

Круто. Но не очень – привычное переключение глобального класса запускает немалый пересчет стилей, и это не есть гуд. Гениальное решение предложил Christian Schaefer:

О да, pointer-events – наше все!

Свойство pointer-events позволяет управлять условиями, при которых элементы вашей страницы будут реагировать на события мыши. Смотрите сами:

Ошеломительная разница, не так ли? И все это без лишней сложности селекторов:

.disable-hover {   pointer-events: none; }

Просто добавляем этот класс к нашему body по началу скрола, и все – мышь «пролетает»!

var body = document.body,     timer;  window.addEventListener('scroll', function() {   clearTimeout(timer);   if(!body.classList.contains('disable-hover')) {     body.classList.add('disable-hover')   }      timer = setTimeout(function(){     body.classList.remove('disable-hover')   },500); }, false); 

Код, как видите, довольно простой. Вешаем обработчик на событие скрола, в котором сперва сбрасываем предыдущий таймер, проверяем наличие класса на нашем body, и, если его нет – добавляем. Затем просто добавляем новый таймер, который, через пол секунды после окончания скрола, сбросит наш класс. Все!

Почти

Если где-то в странице будут элементы со стилем pointer-events: auto, они перетрут глобальный класс, и будут все еще тормозить. Мы же не хотим этого, верно?

.disable-hover, .disable-hover * {   pointer-events: none !important; }

Как вы догадались, решение, так же, простое. Супер-селектором * с флагом !important мы научим наши элементы вести себя хорошо.

Можете убедиться в работе данного подхода. Попробуйте замерить производительность с hover-ом, и без. Результат впечатляет!

ссылка на оригинал статьи http://habrahabr.ru/post/204238/

Управление правами доступа к WMI через Puppet

В качестве предисловия


Основной задачей моей работы является поддержка парка железных и vm хостов — уже под 200 (а приходил было менше 100, эх, время бежит…) Поддерживаю все железо, а также сеть. Также на мне весь мониторинг (используем Opsview — сделан на ядре nagios), аггрегация логов (я внедрил Logstash, обалденное opensource решение за место ну ооочень дорогого Splunk), configuration management (puppet), бекапы, поддержка баз данных и прочих систем тоже на мне (MongoDB, MySQL, Redis, ElasticSearch, etc). В общем — все самое интересное). Стоит отметить что у нас достаточно тонкая грань между поддержкой и разработкой, и разработчики часто говорят что они хотят, а я уже занимаюсь внедрением. Хочется рассказать обо всем что происходит интересного и какие технологии удается использовать. Какие прижились, а какие по каким-то причинам нет.

В свободное от решения проблем время перевожу инфраструктуру на Infrastructure-as-a-code (IaaC), выбрал puppet для этого из-за неоднородности нашей инфраструктуры. В моей сети зоопарк из Windows Server 2008, Windows Server 2012, CentOS 5.5, CentOS 6.4. Ах, да, пару дедушек на 2003 — пора их на пенсию отправлять скоро…

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

Задача

Возникла необходимость автоматизировать конфигурацию WMI на серверах Windows 2008 / 2012. Ключевой необходимостью стало добавление сервисного пользователя (назовем его «domain\service-user») в локальные группы сервера, которые разрешают удаленное использование WMI, а также доступ к Performance Counters, Performance Logs, в общем ко всему что нужно чтобы удаленно мониторить сервер. Сами группы определились достаточно быстро, оставалось найти удобный и быстрый способ это сделать. Также необходимо было дать права пользователю domain\service-user на доступ к корневым неймспейсам WMI. Так же все это должно быть частью общей концепции IaaC, что должно означать как минимум проверку текущего состояния, и пропускать выполнение если пользователь уже добавлен куда нужно в любом варианте присутствия-отсутствия пользователя в группах. Т.е. решение должно быть максимально автоматизированным, а точнее полностью. После небольшого гугления стало ясно что для моего случая нужно, а мне предстояло:

Добавить доменного пользователя domain\service-user в локальные группы (как минимум):
— Certificate Service DCOM Access
— Performance Log Users
— Performance Monitor Users
— Distributed COM Users.
Установить права доступа, как минимум, «read» для пользователя domain\service-user на следующие неймспейсы WMI:
— CIMV2
— MicrosoftIISv2.
Как только все будет установлено, check_wmi_plus (входит в стандартную поставку Opsview Pro) сможет получить необходимые данные об IIS и других интересных параметрах (а это то нам и надо)!

Сложности

Главная сложность которая возникла — готового решения чтобы запустить и быть уверенным в том, что «Сервер будет доступен для мониторинга» нет. В общем-то я и не очень расстроился, потому что очень редко бывают готовые решения под мои задачи, а если и бывают то часто делают что-то не то или не так.

Puppet имеет встроенный ресурс «user», который, по идее, должен был выполнить половину всех задач, не заработал в связке «доменный пользователь — локальная группа». Как оказалось это известный баг и его собираются исправлять (UPD: уже исправили в релизе 3.4), но постоянно отодвигают в следующий релиз puppet. Попытка выполнить workaround в puppet DSL не увенчалась успехом из-за слишком сложной структуры, требующей сложных escape последовательностей, которые не всегда работают.

Еще одна сложность — в windows отсутствует встроенный универсальный способ управления правами доступа к wmi классам, который можно было бы «обернуть» в puppet, если только ковырять реестр и изобретать велосипед.

Реализация

В итоге я принял решение написать свой провайдер и использовать его, до тех пор пока родной провайдер для добавления доменного пользователя в локальную группу на сервере не будет починен. И сделал я это… обернув powershell код!

win_user.rb

Puppet::Type.type(:win_user).provide(:win_user) do   @doc = %q{Manage windows users and groups}   desc "Manage windows users and groups"   confine    :operatingsystem => :windows   defaultfor :operatingsystem => :windows 	  	commands :powershell => 	if File.exists?("#{ENV['SYSTEMROOT']}\\sysnative\\WindowsPowershell\\v1.0\\powershell.exe") 	  "#{ENV['SYSTEMROOT']}\\sysnative\\WindowsPowershell\\v1.0\\powershell.exe" 	elsif File.exists?("#{ENV['SYSTEMROOT']}\\system32\\WindowsPowershell\\v1.0\\powershell.exe") 	  "#{ENV['SYSTEMROOT']}\\system32\\WindowsPowershell\\v1.0\\powershell.exe" 	else 	  'powershell.exe' 	end    def add_user_to_group     #   end    def exists?     #add transform to array if just a string          groups = resource[:groups]     if groups.kind_of?(String)       groups.to_a      end        found = false      groups.to_a.each do |group|       Puppet.debug("Checking the existence of value: #{self} in #{group}")       result = powershell 'if (([ADSI]"WinNT://$env:computername/'+group+'").IsMember(([ADSI]"WinNT://$env:userdomain/'+ resource[:name]+'").ADsPath) -eq $False){echo 0} else {echo 1}'                    if result.chomp == "0" #if not found (ps returned false on search of user in group)         Puppet.debug("User '#{resource[:name]}' is not found in group '#{group}'")         found = false #         break       else         Puppet.debug("User '#{resource[:name]}' is found in a group '#{group}'")         found = true       end     end     found   end    def create     groups = resource[:groups]     if groups.kind_of?(String)       groups.to_a      end      groups.to_a.each do |group|       Puppet.debug("Adding user to a group #{self}")       powershell 'if (([ADSI]"WinNT://$env:computername/'+group+'").IsMember(([ADSI]"WinNT://$env:userdomain/'+ resource[:name]+'").ADsPath) -eq $False){$([ADSI]"WinNT://$env:computername/'+group+'").Add(([ADSI]"WinNT://$env:userdomain/'+resource[:name]+'").ADsPath)} else {echo "User is already in a group"}'     end   end    def destroy        end end 

Для настройки параметров WMI пришлось пользоваться сторонней opensource утилитой wmisecurity.exe. Для ее установки я создал пакет на chocoaltey.org — wmisecurity. Для установки пакета я использовал puppet-провайдер chocolatey, который я использую постоянно.

И вот сам puppet-манифест, который использует раннее написанный модуль, а также содержит powershell хуки для добавления прав доступа к wmi классам для пользователя (возможно перепишу это как отдельный модуль позднее):

wmi.pp

class packages::wmi {	 	 	$wmiuser = 'service-user' 	 	###Doesn't work on windows right now 	#user { $wmiuser: 	#		groups => ['Certificate Service DCOM Access','Performance Log Users','Performance Monitor Users', 'Distributed COM Users'], 	#	}  	     win_user { $wmiuser:       groups => ['Certificate Service DCOM Access','Performance Log Users','Performance Monitor Users', 'Distributed COM Users'],       ensure => present_local,     }  	###it is required to add user to those local groups in order monitoring to perform correctly. 	 	exec {"add-to-wmi-cimv2": 		command => "wmisecurity.exe /C=\$env:computername /A /N=Root/CIMV2 /M=\$env:userdomain\\$wmiuser:REMOTEACCESS /R", 		path => $::path,		 		#if found user guid - skip 		onlyif => "if (WmiSecurity.exe /c=\$env:computername /N=Root/CIMV2 /R | Select-String $($(New-Object System.Security.Principal.NTAccount( 		\"\$env:userdomain\", '$wmiuser')).Translate([System.Security.Principal.SecurityIdentifier]).Value)){exit 1} else {exit 0}", 		provider => powershell, 		require => Package['wmisecurity'],	 	}	 	 	exec {"add-to-wmi-microsoftiisv2": 		command => "wmisecurity.exe /C=\$env:computername /A /N=Root/MicrosoftIISv2 /M=\$env:userdomain\\$wmiuser:REMOTEACCESS /R", 		path => $::path,		 		#if found user guid - skip 		onlyif => "if (WmiSecurity.exe /c=\$env:computername /N=Root/MicrosoftIISv2 /R | Select-String $($(New-Object System.Security.Principal.NTAccount( 		\"\$env:userdomain\", '$wmiuser')).Translate([System.Security.Principal.SecurityIdentifier]).Value)){exit 1} else {exit 0}", 		provider => powershell, 		require => Package['wmisecurity'],	 	} 	 	package {'wmisecurity': 		provider => 'chocolatey', 		install_options => '-pre',		 		require         => Class["packages::chocolatey"] 	} } 

Заключение

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

wmi.pp

class packages::wmi {	 	 	$wmiuser = "${env:userdomain}\\service-user"	 	 	     user { $wmiuser:       groups => ['Certificate Service DCOM Access','Performance Log Users','Performance Monitor Users', 'Distributed COM Users'],       ensure => present,     } 	 	wmi_security_user { $wmiuser: 		namespaces => ['Root/CIMV2','Root/MicrosoftIISv2'], 		ensure => present, 	} } 

Теперь при настройке нового сервера мне остается назначить класс packages::wmi на этот сервер (в ручную или через include) и все, puppet сделает свое дело. Лично я чаще всего использую этот класс через класс opsview, который автоматически создает хост для мониторинга в opsview и назначет нужные шаблоны, т.е. если это, скажем, сервер c IIS, итоговый puppet-класс сообщит opsview всю необходимую информацию о том, что это хост с IIS, с такими-то и такими-то хостами которые нужно тоже мониторить определенным образом, а также назначит в opsview шаблон мониторинга через wmi, который зависит от класса который мы описали выше. Вот так, вроде ничего не упустил.

Пара скриншотов результата:


ссылка на оригинал статьи http://habrahabr.ru/post/204306/

История создания проекта успешного игрового хостинга

Приветствую всех хабражителей!

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

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

Почему именно хостинг?

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

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

А почему Minecraft?

По требовательности к ресурсам Minecraft значительно уступает той же Lineage, а потому позволяет мне развернуть несколько аккаунтов из-под небольшого выделенного сервера с полным спокойствием за благополучие клиентов.

По своей популярности игрушка уже давно перешагнула порог в 30 миллионов пользователей и по сей день продолжает набирать обороты. Ввиду доступности и большого количества несовершеннолетней аудитории, а также экономически-ориентированным игровым уклоном идея внутренней монетизации здесь идет «на ура». Однако хостингов, предоставляющих подобные услуги было очень много и все они имели одно но – все они ограничивают клиента привязкой ресурсов к слотам.

Поэтому был избран иной путь. Было принято решение не ограничивать слоты а ограничить ресурсы, при этом сохранив низкую стоимость услуг, более того – развернуть все это на базе российской локации. Создать эдакую монополию на российском рынке подобных услуг. Такие условия очень быстро привлекли клиентов, и уже через неделю мы стали довольно популярны.

Какие возникли проблемы?

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

Более того, клиенты склонны скептически относится к молодому хостингу. Многие верят в истинное расположение серверов лишь после предоставления тестового сервера. В целом же основная масса хостингом остается довольна.

Как и многие другие подобные кампании, мы неоднократно сталкивались с DDoS-атаками. Были то просто чьи-то попытки напакостить или нападение велось от лица конкурентов — неизвестно. Однако, наши админы успешно справляются с подобными казусами. Сервера стабильны, клиенты довольны. На базе дата центров используем хардварные системы фильтрации траффика, а собственный сайт проксируем через несколько крупных узлов связи где вручную режем «плохой» траффик.

А почему вы находитесь на поддомене?

Так сложилось исторически. Проект взял свое начало с закрытого сообщества (abcd.bz), на котором было предложено организовать подобный сервис. Среди участников нашелся тот, кто предложил первый сервер для запуска, помог организовать первоначальную работу. Благодаря этому старт обошелся всего в 150 долларов.

Как это работает?

Серверная часть представлена следующими конфигурациями:
2 х Intel Xeon E5-2670 / 128 GB RAM / raid 5 на SSD дисках / 1 гбит сеть
4 х Intel Xeon E5-4607 / 512 GB RAM / raid 5 на SSD дисках / 1 гбит сеть

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

К уникальным «боксовым» услугам можно отнести ежесуточный полный бекап пользовательских данных на собственный SAN, бесплатный web хостинг для клиентов (под сайт сервера/БД/etc), да даже то что мы не ограничиваем слоты оставляя возможность клиенту решить самому сколько установить слотов. Многие скажут что это первый шаг к оверселлу – но нет, это не так. Мы жестоко ограничиваем именно физические ресурсы аккаунта квотами, как говорится – выше потолка не прыгнешь, если клиент жалуется на лаги – проверяем соответствует ли его запросам тарифный план который он заказал, а там решаем повысить тариф, либо провести оптимизацию сборки. Многие заказывают самый дешевый тариф, ставят 100500 слотов и дырявые сборки с leak ошибками, после чего жалуются и оставляют тонны негативных отзывов, но даже такие проблемы мы успешно решаем.

В биллинге всегда онлайн 1 и более специалистов технической поддержки, которые повседневно работают с серверной частью minecraft’a и помогают решать клиентам их вопросы и проблемы.

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

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

Чем мы отличаемся от других?

1. Мы не загружаем сервера на 100%, тем самым обеспечивая бесперебойную и стабильную работу клиентским аккаунтам.
2. Мы не лимитируем слоты, ограничиваем лишь физические ресурсы.
3. Наша ценовая политика куда более доброжелательна к клиенту в сравнении с другими сервисами.

Зачем я вообще все это прочитал?

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

Желаем успеха в ваших проектах!
Спасибо за уделенное внимание.

ссылка на оригинал статьи http://habrahabr.ru/post/204304/

Производящие функции — туда и обратно

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, …, gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа, который как мы все знаем очень большой.

Вышесказанное можно записать с помощью математических формул следующим образом: <g0, g1, g2, …, gn> <=> g0 + g1z + g2z2 +… + gnzn +…. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

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

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,…, 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернемся немного позже, после того как разберемся более подробно с устройством производящих функций.

Метод производящих функций

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

Обозначим белый шар символом ○, черный — ●, Tn — искомое количество расположений шаров, общее количество которых равно n. Символом Ø обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнем с тривиальных случаев:

Если n = 1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять черный шар ●, таким образом, T2 = 2.

Если n = 2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n = 3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать черным шаром и аналогично продолжить 4-мя способами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T3 = 2T2. Аналогично T4 = 2T3, то есть, обобщая для всех n получаем рекуррентное уравнение Tn = 2Tn-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — Tn = 2n (так как 2⋅2n-1 = 2n).

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

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о справедливости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением все понятно, но что значит умножение шаров? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, то есть ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○●.

Произведем с рядом G последовательность манипуляций, а именно вынесем за скобки белый и черный шары:

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + …) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + …) = Ø + ○G +●G.

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

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

Далее воспользуемся формулой бинома Ньютона: , где — число сочетаний из n по k.

Тогда с учетом этого имеем: .

Коэффициент при ○kn-k равен показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Как известно .

Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (так как цвет шара не играет роли). Получим , то есть коэффициент при zn равен 2n.

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g0 + g1z + g2z2 +… + gnzn +… причем коэффициенты gk — являются ключом к решению исходной задачи. Тот факт, что ряд является формальным, говорит о том, что z — является просто символом, вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g0 + g1z + g2z2 +… + gnzn +… — называется производящей функцией для последовательности чисел <g0, g1, g2, …, gn>. Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z значение z = z0, за исключением z = 0, так как G(0) = g0.

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому.

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

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, …, 1> в бесконечном виде представляется как 1 + x + x2 + x3 + …, а в замкнутом .

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 20, 21, 22,…, 2n грамм и сколькими способами?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z2)(1+z4)(1+z8)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = g0 + g1z + g2z2 +… + gnzn +….

Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при zk, а zk — получается как произведение каких-то одночленов z2m, то есть gk — это в точности число разных представлений числа k в виде суммы некоторых из чисел 20, 21, 22, 23,…,2m,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера не менее удивителен. Он умножает обе части равенства на (1-z).


С одной стороны G(z) = g0 + g1z + g2z2 +… + gnzn +… с другой стороны мы только что получили G(z) = . Но ведь . Сопоставляя эти два равенства, получаем g1 = g2 = g3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Вот так вот Эйлер применил метод производящих функций при решении задач.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает ее рекуррентный вид: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 ,n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число в своем составе (кстати, это число есть не что иное как «золотое сечение»).

Итак, имеем

F0 = 0,
F1 = 1,
Fn = Fn-1 + Fn-2, n ≥ 2

Умножим каждую строчку на z0, z1, …, zn соответственно:

z0 ⋅ F0 = 0,
z1 ⋅ F1 = z,
zn ⋅ Fn = zn ⋅ Fn-1 + zn ⋅ Fn-2 ,n ≥ 2

Просуммируем эти равенства:

Обозначим левую часть

Рассмотрим каждое из слагаемых в правой части:

Имеем следующее уравнение:


решая которое относительно G(z) находим — производящая функция для последовательности чисел Фибоначчи. Следующим шагом является ее разложение в степенной ряд, а для этого разложим ее на сумму простейших дробей.
Корни уравнения 1 — z — z2 = 0 —
Тогда нашу производящую функцию можно разложить следующим образом:


Методом неопределенных коэффициентов или подстановки различных значений z находим .
Напоследок немного преобразуем выражение для производящей функции:


Теперь каждая из дробей представляет собой сумму геометрической прогрессии. По формуле

находим .

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

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

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

  1. Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g-1=g-2=….=0.
  2. Умножьте обе части уравнения на zn и просуммируйте по всем n. В левой части получится сумма , которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z).
  3. Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
  4. Разложите G(z) в степенной ряд и прочитайте коэффициент при zn, это и будет замкнутый вид для gn.

Причина работоспособности этого метода в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.

Давайте для закрепления алгоритма рассмотрим еще один пример (более сложный). Пусть надо решить такое рекуррентное уравнение:

g0 = 1,
g1 = 1,
gn = gn-1 + 2gn-2 + (-1)n

По первым значениям n трудно сказать что-либо об общей формуле:

n 0 1 2 3 4 5 6
gn 1 1 4 5 14 23 52

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z0⋅g0 = 1,
z⋅g1 = z,
zn⋅gn = zn⋅gn-1 + 2zn⋅gn-2 + (-1)n⋅zn

Левая часть — представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Составляем уравнение:

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

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

Собственно все. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Попробуйте решить такое рекуррентное уравнение:

g0 = 1,
g1 = 2,
gn = 6gn-1 — 8gn-2 + n

Подсказка

Ответ

Заключение

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

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

ссылка на оригинал статьи http://habrahabr.ru/post/204258/

Расширение хабры для браузера. Прочитанность комментариев одним взмахом мыши

Позволяет одним движением мыши помечать новые комментарии прочитанными.

Сделаны версии для трёх браузеров — Chrome, Opera и Firefox.

Нужно зажать Shift и провести мышкой над новыми комментариями — каждый комментарий, над которым прошла мышь, будет прочитан.
Не нужно долго ждать, пока стандартная фича от Хабры прокрутит до каждого нового комментария.
Удобно в случае, если новые комментарии расположены близко и их видно все сразу. Один взмах мыши — и всё готово.

Если зажать Ctrl-Shift, то сбросятся также все дети от того комментария, над которым провели мышкой.

Делал для себя, но вдруг кому-нибудь будет полезно.

Код очень простой, сделан быстренько на jquery, позже оптимизирую без jquery.

        that.$('.comment_item > .comment_body')         	.live('mouseover', function(event) {         		if (event.shiftKey) {         			var el = that.$(this);         			var root = !event.ctrlKey ? el : el.parent();         			var info = root.find('.info.is_new');         			if (info.length) { 	        			info.removeClass('is_new'); 	        			var xpanel_new = that.$('#xpanel .new'); 	        			var n = xpanel_new.html()|0; 	        			n -= info.length; 	        			if (n < 0) { 	        				n = 0; 	        			} 	        			xpanel_new.html(n); 	        			if (!n) { 		        			xpanel_new.hide(); 	        			} else { 		        			xpanel_new.show(); 	        			}         			}         		}         	}) 

Для Firefox сделано на движке jetpack, код запуска content-скрипта:

exports.main = function(options, callbacks)  { 	var data = require("sdk/self").data;      require("sdk/page-mod").PageMod({       	include: "*.habrahabr.ru",        	attachTo: ["existing", "top", "frame"],        	contentScriptFile : [       		data.url("includes/jquery-1.8.0.min.js"),       		data.url("includes/content.js")         ],          contentScriptWhen : 'end'     }); }; 

Для старой Оперы (до 15) для запуска content-скрипта необходимо скрипты положить в папку /includes

ссылка на оригинал статьи http://habrahabr.ru/post/204302/