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

Для того, чтобы сделать обучение более веселым и интересным, представляю вам перечень важных теорий и концепций в информатики, объяснённых с помощью аналогий с минимальным количеством технических деталей. Это будет похоже на очень быстрый курс информатики для всех с целью просто дать вам общее представление об основных концепциях.

Важные замечания:

• Пункты с неуказанным источником написаны мной самостоятельно. Поправьте меня, если вы заметите какие-то неточности. Предложите лучшую аналогию, если это возможно.
• Заголовки ссылаются на соответствующие им статьи в Wikipedia. Пожалуйста, читайте эти статьи для более серьезных и детальных объяснений.
• Аналогии — отличный способ объяснить материал, но они не идеальны. Если вы хотите по-настоящему понять перечисленные концепции, вам следует начать с фундаментальных азов и рассуждать, исходя из них.

Также зацените эту инфографику (вариант на русском), если вы просто начинающий программист.

Ключевые концепции #1 — Алгоритмы и структуры данных

1.1 Нотация “О-большое” (на русском)

Допустим вы заказываете полную коллекцию серии фильмов о Гарри Поттере из 8 частей на Amazon и скачиваете ту же самую коллекцию в то же время. Вы хотите проверить, какой метод быстрее. Магазин доставил коллекцию почти через день, а скачивание завершилось всего на 30 минут раньше этого. Класс! Это была близкая гонка.
Но что если я закажу несколько Blu-ray фильмов, например Властелин Колец, Сумерки, трилогию о Тёмном Рыцаре и тому подобное, и в то же время буду пытаться скачать все эти фильмы? Доставка всё равно займёт день, но скачивание в сети продлится на этот раз 3 дня.
При покупках в интернете количество покуппаемых вещей (входные данные) никак не влияет на время, за которое они будут доставлены. Выходные данные константны. Мы называем это О(1).
Но при скачивании в сети время скачивания прямо пропорционально размеру скачиваемых фильмов (входные данные). Мы называем это O(n). Из этих экспериментов мы понимаем, что покупки в интернете лучше масштабируются, чем загрузка файлов из сети. Очень важно понимать “О-большое”-нотацию, так как это поможет вам анализировать эффективность и масштабируемость алгоритмов.
Замечание: нотация “О-большое” служит для оценки эффективности в худшем случае для алгоритма. Давайте согласимся, что О(1) и О(n) — худшие сценарии для приведённого примера.
Больше информации: Big O Notations (video), Plain English explanation of Big O, A Beginner’s Guide to Big O Notation

1.2 Алгоритмы сортировки (на русском)

Больше информации: Sorting Algorithm Animations, Beautiful and configurable visualizations of sorting algorithm

1.3 Рекурсия (на русском)

Кто-то в кино спрашивает вас, на каком ряду вы сидите. Вы слишком ленивы, чтобы посчитать, так что вы спрашиваете человека, сидящего перед вами. Вы просто будете должны добавить 1 к его ответу, чтобы получить номер своего ряда. Отличная идея, не так ли? Однако, человек перед вами сделал то же самое, и так дальше. В конце концов вопрос доберётся до первого ряда и человек на первом ряду ответит “Я в ряду номер 1!”. С этого момента правильное сообщение (увеличиваемое на 1 за каждый ряд) пройдёт весь свой путь обратно к тому, что изначально спросил.

Aaron Krolik/Quora

Есть ещё один пример, известный как эффект Дросте (на русском).
Медсестра несет поднос с пачкой какао и чашкой, на которой нарисовано уменьшенное изображение её, держащей всё то же самое, которое в свою очередь содержит ещё более маленькое изображение той же картинки, и так далее.
Тут вы можете найти ещё больше примеров эффекта Дросте, если хотите, чтобы вам стало сонливо.



Если вы ещё не до конца поняли рекурсию, попробуйте посмотреть тут… Ну а если поняли — продолжайте читать.

1.4 Big Data (на русском)

Давайте представим, что у вас течет труба в саду. Вы берете ведро и немного уплотнителя, чтобы починить её. Через некоторое время вы видите, что течь стало ещё больше и вам уже нужен водопроводчик с нормальными инструментами. В то же время, вы всё ещё используете ведро, чтобы как-то справляться с водой. Ещё через какое-то время вы замечаете, что открылся огромный подземный поток. Вам уже нужно как-то справляться с галлонами воды в секунду!
Вёдра больше не помогут. Вам нужен совершенно новый подход для решения проблеммы, так как количество и скорость поступления воды увеличилась. Чтобы предотвратить город от наводнения, вам может понадобится помощь правительства, чтобы построить дамбу, что требует огромного количества инженерных знаний и тщательно проработанной системы контроля.

Balaji Viswanathan/Quora

Термин “большие данные” описывает наборы данных на столько большие и сложные, что с ними невозможно работать с помощью обычных инструментов обработки данных.
Больше информации: Big Data by TED-Ed (video), What is Big Data and Hadoop (video)

1.5 Структуры данных (на русском)

Каждый специалист в области информатики и программист должен знать как минимум следующие структуры данных:

• Массив (на русском)
• Дерево (на русском)
• Стек (на русском)
• Очередь (на русском)
• Граф (на русском)
• Хеш-таблица (на русском)
• Связный список (на русском)
• Куча (на русском)

Ключевые концепции #2 — Искуственный интеллект

2.1 Жадный алгоритм (на русском)

Представьте, что вы решили прогуляться, и ваша цель — добраться до самого высокого места. У вас есть карта, но на карте тысячи возможных путей. Вы слишком ленивы и у вас просто нет времени, чтобы попробовать кажный из них. Так что к черту карту! Вы просто идете вперёд с простой стратегией — быть жадным и близоруким. Вы просто выбирете пути, которые как можно более наклонены вверх.
После того, как ваше путешествие завершилось и ваше тело стало измученным и уставшим, вы посмотрели на карту местности впервые. О боже мой! Вот грязная речка, через которую я должен был переправиться вместо того, чтобы идти вверх!
Жадный алгоритм делает лучший выбор в текущий момент времени и никогда не пересматривает своих решений.

2.2 Восхождение к вершине (на русском)

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

2.3 Алгоритм имитации отжига (на русском)

Это — гора Эверест, самый крупный вызов, с которым вы сталкивались. Ваша задача — добраться до вершины, но это очень непрактично забираться на Эверест по многу раз. У вас есть только один шанс. И вы стали куда более предусмотрительнее, чем раньше. Вместо того, чтобы всегда взбираться наверх, вы изредка двигаетесь вниз и находите новые пути, чтобы уменьшить риск пойти по неправильному пути. Чем выше вы забираетесь, тем меньше вероятность того, что вы пойдёте вниз.

2.4 Динамическое программирование (на русском)

Отец: *Пишет “1+1+1+1+1+1+1+1 =” на куске бумаги*
Отец: Чему это равно?
Ребенок: *Считает и тремя секундами спустя* Восемь!
Отец: *Дописывает ещё “+1”*
Отец: А теперь?
Ребенок: *Сразу же* Девять!
Отец: Ого, как ты посчитал так быстро?
Ребенок: Ты просто добавил ещё один!
Отец: Ты понял, что тебе не нужно пересчитывать, потому что ты запомнил, что это было восемь до этого. Отлично!

Jonathan Paulson / Quora

Пример выше описывает мемоизацию (на русском) (да, мемоизация — это не запоминание), подход к динамическому программированию сверху вниз, при котором результаты предыдущих рассчетов сохраняются для дальнейшего использования.
Больше информации: Dynamic Programming – From Novice to Advanced (TopCoder), Tutorial for Dynamic Programming (CodeChef)

2.5 Машинное обучение (на русском)

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

2.6 Равенство классов P и NP (на русском)

Равенство классов P и NP задач — одна из наиболее популярных и важных неразрешенных проблем в информатике.
Допустим, у нас есть следующая задача:
Задача1: 7 x 17 = p
Ответ — 119.
Это было легко, не так ли? Но что если у нас противоположная задача:
Задача2: p x q = 119 (p и q не могут быть 1 и 119)
Для того, чтобы решить вторую задачу, предполагая, что вы не видели первую, вам нужно пройтись по всем возможным числам от 2 до 118. Существует хороший алгоритм, позволяющий просто раскладывать числа на множетели (на русском).
Что если я спрошу: может ли p быть 7? Вы сможете очень просто ответить, просто разделив 119 на 7.
Умножение — это просто. Разложение на множители числа — сложно.
В итоге, задача 1 — P (полиномиальная), так как её просто решить. Компьютер отлично справляется с умножением двух огромных чисел, не тратя существенно больше времени, чем умножая два небольших числа.
Задача 2 — это NP (недетерминированная полиномиальная), потому что её легко проверить, но сложно решить. Разложение на множители числа 119 — все ещё не очень сложная задача для компьютера, но что на счёт числа, состоящего из 500 знаков? Это невозможно ни для одного компьютера в наши дни.
И тут начинается важная часть: являются ли NP-задачи (например, разложение на множители) также и P-задачами (как умножение), а мы просто ещё не обнаружили эффективного способа решения NP-задач? Действительно ли NP-зачадачи сложны или нам просто нужен момент просветления какого-нибудь хорошего ученого (может быть вас?), который придумает эффективный алгоритм? Или может быть люди слишком глупы? Представьте, что существует машина или жизнь, обладающая куда большим интелектом, чем человек. Мы для них, как муравьи для нас. Наш уровень интеллекта для них совершенно несущественен. Решение данной проблемы для них как 1+1.
Так или иначе, почему же задача равенства классов P и NP задач так важна? Если мы сможем доказать, что P=NP, это означает, что все NP-задачи могут быть решены за разумое компьютерное время. Мы сможем вылечить рак (укладка белка, на русском), взламывать пароли (RSA, на русском) и тому подобное. Это изменит мир.
Проблема равенства классов P- и NP-полных задач является одной из семи в списке проблем тысячелетия от математического института Клэя. Награой за первое верное решние является $1 000 000.
Больше информации: P vs. NP and the Computational Complexity Zoo (video), Simple Wikipedia

Ключевые концепции #3 — Архитектура компьютера и инженерия

3.1 Как работают компьютеры

Компьютеры работают, добавляя сложность поверх сложности (Computers work by adding complexity on top of complexity). Для того, чтобы вести машину, не обязательно понимать, как работает её двигатель. Сложные детали скрыты.
Так как же компьютер превращают бинарный код, нолики и единички в программы? Вот превосходное видео, в котором с помощью домино визуализируется, как компьютеры осуществляют бинарные вычисления на самом базовом, фундаментальном уровне:


Больше информации: Interactive explanation on how computer works

3.2 Проблема остановки (на русском)

Больше информации: The Freeze App Analogy, Simple Wikipedia

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

Ключевые концепции #4 — Параллелизм (на русском)

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

Параллелизм (параллельное выполнение) — это свойство программ и систем, которое позволяет задачам выполняться в перекрывающихся периодах времени.

4.1 Параллельные вычисления (на русском)

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

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

Однако, реализация концепций параллельного выполнения так же приносят и многие потенциальные проблемы, такие как состояние гонки.

4.2 Состояние гонки (на русском)

Вот, что произойдет, если вы допустите выполнение параллельных транзакций в системе банкинга, а состояние гонки не будет обрабатываться: