Почему калькулятор нельзя назвать алгоритмической машиной, а компьютер можно

Обновлено: 21.11.2024

Компьютерная программа представляет собой набор инструкций (также называемых кодом), данных компьютеру для выполнения какой-либо задачи, которая может быть любой: от суммирования чисел от 1 до 10 до моделирования климата. Когда компьютер следует инструкциям, данным в программе, мы говорим, что компьютер выполняет программу. Есть много разных способов написать эти инструкции для компьютера (мы говорим о программировании на разных языках) — в этой статье мы будем использовать язык C++. По его окончанию вы сможете писать свои собственные программы для выполнения основных математических и научных задач.

Наша первая программа на C++

Наша первая программа на C++ скажет компьютеру распечатать текст "Hello world!". Вот он (не волнуйтесь, он будет объяснен построчно).

Чтобы компьютер мог запустить эту программу, она должна быть сначала скомпилирована компилятором (это означает ее перевод с языка C++ на родной язык машинного кода компьютера). Есть полезный онлайн-ресурс codepad.org, который делает для нас шаги по компиляции и запуску программы. Перейдите на этот веб-сайт, выберите параметр «C++» для языка и скопируйте и вставьте (или, что еще лучше, введите) программу выше в текстовое поле, прежде чем нажать кнопку «Отправить». Если вы ввели текст правильно, вы должны увидеть следующее для вывода:

Если этого не произошло, возможно, вы неправильно вошли в программу — попробуйте еще раз.

Чтобы понять, что происходит, давайте рассмотрим структуру программы.

Эти первые две строки сообщают компилятору о ряде доступных функций. Функция — это блок кода, который в данном случае уже существует в памяти компьютера и готов к использованию. Пока вам не нужно точно понимать, что означают эти строки; только то, что они должны быть помещены в начало большинства программ на C++, которые вы будете писать. В этой программе мы хотим использовать функцию cout, которая выводит текст.

Этот тип структуры обозначает функцию в программе, называемую "основной". Это специальная функция; мы можем (и позже будем) определять функции с другими именами, но компьютер будет искать эту функцию, чтобы начать следовать начальным инструкциям, которые мы помещаем в скобки (они показывают, где функция начинается и заканчивается). Позже мы подробнее опишем синтаксис функции.

Это строка комментария. Когда компилятор увидит "//", он будет игнорировать все, что идет после этого, до конца строки. Добавление этого текста не влияет на поведение программы, но может быть полезно, когда человек хочет прочитать и понять код позже.

Например, предположим, что мы объявили целочисленную переменную с именем «возраст». Выражение age >= 18 имеет логическое значение и истинно, если возраст $\ge$ 18, и ложно в противном случае. Аналогично, мы могли бы написать возраст > 17. Мы можем сохранить результат этого выражения в логической переменной. Вот пример программы:

Попробуйте запустить программу. Попробуйте изменить значение age, а также попробуйте другие операторы сравнения (например, попробуйте заменить >= одним из , 17 — допустимый фрагмент кода C++, и всегда имеет значение false). Мы также можем комбинировать выражения сравнения так же, как мы комбинировали логические значения вместе с && и ||. Что делает следующий фрагмент кода?

Этот код также показывает, где еще используются скобки < >. Они похожи на круглые скобки ( ) в математическом выражении, таком как (((2+3)*5)-4)*(3-4). Они должны быть вложены друг в друга и должным образом сопоставляться — например, )2+(3*7)+3( не является допустимым математическим выражением. Каждый раз, когда < появляется в коде C++, за ним нужно следовать где-то позже с помощью соответствующего >. Мы можем объединить операторы if таким образом, например:

Мы также можем расширить операторы if до блока кода if-else. Это имеет общую форму if ( expr1 ) < code1 > else if ( expr2 ) < code2 >. else if ( exprN ) < codeN >else (но возможны многие варианты). Компьютер по очереди проверит каждое выражение expr1, expr2, ., чтобы убедиться, что какое-либо из них истинно. Если это правда, то код внутри скобок будет выполнен, и дальнейшие выражения не будут проверяться. Если ни одно из выражений не является истинным, то выполняется код в последних скобках (lastCode выше). Любая из частей else if или else может быть исключена, чтобы также получить корректный код. В следующем примере программы показано их использование.

При запуске программы отображается текст "x меньше y". Мы могли бы удалить последнюю часть else, чтобы создать корректную программу на C++, которая не будет отображать никаких результатов при запуске (поскольку ни одно из выражений x > y или x == y верно), например:

Или мы могли бы удалить среднюю часть "else if", чтобы выполнялся либо первый код, либо второй код.

Упражнение. Напишите программу, определяющую переменную x с некоторым начальным значением и оператор if-else, выводящий, является ли x нечетное или четное.

Циклы

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

Первый тип циклов — это цикл while. Чтобы использовать это в программе на C++, мы вставляем код формы

  1. Если выражение ложно, то пропустите код внутри скобок < >и продолжите работу с программой.
  2. В противном случае выполните код в квадратных скобках < >и снова перейдите к шагу 1.

Поэтому код в квадратных скобках < >будет выполняться повторно, пока выражение не станет ложным.

Давайте рассмотрим пример. Попробуйте запустить следующую программу:

Упражнение: напишите программу, которая выводит числа от 0 до 9 по порядку, а затем обратно до 0. Вам понадобятся два цикла while.

На самом деле такое использование цикла while (где мы увеличиваем переменную счетчика каждый раз, пока она не достигнет определенного значения) происходит так часто, что в C++ есть специальный способ записи — цикл for. Общая форма:

Давайте рассмотрим пример цикла for, суммирующего числа от 0 до 10 и выводящего значение:

Упражнение: Измените приведенную выше программу:

  1. Таким образом, он суммирует квадраты от 0 до 10.
  2. Добавьте целочисленную переменную с именем N с некоторым начальным значением (например, 100) и измените код так, чтобы он суммировал квадраты от 0 до N.

Гипотеза Коллатца утверждает, что следующий процесс всегда останавливается для всех начальных значений n:

  1. Возьмите целое число n больше 0.
  2. Если n четное, уменьшите его вдвое. В противном случае установите значение 3n+1.
  3. Если n теперь имеет значение 1, остановитесь. В противном случае перейдите к шагу 2.

Упражнение: напишите программу на C++ для проверки гипотезы Коллатца, которая выводит n на каждой итерации (мы даем программу решения ниже, но попробуйте сначала написать ее!).

Упражнение. Напишите программу на C++, реализующую алгоритм Евклида.

Функции

В простейшем случае функция — это способ группировки набора инструкций, чтобы их можно было многократно выполнять. У каждой функции есть имя (у них те же правила, что и у имен переменных, поэтому они чувствительны к регистру; разрешены буквы, цифры и _, и они не могут начинаться с цифры). В начале программы на C++ мы «объявляем» функцию, которая сообщает компилятору, что она существует (иначе, когда встречается имя функции, компилятор не знал бы, что оно означает). Затем где-то в программе мы «определяем» функцию, т. е. пишем инструкции для функции. Когда мы хотим выполнить инструкции в функции, мы вызываем ее, записывая ее имя (как будет видно).

Давайте рассмотрим пример. Мы пишем функцию countToTen, которая выводит числа от 1 до 9. Во-первых, нам нужно включить следующую строку кода где-то в верхней части программы, чтобы определить функцию:

Ключевое слово void говорит о том, что функция не возвращает значение. Подробнее об этом чуть позже. Вскоре будет объяснено использование символа () и, конечно же, точки с запятой; требуется в конце инструкции.

И чтобы определить функцию, мы включаем следующий блок кода (обратите внимание, что на этот раз мы не ставим точку с запятой в конце первой строки):

Здесь // код заменяется кодом, который будет выполняться при вызове функции. Как видите, форма очень похожа на out int main() — это потому, что «main» на самом деле является специальной функцией, которую вызывает компьютер. Когда мы хотим вызвать функцию, мы пишем countToTen();. Давайте посмотрим на полную программу, которая дважды вызывает эту функцию. Попробуйте запустить его.

Они называются функциями, потому что могут вести себя как математические функции — они могут иметь входные значения и/или выходные значения.

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

Давайте изменим приведенную выше функцию countToNine, чтобы она имела входное значение (которое мы называем N) и печатала числа от 1 до N. Мы объявляем функцию следующим образом (изменив ее имя):

Мы аналогичным образом определяем функцию, заменив 9 в цикле for на N. Чтобы вызвать функцию со значением, скажем, 5, напишем «countToN(5);». Если у нас есть целочисленная переменная с именем x, мы можем использовать значение x в качестве входных данных, написав «countToN(x);».Давайте соберем это вместе, чтобы сформировать полную программу — попробуйте угадать, что делает следующая программа, прежде чем запускать ее!.

Чтобы объявить функцию с выходным значением (которое называется возвращающим значение), мы заменяем ключевое слово void типом значения. Например, если бы мы хотели вернуть десятичное число, мы бы заменили void на float. Внутри функции, когда мы хотим вернуться из функции туда, откуда была вызвана функция, мы пишем "return value;", где value заменяется возвращаемым значением (например, 5 или x).

Давайте создадим функцию с именем gcd, которая имеет два входных значения (которые мы будем называть a и b) и (грубо) вычисляет их наибольший общий делитель и возвращает значение. Как описано выше, мы объявляем функцию как

И для определения функции мы используем аналогичный формат (на этот раз снова без точки с запятой в конце первой строки):

Упражнение: Как и почему работает алгоритм, приведенный в приведенной выше функции?

Для вызова функции мы пишем, например, gcd( 168, 120 ). Затем это обрабатывается как целое число, значением которого является возвращаемое значение, поэтому мы можем рассматривать его как любое другое целое число. Например, мы можем написать «int x = gcd (168, 120);» чтобы создать целое число с этим значением. Или мы могли бы написать "cout

Упражнение: измените код в функции gcd, чтобы она использовала алгоритм Евклида, который более эффективен в вычислительном отношении.

Упражнение. Напишите функцию, которая принимает два целых числа a и b и возвращает значение $a^b$.

Другие математические функции

Мы рассмотрели основные функциональные возможности C++. C++ также поставляется с целым набором предопределенных функций, например, с такими распространенными математическими функциями, как sin, cos и квадратный корень, а также с функциями для генерации случайных чисел.

Общие математические функции

Это содержит новый код — float(rand()) превращает целое число, возвращаемое rand(), в число с плавающей запятой с тем же значением. Это необходимо, так как если мы делим два целых числа, то часть после запятой отбрасывается. Вот пример программы, генерирующей 10 случайных чисел от 0 до 1.

Упражнение. Как бы вы сгенерировали случайное целое число от 1 до 10?

Упражнение. Используйте случайные числа и стрелку Бюффона, чтобы вычислить число Пи.

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

Алгоритм – это специальная процедура для решения четко определенной вычислительной задачи. Разработка и анализ алгоритмов лежат в основе всех аспектов информатики: искусственного интеллекта, баз данных, графики, сетей, операционных систем, безопасности и так далее. Разработка алгоритмов — это больше, чем просто программирование. Это требует понимания альтернатив, доступных для решения вычислительной задачи, включая аппаратное обеспечение, сеть, язык программирования и ограничения производительности, которые сопровождают любое конкретное решение. Это также требует понимания того, что значит для алгоритма быть «правильным» в том смысле, что он полностью и эффективно решает поставленную задачу.

Сопутствующее понятие – это разработка конкретной структуры данных, которая позволяет алгоритму работать эффективно. Важность структур данных связана с тем фактом, что основная память компьютера (где хранятся данные) является линейной и состоит из последовательности ячеек памяти, последовательно пронумерованных 0, 1, 2,…. Таким образом, простейшая структура данных представляет собой линейный массив, в котором соседние элементы нумеруются последовательными целочисленными «индексами», а доступ к значению элемента осуществляется по его уникальному индексу. Массив можно использовать, например, для хранения списка имен, а эффективные методы необходимы для эффективного поиска и извлечения определенного имени из массива. Например, сортировка списка в алфавитном порядке позволяет использовать так называемый метод бинарного поиска, при котором оставшаяся часть списка для поиска на каждом шаге разрезается пополам. Этот метод поиска похож на поиск определенного имени в телефонной книге. Зная, что книга находится в алфавитном порядке, можно быстро перейти на страницу, близкую к странице, содержащей нужное имя. Для эффективной сортировки и поиска списков данных было разработано множество алгоритмов.

Хотя элементы данных хранятся в памяти последовательно, они могут быть связаны друг с другом указателями (по сути, адресами памяти, хранящимися вместе с элементом, чтобы указать, где находится следующий элемент или элементы в структуре), чтобы данные можно было организовать в способами, аналогичными тем, которыми они будут доступны.Простейшая такая структура называется связанным списком, в котором к несмежным элементам можно получить доступ в заранее заданном порядке, следуя указателям от одного элемента в списке к другому. Список может быть циклическим, когда последний элемент указывает на первый, или каждый элемент может иметь указатели в обоих направлениях, образуя двусвязный список. Были разработаны алгоритмы для эффективного управления такими списками путем поиска, вставки и удаления элементов.

Указатели также позволяют реализовывать более сложные структуры данных. Граф, например, представляет собой набор узлов (элементов) и связей (известных как ребра), соединяющих пары элементов. Такой граф может представлять набор городов и соединяющих их автомагистралей, расположение элементов схемы и соединительных проводов на микросхеме памяти или конфигурацию людей, взаимодействующих через социальную сеть. Типичные алгоритмы графа включают стратегии обхода графа, например, как следовать ссылкам от узла к узлу (возможно, искать узел с определенным свойством) таким образом, чтобы каждый узел посещался только один раз. Связанной с этим проблемой является определение кратчайшего пути между двумя заданными узлами на произвольном графе. (См. теорию графов.) Проблема, представляющая практический интерес в сетевых алгоритмах, например, состоит в том, чтобы определить, сколько «сломанных» каналов связи можно допустить, прежде чем связь начнет прерываться. Аналогичным образом, при проектировании микросхем сверхбольшой интеграции (СБИС) важно знать, является ли граф, представляющий схему, плоским, то есть может ли он быть нарисован в двух измерениях без пересечения каких-либо звеньев (соприкосновения проводов).

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

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

Еще дальше находятся те алгоритмические проблемы, которые могут быть сформулированы, но неразрешимы; то есть можно доказать, что никакая программа не может быть написана для решения проблемы. Классическим примером неразрешимой алгоритмической проблемы является проблема остановки, которая утверждает, что нельзя написать программу, которая может предсказать, остановится ли какая-либо другая программа после конечного числа шагов. Неразрешимость проблемы остановки имеет прямое практическое значение для разработки программного обеспечения. Например, было бы легкомысленно пытаться разработать программный инструмент, который предсказывает, есть ли в другой разрабатываемой программе бесконечный цикл (хотя наличие такого инструмента было бы чрезвычайно полезным).

Компьютер – это машина, работающая с символами, которая следует набору хранимых инструкций, называемых программой. Он выполняет эти манипуляции очень быстро и имеет память для хранения ввода, списков команд и вывода. Компьютер не может думать так, как мы общаемся с людьми. При использовании компьютера для решения задачи необходимо указать необходимые исходные данные, операции, которые необходимо выполнить (в порядке выполнения) и какие результаты вы хотите получить на выходе. Если какая-либо из этих инструкций отсутствует, вы либо не получите результатов, либо получите неверные результаты. В любом случае ваша проблема еще не решена. Поэтому перед написанием программы необходимо рассмотреть несколько шагов. Эти шаги могут освободить вас от многочасового поиска и устранения ошибок в вашей программе (процесс, называемый отладкой). Это также должно значительно упростить решение проблем с помощью компьютера. Для облегчения процесса решения проблемы предлагаются следующие шаги:

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

Примеры 1. Вычислите и распечатайте среднее значение набора значений данных. 2. Для квадратного уравнения вычислить его действительные корни. Посоветуйте пользователю, если корни сложные. 3.Распечатайте таблицу значений времени и высоты для траектории ракеты. Начните время с нуля и увеличивайте время на 1,0 секунды, пока ракета не упадет на землю или общее время не превысит 300 секунд.

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

<Н3>3. Разработайте алгоритм

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

Пример определения проблемы. Вычислите и распечатайте среднее значение набора значений данных. Алгоритм: 1. Установить сумму значений данных равными нулю. 2. Установите количество значений данных равным нулю. 3. Пока значения данных существуют, добавьте следующее значение данных к сумме и добавьте 1 к счету. 4. Чтобы вычислить среднее значение, разделите сумму на количество. 5. Распечатайте среднее значение.

<Н3>4. Напишите код проблемы.

Приведенный выше алгоритм не может быть прочитан компьютером. Сначала его нужно написать на языке программирования. Затем компилятор преобразует ваш программный код в машинный код, который компьютер сможет понять и использовать. Сначала изучение компьютерного языка может показаться трудным, но с практикой это станет легче.

<Н3>5. Протестируйте свою программу.

Тестирование вашей программы должно устранять как синтаксические, так и логические ошибки. У вас могут быть ошибки в синтаксисе вашего кода, которые не позволяют компилятору преобразовать его в машинный код. Ваш алгоритм мог пропустить важный шаг в последовательности, и хотя программа компилируется, она не дает достоверных результатов. Эти ошибки называются ошибками, и «отладка» кода может занять больше времени, чем его написание. Выполнение шагов 1, 2 и 3 должно ограничить количество ошибок в вашей программе и упростить исправление и модификацию.

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

Решение проблемы

Результаты, которые вы получаете после успешной компиляции и запуска программы, редко являются "ответом" на ваш вопрос. Вы должны интерпретировать эти результаты относительно определения проблемы. Если результаты состоят из длинного списка значений данных, создайте визуализацию данных, чтобы интерпретировать то, что вы видите. Помните, что компьютер не «решает» проблему; это инструмент, который выполняет инструкции в программе. Вы, пользователь, должны ответить на вопрос, поставленный в постановке задачи.

УПРАЖНЕНИЯ

<р>1. Сформулируйте математическую модель и разработайте алгоритм для каждой из следующих задач. а. Найдите среднее значение набора из десяти чисел. б. Преобразуйте набор температур Фаренгейта в температуры Цельсия в температуры Кельвина и распечатайте таблицу всех трех температур. в. Зная основания и высоту треугольника, вычислить площадь треугольника. Повторите этот расчет для 10 пар значений.

Алгоритм – это специальная процедура для решения четко определенной вычислительной задачи. Разработка и анализ алгоритмов лежат в основе всех аспектов информатики: искусственного интеллекта, баз данных, графики, сетей, операционных систем, безопасности и так далее. Разработка алгоритмов — это больше, чем просто программирование. Это требует понимания альтернатив, доступных для решения вычислительной задачи, включая аппаратное обеспечение, сеть, язык программирования и ограничения производительности, которые сопровождают любое конкретное решение. Это также требует понимания того, что значит для алгоритма быть «правильным» в том смысле, что он полностью и эффективно решает поставленную задачу.

Сопутствующее понятие – это разработка конкретной структуры данных, которая позволяет алгоритму работать эффективно. Важность структур данных связана с тем фактом, что основная память компьютера (где хранятся данные) является линейной и состоит из последовательности ячеек памяти, последовательно пронумерованных 0, 1, 2,…. Таким образом, простейшая структура данных представляет собой линейный массив, в котором соседние элементы нумеруются последовательными целочисленными «индексами», а доступ к значению элемента осуществляется по его уникальному индексу. Массив можно использовать, например, для хранения списка имен, а эффективные методы необходимы для эффективного поиска и извлечения определенного имени из массива.Например, сортировка списка в алфавитном порядке позволяет использовать так называемый метод бинарного поиска, при котором оставшаяся часть списка для поиска на каждом шаге разрезается пополам. Этот метод поиска похож на поиск определенного имени в телефонной книге. Зная, что книга находится в алфавитном порядке, можно быстро перейти на страницу, близкую к странице, содержащей нужное имя. Для эффективной сортировки и поиска списков данных было разработано множество алгоритмов.

Хотя элементы данных хранятся в памяти последовательно, они могут быть связаны друг с другом указателями (по сути, адресами памяти, хранящимися вместе с элементом, чтобы указать, где находится следующий элемент или элементы в структуре), чтобы данные можно было организовать в способами, аналогичными тем, которыми они будут доступны. Простейшая такая структура называется связанным списком, в котором к несмежным элементам можно получить доступ в заранее заданном порядке, следуя указателям от одного элемента в списке к другому. Список может быть циклическим, когда последний элемент указывает на первый, или каждый элемент может иметь указатели в обоих направлениях, образуя двусвязный список. Были разработаны алгоритмы для эффективного управления такими списками путем поиска, вставки и удаления элементов.

Указатели также позволяют реализовывать более сложные структуры данных. Граф, например, представляет собой набор узлов (элементов) и связей (известных как ребра), соединяющих пары элементов. Такой граф может представлять набор городов и соединяющих их автомагистралей, расположение элементов схемы и соединительных проводов на микросхеме памяти или конфигурацию людей, взаимодействующих через социальную сеть. Типичные алгоритмы графа включают стратегии обхода графа, например, как следовать ссылкам от узла к узлу (возможно, искать узел с определенным свойством) таким образом, чтобы каждый узел посещался только один раз. Связанной с этим проблемой является определение кратчайшего пути между двумя заданными узлами на произвольном графе. (См. теорию графов.) Проблема, представляющая практический интерес в сетевых алгоритмах, например, состоит в том, чтобы определить, сколько «сломанных» каналов связи можно допустить, прежде чем связь начнет прерываться. Аналогичным образом, при проектировании микросхем сверхбольшой интеграции (СБИС) важно знать, является ли граф, представляющий схему, плоским, то есть может ли он быть нарисован в двух измерениях без пересечения каких-либо звеньев (соприкосновения проводов).

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

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

Еще дальше находятся те алгоритмические проблемы, которые могут быть сформулированы, но неразрешимы; то есть можно доказать, что никакая программа не может быть написана для решения проблемы. Классическим примером неразрешимой алгоритмической проблемы является проблема остановки, которая утверждает, что нельзя написать программу, которая может предсказать, остановится ли какая-либо другая программа после конечного числа шагов. Неразрешимость проблемы остановки имеет прямое практическое значение для разработки программного обеспечения. Например, было бы легкомысленно пытаться разработать программный инструмент, который предсказывает, есть ли в другой разрабатываемой программе бесконечный цикл (хотя наличие такого инструмента было бы чрезвычайно полезным).

Читайте также: