Математика и секс
Декабрь 27th, 2011

Литература по Computer Science

Читатель 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: Эту заметку я все-таки не буду корректировать видимо. Лучше когда сам примерно буду иметь представление как правильно готовиться, сделаю отдельный удобный и адекватный обзор. Но пока все равно есть смысл дискутировать в комментариях.

29 комментариев »

  1. Как насчет стэнфордских курсов, которые с января запускаются? (список тут: http://jan2012.ml-class.org/#others)

    Comment by igor — 27.12.2011 @ 12:59
  2. @ igor:
    Да, эти курсы укажу и сам буду слушать. Но только они покрывают лишь малую часть, к сожалению.

    Comment by Хеллер — 27.12.2011 @ 13:47
  3. http://habrahabr.ru/blogs/programming/128280/

    Comment by hshhhhh — 27.12.2011 @ 13:59
  4. @ hshhhhh:
    Там как-то достойно выглядит только HTDP и список по алгоритмам. Остальное быдлокодинг, не имеющий отношения к CS.

    Comment by Хеллер — 27.12.2011 @ 16:08
  5. @ hshhhhh:
    ну не совсем быдлокодинг, конечно, но и не по теме программы GRE совершенно.

    Comment by Хеллер — 27.12.2011 @ 16:08
  6. Судя по скачанной пдф-ке, большая часть вопросов на структуры данных, алгоритмы и их эффективность вполне покрывается книжкой Кормена «Алгоритмы построение и анали»(Introduction to algorithms).

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

    Про всякие грамматики, регулярные выражения есть книжка Ахо «Теория синтаксического анализа, перевода и компиляции»

    Comment by Anon — 27.12.2011 @ 16:20
  7. Таненбаума и Кормена помянули совершенно правильно. По архитектуре — лично я скачал Daniel Page, A practical introduction into computer architecture. У того же Таненбаума тоже есть книга по архитектуре компьютера. Полезна будет еще Вики. Ну и очень хорошее, хотя и кратенькое, пособие — — Titanium Bits (http://sites.google.com/site/titaniumbits/).

    По грамматикам, рег. выражениям, машинам Тьюринга еще хорошая книжка — Хопкрофт, Мотвани, Ульман, Introduction to Automata Theory, Languages, and Computation.

    По компиляторам можно еще Dragon Book добавить, конечно, но компиляция все же не так много процентов в вопросах занимает.

    Насчет «вопросы простые» — не сказал бы, требуется все же неплохое понимание и поверхностное сканирование не шибко поможет.

    Comment by ende_neu — 27.12.2011 @ 16:29
  8. @ Anon:
    Ну то что они покрывают — это да. Только на чтение этих книг уйдет куча времени. По-хорошему все заявленные темы можно покрыть лекциями к трем-четырем семестровым курсам (не считая программирования и алгоритмов — но это мелочь в общем-то). Читать двухтомник (вроде) Ахо для того, чтобы сдать тест, где требуется всего-то context-free и regular grammar — ну как-то перебор. То есть с Advanced-секциями все в общем-то понятно куда копать, а вот как быть для получение общего образования — не вполне понятно.

    Comment by Хеллер — 27.12.2011 @ 16:35
  9. В принципе, я сам сейчас по этим книжкам к GRE и готовлюсь, самое слабое место — архитектура компьютера, там надо к Пейджу еще что-нибудь добавить. Планирую сдавать в апреле. Ощутил неприятный шок, когда осознал, как мало я знаю о том, что происходит внутри машины и вообще про программирование.

    Если собираетесь сдавать и ограничены по времени — можете, я думаю, забить на все второстепенное (там примерная процентовка дана — 40 % одного, 40 процентов другого, а ве прочее — в минимальных количествах). С математикой (комбинаторика, теор. вер. и т.п.) у вас же и так все в порядке, по чис. методам особо ничего не надо (сейчас даже матричную алгебру практически не спрашивают, не говоря уж о реальных численных методах). Алгоритмика, ОС и около них (многопоточность, блокировки), архитектура компьютера, особенно процессора, теория вычислений (рег. языки, конечные автоматы, автоматы с магазинной памятью и все такое) —- вот основные темы, которые надо копать максимально глубоко. Так мне кажется.

    Comment by ende_neu — 27.12.2011 @ 16:40
  10. Хеллер написал:

    @ Anon:
    Читать двухтомник (вроде) Ахо для того, чтобы сдать тест, где требуется всего-то context-free и regular grammar – ну как-то перебор.

    Конкретно Хопкрофт, Мотвани, Ульман, во-первых, читается все же легко и быстро, несмотря на объем (около 600 стр), во-вторых, содержит массу полезных задач и примеров. Ведь гнусность GRE в том, что вы ограничены временем, и надо не просто в принципе знать, что есть такая фигня как КС-грамматика, а быстро отвечать на конкретные вопросы про нее. Для этого предварительная тренировка в быстром решении задач не помешает. Ну, то, что с реальными знаниями и умом это может никак не коррелировать — это само собой.

    Comment by ende_neu — 27.12.2011 @ 16:49
  11. @ ende_neu:
    Да, я думаю, что вы правы. Видимо сам я буду в итоге сдавать GRE не в апреле, а следующий. На апрель оставлю математику, посмотрю вообще что за экзамен такой (за математику я как-то спокойнее, напрягает экзамен лишь отсутствие времени на размышления), а потом уже буду сдавать CS. До апреля не уверен просто, что осилю материал по CS.

    Comment by Хеллер — 27.12.2011 @ 17:06
  12. Подобный список (сильно расширенный) уже есть: http://sharpc.livejournal.com/67583.html#comments

    Про алгоритмы, кстати, много книжек, но они все одинаковые. Я могу с уверенностью сказать, что Кормен & Co покрывает их всех процентов на девяносто. Как следствие, достаточно прочитать только его.

    Все, что следует знать про автоматы, регулярные и context-free грамматики, вычислимость, разрешимость и сложность есть в небольшой книжке Michael Sipser’а «Introduction to the Theory of Computation».

    Операционные системы, (virtual) memory management, вопросы синхронизации в multithreading’е есть в достаточно толстом кирпиче Abraham Silberschatz, «Operating System Concepts».

    Pipelining, instruction level parallelism, регистры и прочая архитектура есть в любой книжке по ассемблеру. Лично я читал Kip R. Irvine, «Assembly Language for Intel-based Computers», но наверняка есть и лучше.

    Сети это Таненбаум, конечно.

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

    Вся математика из списка есть в аппендиксе страниц на 30 в конце Кормена.

    Comment by measure_0 — 27.12.2011 @ 17:09
  13. @ Хеллер:
    Математику тебе надо сдавать только если ты хочешь именно в математическую аспирантуру. На CS этого не требуют.

    Comment by measure_0 — 27.12.2011 @ 17:10
  14. @ measure_0:
    Слушай, а я вот не понимаю тогда почему ты сам пошел на CS? Просто вот смотрю я на эти тесты, и для CS мне сейчас надо учиться и учиться (причем темы все ненужные, если работать в том же Artificial Intelligence например). Для математики я готов сдавать экзамен хоть сейчас, причем скорее всего балл будет довольно высок — задачи там действительно элементарные довольно. Я уверен, что у тебя была примерно та же ситуация, особенно учитывая, что твой уровень по математике гораздо выше моего. Да и интерес ты питаешь главным образом в математике. Что тебя подвигло CS выбирать?

    Тест по математике наверное все же сдам — это будет не плохим дополнением в любом случае. Особенно учитывая, что мне к нему готовиться не надо, мне вообще это почти ничего не стоит (стоимость самого теста как я понимаю невысока).

    Comment by Хеллер — 27.12.2011 @ 17:17
  15. Дело не в тесте, а в других требованиях.

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

    Во-вторых, у меня нет математического бэкграунда и, как следствие, рекомендаций от математиков.

    Comment by measure_0 — 27.12.2011 @ 17:25
  16. @ measure_0:
    Хотя в принципе у меня я думаю довольно не плохое начало есть в плане именно CS — я разработал язык описания торговых систем и финансовых индикторов и систему тестирования биржевых стратегий. Они довольно херовые, но тем не менее. Ну и на рынке кстати используются и востребованы. Единственное что меня напрягает, в области компиляторов я бы не хотел работать — это довольно гнилое болото, скучное и бесперспективное, с большой конкуренцией. Если только заняться в будущем Natural Language Processing, но тоже не уверен, что есть перспективы у этого направления (если мыслить о нем как о грамматиках или статистических моделях, что единственное что хоть как-то с компиляторами пересекается).

    Comment by Хеллер — 27.12.2011 @ 17:25
  17. @ Хеллер:
    Natural language processing хорошая и востребованная область. Я как раз этим и хочу заниматься. Но не знаю как это с компиляторами пересекается.

    Comment by measure_0 — 27.12.2011 @ 17:29
  18. measure_0 написал:

    @ Хеллер:
    Математику тебе надо сдавать только если ты хочешь именно в математическую аспирантуру. На CS этого не требуют.

    А на CS, если диплом по специальности, требуют соотв. GRE subject test? Я могу только про магистратуру Германию сказать — там в подавляющем большинстве мест смотрят на содержимое курсов бакалавриата и сравнивают с курсом бакалавриата по CS. Редко где принимают людей с другим образованием и от них как раз и просят GRE CS. Мне он поэтому нужен.
    На американском форуме каком-то я тоже читал, что от нормальных поступающих, не меняющих специальность, тоже этого экзамена никто не ждет в приличных местах — смотреть будут на диплом и рек. письма. То есть там это тоже скорее для меняющих специальность, кажется.
    А уж чтобы с математическим образованием при поступлении в мат. магистратуру/аспирантуру нужен был subject test, — про это я вообще не слышал ни разу. Зато один товарищ сдавал этот тест для поступления в РЭШ на экономику.

    Comment by ende_neu — 27.12.2011 @ 17:34
  19. @ measure_0:
    Ну оно пересекается только в месте как раз разбора грамматик и Abstract Syntax Trees. Вроде системы машинного перевода даже на полном серьезе их используют. Пересечение конечно очень маленькое и ненаучное, но это хоть что-то что можно упомянуть при написании письма. То есть хоть как-то мою прошлую деятельность с AI увязывает.

    Comment by Хеллер — 27.12.2011 @ 17:42
  20. @ measure_0:
    С другой стороны может быть воспринято как притягивание за уши конечно.

    Comment by Хеллер — 27.12.2011 @ 17:42
  21. @ ende_neu:
    В американских университетах вроде требуют. По-крайней мере, все кого я знаю сдавали.

    @ Хеллер:
    Нормально, написать об этом стоит, конечно. Кстати, еще иногда могут попросить thesis extract. У меня при подаче в Imperial College, например, спрашиваль экстракт из магистерской диссертации.

    Comment by measure_0 — 27.12.2011 @ 17:54
  22. Про Таненбаума и Кормена уже написали, по архитектуре есть ещё «Computer Systems. A Programmer’s Perspective». Но! Если посмотреть вопросы, то становится ясно, что они не покрывают и 5% из этих книг. Ну то есть, книжки все эти очень клёвые и интересные, и прочитать их надо обязательно, но для сдачи теста будет достаточно пару месяцев полистать английскую википедию.

    measure_0 написал:

    Natural language processing хорошая и востребованная область. Я как раз этим и хочу заниматься.

    Рекомендую посмотреть в сторону иероглифических языков — перспективнее некуда. Хотя лично мне вся эта область не особо интересна, не знаю, что вас там так привлекает. Особенно, если компиляторы котировать как «гнилое болото».

    Comment by Anonymous — 27.12.2011 @ 20:41
  23. @ Anonymous:
    Ну меня NLP интересует в контексте information retrieval systems и генерации синтетических текстов. То есть, например, работы Лавренко про natural language profile model.

    Comment by measure_0 — 27.12.2011 @ 21:18
  24. @ Anonymous:
    «Гнилое болото» я имел ввиду не про перспективность, а про то что это сложная область, в которой сложно сделать что-то новое, и сам процесс разработки компилятора доставляет мало удовольствия. Внести что-то существенно новое почти невозможно, а разработка чего-то специально под какую-то малую нужду (какое-нибудь моделирование или финансовые индикаторы например) — процесс малоприятный, нудный и почти не интеллектуальный.

    Comment by Хеллер — 27.12.2011 @ 21:32
  25. Кстати, я никак не могу разобраться и найти информации. GRE subject test — это только письменный тест, или там есть еще что-то дополнительное? Везде где они пишут о тесте, они акцентируют внимание на «paper-based test», а собственно за сам бумажный тест судя по тестовому примеру они ставят scaled оценку от 390 до 900, хотя заявленный допустимый разброс от 220 до 990. Нет ли там каких-то дополнительных к тесту секций? Интуиция подсказывает, что могут такие быть, но я не особо смог найти информации.

    Еще такой момент: судя по всему все subject тесты проходят в один день? То есть получается, что в апреле я сдаю либо математику либо CS и никак не получится сдать и то и другое одновременно?

    Comment by Хеллер — 28.12.2011 @ 11:36
  26. Привет! Роман, а эта «Computer Science» тебе интересна в связи с некоторой её близостью с математикой или для заработка денег? Просто если для денег, то мне кажется проще (и IMHO практичнее) выучить какой-нибудь широко сейчас используемый язык программирования (Java/C#/PHP), основы СУБД (+ SQL) и что-нибудь по WEB (HTML, JavaScript) и получается востребованный СЕЙЧАС разработчик, востребованный как у нас в России, так и насколько я знаю, зарубежом.. Ато путь к хорошей зарплате через «Computer Science» мне почему-то кажется ОЧЕНЬ тяжелым и небыстрым..

    Comment by Михаил — 28.12.2011 @ 13:17
  27. Кстати, где можно нормально почитать об образовании на Западе, требованиях к поступлению, оплате? Есть какие-нибудь специальные ресурсы по этой теме? То при поверхностном гуглении один бред пока попадается.

    Comment by Вадим — 28.12.2011 @ 13:49
  28. Ром, а как ты относишься к школе анализа данных?
    http://shad.yandex.ru/
    Там вроде есть отделение cs и по окончанию дают диплом…

    Comment by tkoh — 28.12.2011 @ 17:04
  29. Хеллер написал:

    Еще такой момент: судя по всему все subject тесты проходят в один день? То есть получается, что в апреле я сдаю либо математику либо CS и никак не получится сдать и то и другое одновременно?

    Это именно так.

    Насчет же каких-то доп. секций — не знаю, не слышал ни разу.

    Comment by ende_neu — 28.12.2011 @ 20:41

RSS feed for comments on this post. TrackBack URI

Оставить комментарий

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline