?

Log in

No account? Create an account
yvl [entries|archive|friends|userinfo]
yvl

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

О науке [Dec. 9th, 2010|10:55 pm]
yvl
Как и ремонт квартиры, диссертацию нельзя закончить, ее можно только остановить.
link3 comments|post comment

Holy fucking shit! (P \neq NP) [Aug. 7th, 2010|08:29 pm]
yvl
[Current Location |Canada, Vancouver]
[mood |excitedexcited]

Похоже, мы станем свидетелями огромного прорыва человеческой мысли. По сообществу поползло докзательство разделения классов сложности P и NP. Эта задача является ключевой в теории вычислительных систем и математике вообще и находится в числе задач тысячелетия. По моему мнению она далеко опережает все остальные задачи по их практическим последствиям. Доказательство занимает 102 страницы (с библиографией) и применяет весьма обширный матаппарат.

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

Стив Кук по поводу этого доказательства сказал "Это кажется сравнительно серьезной заявкой на решение вопроса P vs NP". Будем ждать реакции от сообщества, а пока сами на досуге полистаем.

Итак, похоже криптографы смогут спать спокойно, а народ занимающийся вероятностными алгоритмами и алгоритмами приближения будет мощно бухать на радостях. Ну и мы в стороне не останемся и в очередной раз поразимся красоте и сложности нашей Вселенной.
link32 comments|post comment

How CPU burns with shame. [Jul. 2nd, 2010|10:56 pm]
yvl
A problem from Computer Architecture midterm I gave:

Yaroslav decided to overclock his legacy Intel 486 DX 2 66 MHz CPU.
• He set the clock rate to 100 MHz. The processor did not work. He set the clock rate back to 66 MHz, but the CPU stopped working even at the specified rate. Explain as fully as possible in at most 4 lines of text what happened and why.
• Yaroslav went to the flea market and bought another 486 DX 2 66 MHz CPU equipped with a large copper heat sink. He set the clock rate to 100 MHz, but the CPU did not work. However, it worked at 75 MHz. Using propagation delay analysis, explain what was happening with CPU at 66MHz, 75 MHz, and 100 MHz. Write at most 6 lines of text.



One of the replies to the first part:

"...the CPU could not handle the clock rate and began making errors; the errors build up heat on the CPU and causes the circuit to overheat..." @g
link1 comment|post comment

"Зочем вы кгасите" (с) или истинно декларативная проверка графа на двудольность [Dec. 25th, 2009|01:24 pm]
yvl
Рождество - прекрасное время, когда оценки выставлены и есть время высказаться по поводу двудольных графов. Вторая реализация ("в декларативном стиле"), написанная _adept_ элегантна и эффективна (настолько, насколько эффективны используемые библиотечные функции). Но все же, она использует алгоритм для проверки двудольности, а не определение двудольности напрямую. Что можно было бы сделать, если бы мы уже придумали двудольный граф, но еще не придумали алгоритм?

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

Итак, Неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части U \cup V = W, | U | > 0, | V | > 0, так, что
* ни одна вершина в U не соединена с вершинами в U и
* ни одна вершина в V не соединена с вершинами в V
Иными словами, в таком разбиении оба множества U и V независимы.

Разбиение можно задать одним множеством, при этом V будет его дополнением. Множество таких разбиений - булеан множества вершин. Значит,

isBipartite g = any bothIndependent (powerset (nodes g))
           where
                bothIndependent a = independent a && independent ((nodes g) \\ a)

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

               independent a = null $ edges $ delNodes ((nodes g) \\ a) g

Наконец, булеан (множество всех подмножеств). Приведу два варианта. Если у нас есть множество xs для которого известен булеан acc и мы расширим xs добавив в него элемент x, то булеан для этого расширенного множества будет состоять из acc объединенного с acc', в котором каждый из членов был расширен элементом x:

               powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]

Второй вариант использует понятие индикаторной(характеристической функции) подмножества. Булеан - множество всех подмножеств, поэтому можно построить его, рассмотрев все возможные индикаторы. Задав порядок на множестве (в Хаскеле мы получаем его "бесплатно" если держим множества в списках) можно представлять индикаторы в виде двоичных векторов. Итак,

powerset xs = map subsetByIndicator $ map binExpansion [0..2^(length xs)-1]
  where      
    subsetByIndicator p = [x|(x,i)<-(zip xs p), i==1]
    binExpansion x = mod x 2 : binExpansion (div x 2)


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


import Data.Graph.Inductive hiding (empty)
import Data.List
{-a bipartite graph (or bigraph) is a graph whose vertices can be divided into two
 disjoint sets U and V such that every edge connects a vertex in U to one in V;
 that is, U and V are independent sets-}
{-Any subset of vertices defines a partition (itself and its complement).
 Thus, we consider a powerset of vertices and if one of the elements in powerset
 and its complement both are independent, the graph is bipartite-}
isBipartite g = any bothIndependent (powerset (nodes g))
  where
{- We will check whether set a and its complement ((nodes g) \\a) are
   both independent-} 
    bothIndependent a = independent a && independent ((nodes g) \\ a)
{-A set of vertices is independent if no two verices in it are connected,
 meaning that induced subgraph formed by removing the rest of the vertices
 has no edges-}
    independent a = null $ edges $ delNodes ((nodes g) \\ a) g
{-If acc is a powerset of some set xs and we extend xs by element x, the new
  powerset will be formed by original sets acc united with every element of
  acc extended by x-}
    powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]

makeGraph :: [(Int,[Int])] -> Gr () ()
makeGraph g = mkUGraph vs es
  where vs = map fst g
        es = [(n1,n2) |  (n1,es) <- g, n2 <- es]
bipartite = 
  [(0,[1]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]
                
not_bipartite = 
  [(0,[1,2]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]

main = do
  print $ isBipartite $ makeGraph bipartite
  print $ isBipartite $ makeGraph not_bipartite
link26 comments|post comment

Прекрасное [May. 25th, 2009|05:41 pm]
yvl
Вчера по дороге на Pitt Lake видели прекрасное. Ферма с полем, примыкающем к Dewdney Trunk Rd. По полю поверх борозды едет трактор в конфигурации бульдозер. Ковш приподнят, в ковше в медитативных позах сидят трое престарелых сикхов в ослепительно белых одеждах и тюрбанах. Ветер развевает снежно-седые бороды и усы. Каждый сикх руками сыплет семена в одну из трех борозд, доступных с ковша.
link3 comments|post comment

Внезапное Преподавание Функционального программирования, ч. 1 - background [Aug. 30th, 2008|09:40 pm]
yvl
[Tags|, ]
[Current Location |lab]
[music |Buck 65 - Phil]

По причине болезни профессора довелось мне в уходящем семестре внезапно прочитать с середины курс по Функциональному Программированию. Курс был cross-listed, то есть 2 в одном, и для бакалавров 4 курса, и для магистров/докторантов (любого года :) ). Поскольку когда-то возможно прийдется читать такой курс еще, под катом - мой background в ФП, заметки про впечатления от чтения курса, исправления на будещее, и линк на слайды, сделанные для курса. В основном - для меня, но может кому-то еще это интересно. За один раз все не напишу, будет несколько заметок.

Интересующимся жать сюдаCollapse )
linkpost comment

No End in Sight (2007) [Aug. 30th, 2008|08:20 pm]
yvl
[Tags|]

З великим здивуванням побачив на ресурсі ймовірного союзника статтю про те, що на YouTube скоро покладуть чудовий документальний фільм про війну США в Іраку No End in Sight. Всім, кого цікавить питання: "Чому у США не виходить навести лад в Іраку" - дивитися обов'язково. Так само тим, хто хоче подивитися на мабуть найкращий взірець сучасної політичної документалістики, тим, кого цікавлять питання сучасних війн, ефективності демократії, т.т.і. І хоча чекати YouTube вже недовго, цей фільм вже досить давно лежить на гуглвідео:
link4 comments|post comment

Fucked up в смысле "прекрасноe"... [Aug. 29th, 2008|05:56 pm]
yvl
[Tags|]

Кому не шкода своєї психіки - дивимося чудовий відеокліп Apex Twin "Rubber Johnny". Щодо психіки - я серйозно, подумайте. Воно вам треба?Collapse )
link1 comment|post comment

Посмтрели Бэтмэна [Jul. 21st, 2008|04:28 pm]
yvl


Major Boring Shit.


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

А пока - с нетерпением жду, когда страна - правопреемник СССР выпустит блокбастер "Murzilka - The Beginning". Сколько можно экранизировать посредственные произведения клонированного Круга? Ведь у нас есть свои комиксы! Мурзилке, между прочим, 80 лет.

linkpost comment

Happy Birthday to me! [Jul. 3rd, 2008|12:49 am]
yvl
[music |Metallica - The call of Ktulu]

subj.
ps For some reason USA always celebrate my b-day one day later and Canada 2 days earlier....

link3 comments|post comment

navigation
[ viewing | most recent entries ]
[ go | earlier ]