Ruby NoName Podcast S04E10

Подкаст

http://ruby.rpod.ru/276289.html ^[1]

Новости

Libskypekit and Skypekit – C and Ruby interface for Skype ^[2]
Gem для работы с Google spreadsheet ^[3]
Поддержка PostgreSQL datatypes в Rails 4 ^[4]
Ruby 2.0 roadmap ^[5]
The Bastards Book of Ruby ^[6]
Continuos deployment for ruby gems ^[7]
Ruboto 0.6.0 ^[8]
Mechanize 2.5 ^[9]
Гем для асинхронной отсылки почты из devise - devise-async ^[10]
Глава из книги Ruby Under a Microscope ^[11]
Последняя попытка попасть на devConf ^[12]

Обсуждение

NP-полнота

Для ознакомления с базовыми определениями и теоремами рекомендуется к прочтению книга: М. Гэри, Д. Джонсон,
«Вычислительные машины и труднорешаемые задачи».
Random_k-SAT ^[13]
[VV1986] L. G. Valiant, V. V. Vazirani, NP is as easy as detecting unique solutions ^[14] (показано, что поиск solutions to instances having a unique solutions, are as hard as SAT, under randomized reduction)
[Var1982] M. Vardi, Complexity of Relational Query Languages ^[15]
[Imm1986] N. Immerman, Relational Queries Computable in Polynomial Time ^[16] ([Imm1982] и [Var1982] дают th. Immerman-Vardi, что FO(LFP) = P)
Wiki, где собраны основные данные о проверке и paper ^[17]
По всей видимости первое или одно из первых упоминаний в интернете о paper ^[18]
Первый комментарий проф. Liption ^[19]
Ссылки на остальные есть в wiki, вот еще важный комментарий ^[20],
где Liption публикует письмо Immerman, что Deolalikar безосновательно использует только mondaic fixed points и
указывает, что он полагается на это свойство в своем доказательстве, но указывает, что тогда он получает не все P. Тем
самым получается, что Deolalikar неправильно применяет теорему Immermana-Vardi. Ошибка найдена!
Прочее: упоминал «кирпич»: Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ»

Текущее

Наш конкурс закончился, результаты подводятся
Иван Евтухович ушел работать ^[21] в Express42 ^[22].

Контакты

Наш твиттер ^[23]
Email для предложенией ^[24]

Автор: kronos

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/ruby/8467

Ссылки в тексте:

[1] http://ruby.rpod.ru/276289.html: http://ruby.rpod.ru/276289.html

[2] Libskypekit and Skypekit – C and Ruby interface for Skype: http://blog.railsware.com/2012/05/11/libskypekit-and-skypekit-c-and-ruby-interface-for-skype/

[3] Gem для работы с Google spreadsheet: https://github.com/nesquena/sheet_mapper

[4] Поддержка PostgreSQL datatypes в Rails 4: http://reefpoints.dockyard.com/ruby/2012/05/18/rails-4-sneak-peek-expanded-activerecord-support-for-postgresql-datatype.html

[5] Ruby 2.0 roadmap: http://bugs.ruby-lang.org/projects/ruby-trunk/versions/#2.0.0

[6] The Bastards Book of Ruby: http://ruby.bastardsbook.com/

[7] Continuos deployment for ruby gems: http://hackers.mylookout.com/2012/05/continuous-deployment-for-gems/

[8] Ruboto 0.6.0: https://github.com/ruboto/ruboto/wiki/Ruboto-0.6.0-release-doc

[9] Mechanize 2.5: http://blog.segment7.net/2012/05/09/mechanize-2-5

[10] devise-async: https://github.com/mhfs/devise-async

[11] Ruby Under a Microscope: http://patshaughnessy.net/2012/5/9/one-chapter-from-my-upcoming-ebook-ruby-under-a-microscope

[12] devConf: http://devconf.ru/join/?coupon=railsclub

[13] Random_k-SAT: http://michaelnielsen.org/polymath1/index.php?title=Random_k-SAT

[14] NP is as easy as detecting unique solutions: http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf

[15] Complexity of Relational Query Languages: http://www.dcc.uchile.cl/~cgutierr/cursos/CC/vardi-complex-bd.pdf

[16] Relational Queries Computable in Polynomial Time: http://people.cs.umass.edu/~immerman/pub/query.pdf

[17] Wiki, где собраны основные данные о проверке и paper: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper

[18] первое или одно из первых упоминаний в интернете о paper: http://gregbaker.ca/blog/2010/08/07/p-n-np/

[19] Первый комментарий проф. Liption: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

[20] вот еще важный комментарий: http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

[21] ушел работать: http://blog.evtuhovich.ru/blog/2012/05/23/new-work/

[22] Express42: http://express42.com

[23] Наш твиттер: https://twitter.com/#!/rubynoname

[24] Email для предложенией: mailto:evtuhovich@gmail.com

Нажмите здесь для печати.