Теоретические информатические ресурсы для самостоятельной работы программистов

14

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

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

soft-question teaching books Генри Х.
источник
3
Это зависит от того, что вы хотите узнать. Арора-Барак дает подробное введение в теорию вычислительной сложности (и свободно доступно онлайн). Так что это хорошее место для начала.
Томас поддерживает Монику
4
Вы посещали теоретические курсы в колледже / университете, такие как структуры данных, алгоритмы и т. Д.? Если вы обычно не проходили обязательные курсы по бакалавриату, то учебники для этих курсов были бы хорошей отправной точкой. После этого вы можете просмотреть статьи в Википедии, наш список книг и список видео , онлайн-курсы в Coursera / Udacity / EdX / ... Coursera предлагает довольно хорошие теоретические курсы.
Каве
Что ты учила в колледже?
Омар Шехаб
На каких языках вы программируете? Большая часть теоретического CS может быть изучена в тандеме с чем-то конкретным. Например, если вы хотите больше узнать о формальных языках, регулярные языки / выражения (например, регулярные выражения) - это хорошее место для начала, как и изучение для компиляторов. Для теории типов вы можете поиграть со статически типизированным языком, таким как haskell, F # или ML.
Малыш Дракон
попробуйте New Turing Omnibus от Dewdney в качестве широкой / доступной вступительной справки / обзора / сечения. см. также поп-научные книги, которые вдохновляют TCS
vzn

Ответы:

7

Это широкое поле с несколькими совершенно разными областями.

Я бы начал с некоторых из самых фундаментальных идей о том, что такое компьютеры: Хопкрофт и Уллман, «Введение в теорию автоматов, языков и вычислений».

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

Кейт Ф
источник
1
Благодарность! Я не знаю, изменит ли это что-нибудь, но у меня действительно есть некоторый опыт в доказательной математике (я, вероятно, должен был упомянуть об этом в вопросе). Я провел реальный анализ, основанный на доказательствах, топологию множеств точек и абстрактную алгебру.
Генри Х.
Тогда ты сможешь пройти через это очень быстро :)
Kate F
его разница , но не разница. CS влечет за собой множество других принципов и т. Д.
vzn
Я не думаю, что потребность в строгости - это разница между программированием и математикой. Теоремы о программировании и доказательстве являются их очень близкими задачами (см. Изоморфизм Карри-Ховарда), и вряд ли любая нематематическая задача требует большей строгости, чем программирование. Компиляторы гораздо меньше прощают ошибок, чем люди, которые читают доказательства.
Ян Йоханнсен
2
@JanJohannsen Я бы совершенно не согласился - например, см. Неопределенное поведение для C.
Кейт Ф
9

Есть несколько способов узнать о теории типов. Для работающего программиста « Типы и языки программирования » Б. Пирса - хорошее начало. Практические основы языков программирования Р. Харпера также могут быть хорошими. Если вы хотите немного легкого для понимания фона по операционной семантике, я рекомендую книгу Г. Винскеля « Формальная семантика языков программирования: введение» . С Т. Нипковым, Г. Кляйном, Конкретная семантикавариант книги Винскеля был оформлен для интерактивного помощника Изабель / HOL. Я подозреваю, что действительно трудно справиться с прувером только из этой (или любой) книги, вы бы хотели, чтобы эксперт поблизости задавал вопросы. Если вам нужен более математический подход к теории типов, вы можете взглянуть на JR Hindley, JP Seldin, Lambda-Calculus and Combinators: Введение , или H. Barendregt, Lambda Calculi with Types . Хотя я бы не рекомендовал начинать с Барендрегта.

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

Мартин Бергер
источник
2

Я рекомендую вычислимость, сложность и языки Мартина Дэвиса, Рона Сигала и Элейн Вейукер.

valepert
источник
Это красивая книга для старой школы TCS. За исключением части теоретической семантики области, которая может быть пропущена.
Мартин Бергер
1

Я большой поклонник теории и алгоритмов. Однажды у меня была возможность посетить Теоретическую информатику в Индийском технологическом институте, Мадрас (ИИТ-М), Индия. Я узнал о многих теоретиках в ИИТ-М. Когда я пришел туда, я понятия не имел, что такое Теория, но сегодня я полностью влюблен в нее.

Спасибо @Kate F за указатель, да, Hopcroft и Ullman - отличное место для старта.

Однако вот как я начал,

  1. Прочтите Введение в алгоритмы от Кормена. <\ Br> Это отличное место для начала. Когда вы учитесь, постарайтесь понять каждое доказательство как можно более подробно. Если вы хорошо понимаете доказательство, попробуйте написать ту же логику на любом языке по вашему выбору. (Это займет немного больше времени, но стоит попробовать)

  2. Следуйте за главными конференциями в Теории как
    FOCS
    SODA
    STOC
    EC (Электронная коммерция) - Алгоритмическая теория игр
    COLT (Конференция по теории обучения) - Теория обучения
    CRYPTO - Криптография
    SOCG (Симпозиум по вычислительной геометрии) - Вычислительная геометрия
    CCC (Конференция по Вычислительная сложность) - Теория сложности

Даже если вы плохо понимаете, старайтесь читать и ДУМАТЬ как можно больше. Вы должны сделать как можно больше доказательств ..

  1. Это удивительное место, на которое стоит обратить внимание, если вы думаете о сложности вычислений, в частности ( это из Стэнфорда ).
  2. Следуйте за профессором Санджив Арора, Боаз Барак, Джелани Нельсон, Мадху Судан
  3. Вот набор синтезированной информации в области вычислительной сложности
Jaugust
источник