Теоретический минимум по Computer Science [заметки]
1
Рисунок использован с согласия http://xkcd.com.
2
См., например, http://code.energy/coding-courses.
3
Адаптация схемы с сайта http://wikipedia.org.
4
См., например, http://code.energy/coding-courses.
5
Здесь
6
Любезно предоставлено http://ctp200.com.
7
Любезно предоставлено http://programmers.life.
8
В нечеткой логике значения могут быть промежуточными, но в этой книге она рассматриваться не будет.
9
И, между прочим
10
Названа так в честь Джорджа Буля (1815–1864). Его публикации положили начало математической логике.
11
Огастес де Морган дружил с Джорджем Булем. Кроме того, он обучал молодую Аду Лавлейс, ставшую первым программистом за век до того, как был создан первый компьютер.
12
Например, таблица истинности для 30 переменных будет иметь более миллиарда строк
14
True = 1, False = 0. Если вы не знаете, почему 101 — это 5 в двоичной системе счисления, загляните в приложение I.
15
В 2016 году был создан действующий транзистор с размером 1 нм. Для справки: атом золота имеет размер 0,15 нм.
16
Комбинаторика и логика относятся к одной из важнейших областей информатики, которая называется дискретной математикой.
17
По определению 0! = 1. Мы говорим, что ноль элементов, то есть пустое множество, можно упорядочить единственным способом.
18
В литературе принято обозначение
19
Профессиональная подсказка: поищите в Интернете по запросу «из 64 по 8», чтобы узнать результат.
20
Любезно предоставлено http://xkcd.com.
21
22
Любезно предоставлено http://xkcd.com.
23
Чтобы разобраться в алгоритме, выполните его на бумаге с небольшим объемом входящих данных.
24
25
Читаются такие конструкции следующим образом: «алгоритм сортировки имеет временную сложность o-n-квадрат».
26
По поводу сложностей большого «О» большинства алгоритмов, которые выполняют типовые задачи, смотрите http://code.energy/bigo.
27
Было доказано, что неэкспоненциальный алгоритм для любой NP-полной задачи может быть обобщен для всех NP-полных задач. Поскольку мы не знаем, существует ли такой алгоритм, вы также получите миллион долларов, если докажете, что NP-полная задача не может быть решена с использованием неэкспоненциальных алгоритмов.
28
Объем входных данных (так называемый размер входа) — это число элементов в обоих входных списках, взятых вместе. Цикл while выполняет три операции для каждого из этих элементов, следовательно, T(n) = 3n.
29
Если вам нужно больше узнать о множествах, см. приложение III.
30
Палиндромы — это слова и фразы, которые читаются одинаково в обе стороны, например «Ада», «топот», «ротатор».
31
Любезно предоставлено http://geek-and-poke.com.
32
В интервале n дней имеется n(n + 1)/2 пар дней (см. раздел «Комбинаторика» главы 1).
33
Подробнее о степенных множествах см. в приложении III.
34
Задача о рюкзаке является частью класса NP-полных задач, который мы обсудили в разделе 2.3. Вне зависимости от стратегии ее решают только экспоненциальные алгоритмы.
35
Задача коммивояжера относится к классу NP-полных задач, который мы обсудили в разделе «Экспоненциальное время» (см. главу 2). Пока не удалось найти оптимальное решение, которое было бы лучше экспоненциального алгоритма.
36
Любезно предоставлено http://xkcd.com.
37
Это самый первый алгоритм, который вы увидели в главе 3.
38
Операции, которые выполняются рекурсивными вызовами, подсчитываются на следующем шаге разбиения.
39
Мы не можем проигнорировать x, потому что это не константа. Если размер списка n удвоится, то нам потребуется еще один шаг разбиения. Если n увеличится в четыре раза, тогда нужны будут два дополнительных шага разбиения.
40
Любой процесс, постепенно сокращающий объем входных данных на каждом шаге, деля его на постоянный делитель, требует логарифмического количества шагов до полного сокращения входных данных.
41
В таком случае говорят, что задачи имеют перекрывающиеся подзадачи.
42
Вам нужно найти самого высокого мужчину, самую высокую женщину и самого высокого человека в комнате. Будете ли вы измерять рост каждого присутствующего с целью найти самого высокого человека, а затем делать это еще и еще раз применительно к женщинам и мужчинам по отдельности?
43
Метод удаления ограничений из задач называется ослаблением. Он часто используется для вычисления ограничений в задачах оптимизации.
44
Модуль, или библиотека, — это структурная часть программного обеспечения, которая предлагает универсальные вычислительные процедуры. Их можно включать при необходимости в другие части программного обеспечения.
45
Они сопряжены с разрешением доменного имени, созданием сетевого сокета, установлением шифрованного SSL-соединения и многим другим.
46
Числа с плавающей точкой — это общепринятый способ представления чисел, имеющих десятичный разделитель.
В англоязычных странах в качестве десятичного разделителя используется точка, в большинстве остальных — запятая. — Примеч. пер.
47
Если узел нарушает это правило, многие алгоритмы поиска по дереву не будут работать.
48
Иногда их называют двоичными деревьями с автоматической балансировкой, или самоуравновешивающимися двоичными деревьями. — Примеч. пер.
49
Стратегии автоматической балансировки выходят за рамки этой книги. Если вам любопытно, то в Интернете имеются видеоматериалы, которые показывают, как работают эти алгоритмы.
50
Двоичная куча min-heap характерна тем, что значение в любой ее вершине не больше, чем значения ее потомков; в двоичной куче max-heap, наоборот, значение в любой вершине не меньше, чем значения ее потомков. — Примеч. пер.
51
Ситуация, когда найдена новая, неисследованная задача, — это редкость. Когда исследователи находят новую задачу, они пишут об этом научную работу.
52
Вот более полный список: https://code.energy/algo-list.
53
Любезно предоставлено http://xkcd.com.
54
Задача раскраски графа на сайте онлайновых экспертов UVA: https://code.energy/uva-graph-coloring.
55
Формально полиномов 1-й степени. Они не имеют квадратов (впрочем, и любых других степеней), а их переменные могут умножаться лишь на константы.
56
Читается как «А-звезда» или «А-стар». — Примеч. ред.
57
Премия Тьюринга — самая престижная премия в области информатики. Ее премиальный фонд составляет один миллион долларов.
58
В английском языке аббревиатура SQL чаще произносится, как «сиквел», а устная форма «эс-кью-эл» не считается неправильной.
59
Существует несколько способов выполнить операцию JOIN — см. https://code.energy/joins.
60
Атомарные операции выполняются одноэтапно: они не могут быть выполнены наполовину.
61
Любезно предоставлено http://geek-and-poke.com.
62
В профессиональных кругах это называется «три V»: volume (объем), velocity (скорость) и variety (разнообразие). Некоторые добавляют еще два аспекта: variability (переменчивость) и veracity (достоверность), превращая термин в «пять V».
63
Большой адронный коллайдер, или БАК, — это самый большой ускоритель частиц в мире. Во время эксперимента его датчики генерируют 1000 терабайт данных в секунду.
64
Антенная решетка площадью в квадратный километр, или SKA (от англ. Square Kilometer Array), — это группа телескопов, которые планируется ввести в строй в 2020 году. Они будут генерировать 1 млн терабайт данных каждый день.
65
Сразу после финального матча на чемпионате мира 2014 года по футболу Twitter испытал пиковую нагрузку в более чем 10 000 твитов в секунду.
66
По данным https://census.gov.
67
Оперативное запоминающее устройство (англ. RAM, random access memory). Более точное наименование на русском — запоминающее устройство (память) с произвольным доступом, сокращенно ЗУПД (ППД).
68
Центральный процессор (англ. CPU, central processing unit).
69
Двоичные числа выражены в системе счисления с основанием 2. Приложение I объясняет, как это следует понимать.
70
Программный код даже может изменять сам себя за счет включения команд, которые переписывают части собственного кода в ОЗУ. Нередко компьютерные вирусы поступают именно так, чтобы затруднить их обнаружение антивирусным ПО. Здесь можно провести удивительную параллель с биологическими вирусами, изменяющими свои ДНК, чтобы спрятаться от иммунной системы носителей.
71
Не путайте эту аббревиатуру с общепринятым акронимом для Personal Computer (PC) — «персональный компьютер».
72
Во многих персональных компьютерах эта программа называется BIOS (англ. basic input/output system, «базовая система ввода-вывода»).
73
О процессоре с 1000 ядер исследователи объявили еще в 2016 году.
74
Дисковая операционная система (Disk Operating System). Об операционных системах мы вскоре расскажем подробнее.
75
О языках программирования подробнее будет рассказано в следующей главе.
76
Можете взглянуть на компилятор, который превращает любой код на C в двоичный код лишь с одной машинной командой MOV: https://code.energy/mov.
77
Любезно предоставлено http://geek-and-poke.com.
78
Любезно предоставлено http://xkcd.com.
79
По крайней мере, на данный момент. С развитием искусственного интеллекта это когда-нибудь окажется возможным.
80
В ЦП с таковой частотой 1 ГГц один цикл длится порядка одной миллиардной секунды — время, которое необходимо, чтобы свет прошел расстояние от страницы этой книги до ваших глаз.
81
Нужно где-то 10 микросекунд, чтобы звуковые волны вашего голоса достигли человека, который стоит перед вами.
82
Стандартная фотографическая съемка фиксирует свет в течение примерно четырех миллисекунд.
83
Не верите? Тогда ближе к вечеру пятницы попросите ИТ-отдел сделать резервную копию магнитных лент.
84
Любезно предоставлено http://geek-and-poke.com.
85
Иногда такие сущности могут быть импортированы из заранее созданных внешних библиотек.
86
Источник: http://xkcd.com.
87
Если вы хотите обругать чей-то исходный код, скажите, что это спагетти
