3. Теория сложности в теории алгоритмов.

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

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

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

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

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

Классы сложности.

Классами сложности – множества вычислительных задач, примерно одинаковых по сложности вычисления.

1. Класс P (от англ. polynomial) – класс алгоритмов, работающих за полиноминальное время, время работы не существенно зависит от размера входных данных. Стандартные алгоритмы целочисленного сложения, перемножения матриц и др.

2. Класс NP (от англ. non-deterministic polynomial) – класс алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (сертификат решения), то он сможет достаточно быстро решить задачу. Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор. Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.

3. Класс BPP (от англ. bounded-error, probabilistic, polynomial) – класс алгоритмов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Решение СЛАУ методом половинного деления, методом хорд и др.

3. Организация эвм и систем.

   1. Принцип программного управления

Такое определение подчеркивает, что в основу ЭВМ положен принцип программного управления. Один из способов его реализации был предложен в 1945 г. американским математиком Дж. фон Нейманом, и с тех пор неймановский принцип программного управления используется в качестве основного принципа построения ЭВМ. Этот принцип состоит в следующем:

• информация кодируется в двоичной форме и разделяется на единицы (элементы) информации — слова;

• разнотипные слова информации различаются по способу использования, но не способами кодирования;

• слова информации размещаются в ячейках памяти машины и идентифицируются номерами ячеек, которые называются адресами слов;

• алгоритм представляется в форме последовательности управляющих слов — команд, которые определяют наименование операции и слова информации, участвующие в операции. Алгоритм, представленный в терминах машинных команд, называется программой;

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

Выборка программы из памяти осуществляется с помощью счетчика команд. Процессор начинает работу после того, как программа записана в память ЭВМ, а в счетчик команд записан адрес первой команды программы. Счётчик команд процессора последовательно увеличивает хранимый в нем адрес очередной команды на длину команды.

Работу процессора можно описать следующим циклом: чтение команды из памяти по адресу, записанному в СК, увеличение СК на длину прочитанной команды , выполнение прочитанной команды.

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

Таким образом, процессор исполняет программу автоматически, команду за командой, без вмешательства человека.