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

Сегодня решил заказать себе «The Best Test Preparation for the GRE Computer Science Test» и еще кучу разной фигни, как вдруг неожиданно для себя выяснил, что за те ссылки, что я ставил, я по партнерской программе за три года ведения блога заработал аж 150 рублей. Успех.

Не совсем тот эффект, которого я хотел, но тоже занятно. Хвастаюсь вот всем теперь.

Читатель measure_0 порекомендовал мне в прошлой заметке пройти тесты GRE subject tests. Какие именно он не уточнил, но я так решил, что видимо по моему направлению это должны быть mathematics и computer science. Скачал примеры тестов по обоим дисциплинам. Тест по математике оказался вроде простым (если не брать в расчет, что там на каждую задачу по 2 минуты, а задачи бывают и не только элементарные). А вот тест по Computer Science оказался для меня каким-то запредельно сложным и у 50% вопросов я даже толком не понимаю о чем там спрашивают. Проблемы у меня вызывают в основном вопросы, связанные с компьютерным железом и архитектурой операционных систем, хотя и в теоретических вопросах бывают какие-то загвоздки.

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

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

В этой записи я предлагаю коллективными усилиями набросать список литературы по темам Computer Science с прицелом на GRE. Не потому что это какой-то супер-важный экзамен, а просто судя по всему он покрывает на мой взгляд довольно широкий и довольно правильный спектр тем, которыми хорошо бы овладеть быдлокодеру, который ожидает какого-то профессионального роста. Поэтому ниже я привожу темы, заявленные как необходимые для сдачи GRE, а комментаторам я предлагаю предлагать источники, по которым это можно изучать (книги, видеолекции, и подобное — главное чтобы это было возможно достать рядовому пользователю сети Интернет). В комментариях предлагаю указывать собственно источник, темы, которые он покрывает, и уровень — вводный/GRE/продвинутый. Заметку я буду обновлять по мере поступления новых ссылок на материалы.

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

Собственно темы (извиняюсь за дебильную верстку — это почти копипаста, видимо позже поправлю):

SOFTWARE SYSTEMS AND METHODOLOGY
A. Data organization
• Data types
• Data structures and implementation techniques

B. Program control and structure
• Iteration and recursion
• Procedures, functions, methods and exception handlers
• Concurrency, communication and
synchronization

C. Programming languages and notation
• Constructs for data organization and program control
• Scope, binding and parameter passing
• Expression evaluation

D. Software engineering
• Formal specifications and assertions
• Verification techniques
• Software development models, patterns and tools

E. Systems
• Compilers, interpreters and run-time systems
• Operating systems, including resource management and protection/security
• Networking, Internet and distributed systems
• Databases
• System analysis and development tools

II. COMPUTER ORGANIZATION AND ARCHITECTURE
A. Digital logic design
• Implementation of combinational and sequential circuits
• Optimization and analysis

B. Processors and control units
• Instruction sets
• Computer arithmetic and number representation
• Register and ALU organization
• Data paths and control sequencing

C. Memories and their hierarchies
• Performance, implementation and management
• Cache, main and secondary storage
• Virtual memory, paging and segmentation

D. Networking and communications
• Interconnect structures (e.g., buses, switches, routers)
• I/O systems and protocols
• Synchronization

E. High-performance architectures
• Pipelining superscalar and out-of-order execution processors
• Parallel and distributed architectures

III. THEORY AND MATHEMATICAL BACKGROUND
A. Algorithms and complexity
• Exact and asymptotic analysis of specific algorithms
• Algorithmic design techniques (e.g., greedy, dynamic programming, divide and conquer)
• Upper and lower bounds on the complexity of specific problems
• Computational complexity, including NPcompleteness

B. Automata and language theory
• Models of computation (finite automata, Turing machines)
• Formal languages and grammars (regular and context-free)
• Decidability

C. Discrete structures
• Mathematical logic
• Elementary combinatorics and graph theory
• Discrete probability, recurrence relations and number theory

IV. OTHER TOPICS

• Numerical analysis
• Artificial Intelligence
• Computer graphics
• Cryptography
• Security
• Social issues

UPD: Эту заметку я все-таки не буду корректировать видимо. Лучше когда сам примерно буду иметь представление как правильно готовиться, сделаю отдельный удобный и адекватный обзор. Но пока все равно есть смысл дискутировать в комментариях.

Давно уже очень хотел отрекомендовать ставшей классической в узких кругах книгу «Исход». Скачать и почитать можно много где, она легко гуглится, например вот даже тут: http://rghost.ru/1299967.

Собственно написать что-то сложно о книге — надо читать. Это такое депрессивное чтиво в духе Достоевского, только на современный лад и замешанное на насилии и говне. Для тонких ценителей плохого настроения и ненависти. Вот например отрывок:

  …Этот парень, он неплохо одет, скромно, со вкусом. Аккуратная стрижка, волевые черты лица, выглядит атлетически, занимается спортом, уверенный взгляд карих глаз. Он не из всех этих модных пидорков, он серьезный, хороший парень – сильный, смелый, нормальный мужик. Он расчетлив, но любит азарт, момент и кураж игры. Нос с небольшой горбинкой – сломали в драке, этот парень не понаслышке знает вкус крови на губах, он всегда готов постоять за себя и близких. У него много друзей, среди них он пользуется заслуженным уважением. Много подруг, которые любят его за то, что в нем есть что-то опасное, рискованное, что-то мужское, чего так не хватает в обычных городских парнях. Он увлекается, страстно играет, легко тратит деньги, легко выкручивается из сложных ситуаций, он еще молод, но уже очень опытен. И серьезен, он хороший парень, у него есть правильное представление о том, как надо прожить свою жизнь. Не только красиво, с задором, веселыми девчонками и шальными друзьями, но вдумчиво, так, чтобы не было стыдно за бесцельно проведенные годы молодости. Надо знать, понимать. Надо любить свою страну, уважать отца и мать, защищать свои жизненные принципы, не злоупотреблять алкоголем, найти хорошую девушку, создать семью, воспитать детей. Все сделать как надо, красиво прожить красивую жизнь, на одном дыхании.
Вот этот парень стоит вечером у магазина, и я подхожу к нему сзади. В растянутом свитере, в грязных кроссовках, неаккуратно выбритая «под ноль» голова, подростковые усы, прыщи на всем лице, гнилые зубы. Через секунду этот отличный парень превратится в кусок говна, обрезок железной трубы сделает из его головы кровавый фарш. Зубы, куски кожи, кровь во все стороны. Я двоечник с последней парты, меня презирают одноклассники, я бухаю и дрочу. У меня впалая грудь, рахитичное пузо, я предрасположен к астме, плохое сердце. Никогда не было нормальной работы, никогда не было папы, никогда не было девушки, через секунду я отомщу этому пидарасу за все эти годы, за всю мою жизнь, за всех таких же, как я, придурков, за убогих, за больных, за детей из семей бюджетников, за тупых, инфантильных, за всех неудачников, которые составляют охуительный процент населения нашей страны. Я буду бить его по голове обрезком железной трубы за всех нас, и в этом будет что-то от святости. Или в святости всегда есть что-то от этого…

Ну и там вся книга в общем-то такая. Просто нарезка из некрасивых сюжетов.

Буквально пару слов об авторе и подоплеке текста.

Написана книга Петром Силаевым (он же Пит, он же Тед Качински, он же DJ Stalingrad, он же еще куча имен), который вначале был наиболее известен как вокалист антифа-группы «Проверочная линейка». Группа на мой взгляд полное дерьмо вообще-то, но культовая — она оказала большое влияние на субкультурную молодежь и сыграла немалую роль в начале формирования движения Антифа, а так же в популяризации движения straight edge (субкультура, в которой люди не пьют, не курят, не употребляют наркотики, трахаются только с любимыми, с которыми состоят в постоянных и длительных отношениях, не едят мясо и вообще молодцы). На данный момент Пит находится в розыске за организацию нашумевшего прошлогоднего Химкинского погрома. Насколько я понимаю обвинение строится на том, что это именно он идет с мегафоном впереди всех и заряжает «Они охуели!». Книга при этом тему субкультур или антифашизма практически не затрагивает. Это отвлеченное от темы художественное произведение, а не политический текст.

Книгу Пит писал после убийства друга, антифашиста Федора Филатова, которое произошло 10 октября 2008 года. Отсюда и такой настрой. Сам я читал «Исход» когда только еще начинал вливаться в антифашистское движение, но уже знал некоторых ребят из тех, кто был участником событий, описанных в книге. Я помню тогда немного подохерел от прочитанного и начал доставать всех знакомых вопросами на тему что они думают о книге и насколько она правдива. Ребята меня тогда уверили, что Пит во многом сгустил краски, и что некоторые эпизоды вымышлены (например про наркотики), а многие значительно приукрашены подробностями, которых в действительности не было. Сейчас я понимаю уже и сам, что в общем-то действительно сгустил. Но книга менее талантлива от этого не становится.

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

Ну и вот отрывок, который сейчас часто вспоминают:

Вот так бывает. он уже ложился спать, вдруг звонок — как обычно, уже привыкли. Он берет все свои деньги, нож, ствол, выходит из дома. У дверей оглядывается, видит мать на кухне капает валокордин в стакан. Опять подслушивала. Садится на скутер, едет в центр в 3 часа ночи, чтобы вытаскивать ребят, всех этих пацанов которым нет и двадцати, из какой-то очередной безвыходной ситуации, в которой они могут умереть или сесть. Снова сегодня, как и месяц, и год назад, и все время. Он всегда так делал. Приезжал всегда первый, подбадривал, орал на ментов, совал деньги, звонил кому надо, носил передачки, стоял у отделений по всей москве часами. Вот так как бы человек жил. Другой жизни у него не было. Действительно, не было. Вся жизнь в нищите, в маленькой квартирке с мамой, семьей сестры, в комнате, размером с ванную. Вся жизнь на работе в каких-то складах, на заводах, в грязных стоячках, плохой алкоголь, плохая жизнь. Много лет. У него ничего не было, кроме друзей, кроме всех тех людей, что его окружали и которым он отдавал всегда всего себя, всего целиком, зачем-то. Верть им, доверять, жить их проблемами, жить в них — то что он и умел, одно из не очень большого списка. Таких людей сейчас уже нет. Не помнить себя и жить полностью заботами и радостями твоих близких, в счастье и в горе… как же это…

Тогда он тоже приехал непойми зачем, уже все закончилось давно, у клуба его приняли сразу менты, приехавшие с опозданием на полчаса, нашли нож, ствол. все по сценарию. Снова его единственного забрали, как забирали уже много раз, просто потому что он оставался последним, кто думал о своем спасении. Вроде, он вообще об этом почти не думал никогда. Всегда битый, всегда первый раздавал и отхватывал. А как иначе? Он по другому не умел. Мать говорит: «Ему было четыре годика еще, а я все смотрела не него, и такая тоска и жалость дикая меня охватывала к этому мальчику, ни с того ни сего, нечеловеческая жалость к тем страданиям, которые ему предстоит испытывать всю свою жизнь». Он страдал всегда, до конца, и умер в мучениях. Убийцы не нанесли ему ни одного смертельного ранения, они просто изрезали все его тело, все лицо, спину, руки. Он все время был в сознании и кричал, просил вызвать скорую, катался по земле, пытаясь вытерпеть страшную боль, разрывавшую все его тело. Мать, сестра, собравшиеся вокруг него соседи со всего дома, ничем не могли ему помочь, пока он кричал и хватался из последних сил за свою жизнь. Скорая приехала через 35 минут, он был в сознании до конца, испытывая нечеловеческие страдания. Если есть ад, он испытал эти муки при жизни.

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

По наводке читателя.

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

По сигналу гномики одновременно выкрикивают цвета (синий или красный), пытаясь угадать цвет своей шапки.

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

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

Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar», перевод на русский здесь).

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

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

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

Аксиома выбора вообще замечательная, но эта головоломка с гномиками до сих пор на мой взгляд самый яркий пример ее применения (абсурдный конечно, как может показаться, но вполне себе занятный). Здесь был бы уместен рассказ и о других применениях аксиомы выбора, но его не будет, так как одного только подготовительного текста о лемме Цорна и базисе Гамеля будет довольно много, и он будет не слишком тривиален. Поэтому всех интересующихся отправляю за книжкой Верещагина и Шеня «Начала теории множеств». Она как раз во многом об этом, и понять ее сможет почти каждый, что важно.

Вот вам загадка: как можно разместить шар большего радиуса  в шаре меньшего радиуса?

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

Эту задачку выискал в «Элементарной топологии» Виро, Нецветаева, Иванова и Харламова. Задачка совершенно бесхитростная, но позабавила. Книжку кстати тоже рекомендую — она оказалась совсем для начинающих, но изложение хорошее, интересующимся математикой будет полезно почитать. Что примечательно — вполне подойдет даже для людей с минимальной подготовкой, хотя для них я бы начинал с «Наглядной топологии» Болтянского. А потом уже к этой переходил.

Вышел «Автоном» новый, 32-й номер, держу его сейчас в руках. Отпечатан насколько я знаю буквально несколько дней назад, раздавался позавчера на митинге, но к моменту, когда я туда пришел (из-за врожденного географического кретинизма я вначале перепутал место сбора), все журналы уже разобрали, поэтому свою копию получил только сегодня.

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

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

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

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

P.S. Жаль, что у меня заложен нос — наверняка зин офигенно пахнет типографией, с чего я всегда ловлю кайф, а в этот раз ничего не могу почувствовать. Обидно до жути.

Как-то раз сидели мы в вегетарианском кафе с одним молодым (на порядок моложе меня) и талантливым математиком. Обсуждали конечно же математику и секс (кстати, на написание статьи «Как пойти к простиутке» во многом сподвиг меня именно он в тот вечер). Один из вопросов, который обсуждался — это список тем и книг, с которыми должен быть знаком начинающий математик на базовом уровне. Под базовым уровнем считается четвертый курс математической специальности.

Поскольку я сам изучаю математику на 90% самостоятельно, я обратился к моему товарищу за советом: что изучать? что читать?  И он накидал мне список. Он попросил меня не упоминять его имени и фамилии в блоге, но список позволил опубликвать. По этому списку хочется заметить, что он ценен тем, что составлен действительно разбирающимся человеком, который понимает то что в этих книгах написано (часто списки составляются людьми невменяемыми). Так же очень ценно, что это довольно свежий взгяд молодого человека, а не старика-профессора, который математику воспринимает уже не так, как обычный студент. Так же нет ретроградства в виде рекомендаций учебников алгебры Гельфанда и Ван дер Вардена, которые может быть и хорошие книги, но уже давно появились гораздо более удачные учебники, о которых старшее поколение может просто не знать.

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

Алгебра

Базовый уровень:

Теория представлений:

Коммутативная алгебра:

Гомологическая алгебра:

Анализ

Базовый уровень:

Линейный Функциональный Анализ:

Более продвинутый анализ (эллиптические и дифференциальные операторы, расслоения и т.д., переход к языку пучков, C*-алгебры, KK-теория):

Алгебраический анализ:

Топология

Базовый уровень:

Алгебраическая топология:

K-теория:

Теория узлов:

Геометрия

Базовый уровень:

Комплексная геометрия:

Введение алгебраическую геомтерию:

Абелевы многообразия и теория тэта-функций

Дифференциальная геометрия

Симплектическая и пуассонова геометрии

Теория деформаций

Теория графов

Я потихоньку читаю (проглядываю) списки книг, которые вывесили в ЛЖР-сообществе НМУ, в том числе дабы ничего не упустить смотрю и в книги для совсем начинающих.

Ну там много таких книг, но особенно мне понравилась книга Алексеева «Теорема Абеля в задачах и решениях». Книга на мой взгляд просто изумительная. Излагаемый в книге материал я изучал по разным взрослым учебникам в течении долгого времени и давалось мне это честно сказать не особо просто. Главным образом из-за того, что я к теореме Абеля шел не напрямую и в гораздо более абстрактных терминах. А тут вдруг оказалось, что теорему Абеля вполне может осилить любой даже средний школьник. Книга действительно написана очень просто и понятно.

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

В комментариях к позапрошлой заметке мне посоветовали крутейшую книгу. А я теперь советую ее вам. Потому что действительно очень крутая.

UPD: Продолжаю чтение. Книга замечетальная, и очень хорошо объясняет укоренившиеся мифы, о которых я так настойчиво пишу, но мне не верят. Рекомендую в общем миллион раз.

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

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

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