Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Задача коммивояжера относится к классу NP-полных задач, который мы обсудили в разделе «Экспоненциальное время» (см. главу 2). Пока не удалось найти оптимальное решение, которое было бы лучше экспоненциального алгоритма.

Любезно предоставлено http://xkcd.com.

Это самый первый алгоритм, который вы увидели в главе 3.

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

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

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

В таком случае говорят, что задачи имеют перекрывающиеся подзадачи.

Вам нужно найти самого высокого мужчину, самую высокую женщину и самого высокого человека в комнате. Будете ли вы измерять рост каждого присутствующего с целью найти самого высокого человека, а затем делать это еще и еще раз применительно к женщинам и мужчинам по отдельности?

Метод удаления ограничений из задач называется ослаблением . Он часто используется для вычисления ограничений в задачах оптимизации.

Модуль , или библиотека , — это структурная часть программного обеспечения, которая предлагает универсальные вычислительные процедуры. Их можно включать при необходимости в другие части программного обеспечения.

Они сопряжены с разрешением доменного имени, созданием сетевого сокета, установлением шифрованного SSL-соединения и многим другим.

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

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

Если узел нарушает это правило, многие алгоритмы поиска по дереву не будут работать.

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

Стратегии автоматической балансировки выходят за рамки этой книги. Если вам любопытно, то в Интернете имеются видеоматериалы, которые показывают, как работают эти алгоритмы.

Двоичная куча min-heap характерна тем, что значение в любой ее вершине не больше , чем значения ее потомков; в двоичной куче max-heap, наоборот, значение в любой вершине не меньше , чем значения ее потомков. — Примеч. пер.

Ситуация, когда найдена новая, неисследованная задача, — это редкость. Когда исследователи находят новую задачу, они пишут об этом научную работу.

Вот более полный список: https://code.energy/algo-list.

Любезно предоставлено http://xkcd.com.

Задача раскраски графа на сайте онлайновых экспертов UVA: https://code.energy/uva-graph-coloring.

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

Читается как «А-звезда» или «А-стар». — Примеч. ред.

Премия Тьюринга — самая престижная премия в области информатики. Ее премиальный фонд составляет один миллион долларов.

В английском языке аббревиатура SQL чаще произносится, как « сиквел», а устная форма « эс-кью-эл» не считается неправильной.

Существует несколько способов выполнить операцию JOIN — см. https://code.energy/joins.

Атомарные операции выполняются одноэтапно: они не могут быть выполнены наполовину.

Любезно предоставлено http://geek-and-poke.com.

В профессиональных кругах это называется «три V»: volume (объем), velocity (скорость) и variety (разнообразие). Некоторые добавляют еще два аспекта: variability (переменчивость) и veracity (достоверность), превращая термин в «пять V».

Большой адронный коллайдер, или БАК, — это самый большой ускоритель частиц в мире. Во время эксперимента его датчики генерируют 1000 терабайт данных в секунду.

Антенная решетка площадью в квадратный километр, или SKA (от англ. Square Kilometer Array), — это группа телескопов, которые планируется ввести в строй в 2020 году. Они будут генерировать 1 млн терабайт данных каждый день.

Сразу после финального матча на чемпионате мира 2014 года по футболу Twitter испытал пиковую нагрузку в более чем 10 000 твитов в секунду.

По данным https://census.gov.

Оперативное запоминающее устройство (англ. RAM, random access memory). Более точное наименование на русском — запоминающее устройство (память) с произвольным доступом, сокращенно ЗУПД (ППД).

Центральный процессор (англ. CPU, central processing unit).

Двоичные числа выражены в системе счисления с основанием 2. Приложение I объясняет, как это следует понимать.

Программный код даже может изменять сам себя за счет включения команд, которые переписывают части собственного кода в ОЗУ. Нередко компьютерные вирусы поступают именно так, чтобы затруднить их обнаружение антивирусным ПО. Здесь можно провести удивительную параллель с биологическими вирусами, изменяющими свои ДНК, чтобы спрятаться от иммунной системы носителей.

Не путайте эту аббревиатуру с общепринятым акронимом для Personal Computer (PC) — «персональный компьютер».

Во многих персональных компьютерах эта программа называется BIOS (англ. basic input/output system, «базовая система ввода-вывода»).

О процессоре с 1000 ядер исследователи объявили еще в 2016 году.

Дисковая операционная система (Disk Operating System). Об операционных системах мы вскоре расскажем подробнее.

О языках программирования подробнее будет рассказано в следующей главе.

Можете взглянуть на компилятор, который превращает любой код на C в двоичный код лишь с одной машинной командой MOV: https://code.energy/mov.

Любезно предоставлено http://geek-and-poke.com.

Любезно предоставлено http://xkcd.com.