Виды и свойства алгоритмов. 
Решение задачи Майхилла (о стрелках)

Курсовая работа по дисциплине: «Теория вычислительных процессов»

на тему:

" Виды и свойства алгоритмов. Решение задачи Майхилла (о стрелках)"

• Введение
• 1. Теоретический вопрос «Виды и свойства алгоритмов»
• 1.1 Виды алгоритмов
• 1.2 Свойства алгоритмов
• 2. Решение задачи Майхилла (о стрелках)
• 2.1 Постановка задачи
• 2.2 Решение задачи
• Заключение
• Список использованных источников

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

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

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

Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственное требование — его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить. [1, С.46−47]

1. Теоретический вопрос «Виды и свойства алгоритмов»

1.1 Виды алгоритмов

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

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики — вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа — рекурсивные функции - является исторически первой формализацией понятия алгоритма.

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

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

Впрочем, модели второго и третьего типа довольно близки (их взаимная сводимость доказывается просто). [2, С.154−155]

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

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

· механический алгоритм, или иначе детерминированный, жесткий (например алгоритм работы машины, двигателя и т. п.);

· гибкий алгоритм, т. е. вероятностный и эвристический;

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

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

· линейный алгоритм — набор команд (указаний), выполняемых последовательно во времени друг за другом;

· разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов;

· циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. [3]

1.2 Свойства алгоритмов

Для алгоритмов характерны общие черты и особенности.

1. Дискретность

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

2. Детерминированность (определенность)

Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого конкретного случая. Предписания алгоритма единственным и вполне определенным путем всякий раз приводят к искомому результату. Для описания алгоритмов были разработаны формально определенные языки программирования, или машинные языки, в которых каждый оператор имеет строго определенное значение [5, С.23−24].

3. Результативность

Данное свойство требует от алгоритма остановки после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления функции f (x), должен показать, что алгоритм останавливается после конечного числа шагов (говорят, сходится) для любого x из области задания f. Проверить результативность (сходимость) непросто. Сходимость обычно не удается установить простым просмотром описания алгоритма; общего же метода проверки сходимости, пригодного для любого алгоритма А и любых данных х, не существует.

4. Массовость

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

5. Допустимость начальных данных

Говоря о начальных данных для алгоритма, имеют в виду так называемые допустимые начальные данные, т. е. такие начальные данные, которые сформулированы в терминах данного алгоритма.

Среди допустимых начальных данных для алгоритма могут быть такие, к которым он применим, т. е. отправляясь oт которых можно получить искомый результат, а могут быть и такие, к которым данный алгоритм неприменим, т. е. отправляясь от которых искомого результата получить нельзя. Неприменимость алгоритма к допустимым начальным данным может заключаться либо в том, что алгоритмический процесс никогда не оканчивается, либо в том, что его выполнение во время одного из шагов наталкивается на препятствие, заходит в тупик. [4, С.314−315]

Также следует различать:

а) описание алгоритма (инструкцию или программу);

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

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

2. Решение задачи Майхилла (о стрелках)

2.1 Постановка задачи

Имеется цепь стрелков и офицер. Каждый находящийся в цепи солдат может общаться только со своими соседями справа и слева. Офицер размещается на фланге цепи и может подавать команды только крайнему в цепи стрелку. Общее количество стрелков в цепи каждому из стрелков неизвестно. Общаться каждый из стрелков может только со своими соседями справа и слева. Требуется обеспечить одновременный залп всех стрелков цепи после подачи команды офицером.

2.2 Решение задачи

Данная задача решается при помощи автоматной модели поведения стрелка.

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

Перечень блоков

— Officer — модель офицера;

— Rifleman 1, 2, … N — модели стрелков;

— WriteStates — блок протокола.

Блоки Officer и WriteStates не обязательные. Первый введен для удобства управления цепью стрелков, второй — для визуализации решения.

Функционирование модели

Объекты модели функционируют параллельно. Время для всех объектов едино и моделируется абстрактным дискретным временем. Офицер, получив команду, передает ее ближайшему стрелку, тот следующему и т. д. Чтобы выполнить команду, стрелки обмениваются между собой информацией. По истечении некоторого периода времени они должны одновременно выполнить команду выстрел. В модели — перейти в одинаковое для всех объектов состояние. При этом все промежуточные состояния объектов на каждом такте протоколируются созданным для этого объектом, который функционирует параллельно остальным объектам, составляющим задачу. [6]

Рисунок 1 — Модель поведения стрелков в задаче Майхилла

Решение задачи на языке высокого уровня С++

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

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

Листинг программ сервера («Офицер») и клиента («Стрелок») представлен ниже.

Программа-сервер («Офицер» )

// —————————————————————————————————————;

#include

#include

#pragma hdrstop

#include «Unit1. h»

#define BUFSIZE 512

// —————————————————————————————————————;

#pragma package (smart_init)

#pragma resource «*. dfm»

TForm1 *Form1;

HANDLE hThread;

HANDLE hProcPipe [5];

LPTSTR lpszPipename = «\\. \pipe\pipe1001» ;

HANDLE hPipe;

HANDLE hSemaphoreCount; // дескриптор семафора «Счет»

int SemaphoreMax=5; // максимальный размер счетчика семафора, и его начальное

// значение

int Count=0;

void ConnectShooters (LPVOID); // создание именованного канала для общения с

// клиентом

void ShooterThread (LPVOID); // поток для работы с клиентом

void Shoot (); // произвести выстрел

// —————————————————————————————————————;

__fastcall TForm1: TForm1 (TComponent* Owner)

: TForm (Owner)

{

randomize ();

for (int i=0; i<5; i++)

{

hProcPipe [i] =NULL;

}

}

// создание именованного канала для общения с клиентом

// —————————————————————————————————————;

void ConnectShooters (LPVOID lpvParam)

{

int Number=0;

while (Number<5)

{

bool fConnected;

hPipe = CreateNamedPipe (lpszPipename,

PIPE_ACCESS_DUPLEX,

PIPE_TYPE_MESSAGE |

PIPE_READMODE_MESSAGE |

PIPE_WAIT,

PIPE_UNLIMITED_INSTANCES,

BUFSIZE,

BUFSIZE,

0,NULL);

fConnected = ConnectNamedPipe (hPipe, NULL);

if (fConnected)

{

hProcPipe [Number] =hPipe;

// создание потока для работы с клиентом

hThread = CreateThread (NULL,

0, (LPTHREAD_START_ROUTINE) ShooterThread,

(LPVOID) Number,

0,NULL);

Number++;

}

else

CloseHandle (hPipe);

}

}

// поток для работы с клиентом

// —————————————————————————————————————;

void ShooterThread (LPVOID lpvParam)

{

char chBuf [BUFSIZE];

DWORD cbRead, cbWritten;

bool fSuccess;

int n= (int) lpvParam;

while (1)

{

// считывание ответов клиента из канала

fSuccess = ReadFile (hProcPipe [n],

chBuf,

BUFSIZE,

&cbRead,

NULL);

if (fSuccess)

{

int result=atoi (chBuf);

switch (result)

{

// в случае ответа клиента «1» идет прямой счет

case (1):

Count++;

Form1->StringGrid1->Cells [Count-1] = IntToStr (Count) +" -й" ;

break;

// в случае ответа клиента «2» идет обратный счет

case (2):

Form1->StringGrid1->Cells [Count-1] = IntToStr (Count) +" -й команду принял" ;

Count—;

// при окончании обратного счета производим выстрел

if (Count == 0) Shoot ();

break;

default: break;

}

}

else break;

}

CloseHandle (hProcPipe [n]);

hProcPipe [n] =NULL;

}

// выстрел

void Shoot ()

{

for (int i = 1; i <= 5; i++)

Form1->StringGrid1->Cells [i-1] = «Выстрел» ;

Form1->Button1->Enabled=true;

}

void __fastcall TForm1: Button1Click (TObject *Sender)

{

STARTUPINFO StartupInfo;

PROCESS_INFORMATION ProcessInfo;

Form1->Button1->Enabled=false;

hThread = CreateThread (NULL,

0, (LPTHREAD_START_ROUTINE) ConnectShooters,

(LPVOID) 0,0,NULL);

if (hThread == NULL) {PrintInfo («Ошибка при создании потока»); return; }

// для каждого стрелка создаем процесс

for (int i=0; i<5; i++)

{

ZeroMemory (&StartupInfo, sizeof (StartupInfo));

StartupInfo. cb=sizeof (StartupInfo);

StartupInfo. dwFlags = STARTF_USESHOWWINDOW;

StartupInfo. wShowWindow = SW_HIDE;

// параметр командной строки, определяющий очередность счета

// «стрелков-клиентов»

int ShooterSleep= (i+1) *1000;

AnsiString CommandLine="" ;

CommandLine="Shooter «+IntToStr (i) +» «+IntToStr (ShooterSleep);

if (!

CreateProcess (NULL,

CommandLine. c_str (), // Указатель на строку,

// определяющую командную строку для выполнения

NULL,

NULL,

false,

0,NULL,

GetCurrentDir (). c_str (), // имя текущего каталога

&StartupInfo, // информация предустановки

&ProcessInfo)) // информация о процессе

{PrintInfo («Не могу создать процесс»); return; }

hProcPipe [i] =ProcessInfo. hProcess;

}

// создаем семафор «Счет»

hSemaphoreCount = CreateSemaphore (NULL, // Адрес структуры TSecurityAttributes

SemaphoreMax, // начальное значение счетчика

SemaphoreMax, // максимальное значение

// счетчика

" SemaphoreCount"); // имя объекта

}

// —————————————————————————————————————;

Программа-клиент («Стрелок» )

// —————————————————————————————————————-

#include

#include

#define BUFSIZE 512

#define N 5

#pragma hdrstop

// —————————————————————————————————————;

#pragma argsused

LPTSTR lpszPipename="\\. \pipe\pipe1001″ ;

HANDLE hPipe;

HANDLE hSemaphoreCount; // дескриптор семафора «Счет»

// отправка сообщения на сервер

void MsgToServer (int Message)

{

char chBuf [BUFSIZE];

bool fSuccess;

DWORD cbWritten;

AnsiString S=IntToStr (Message);

wsprintf (chBuf, (const char*) S. c_str ()," /0″);

fSuccess =WriteFile (hPipe,

chBuf,

BUFSIZE,

&cbWritten,

NULL);

}

// основная функция

int main (int argc, char* argv [])

{

randomize ();

char chBuf [BUFSIZE];

DWORD cbRead, cbWritten, dwMode;

// аргумент командной строки, отвечающий за очередность счета стрелков

int ShooterSleep=atoi (argv [2]);

// получение дескриптора канала

while (1)

GENERIC_WRITE,

FILE_SHARE_READ,

NULL,

OPEN_EXISTING,

0,NULL);

if (hPipe! = INVALID_HANDLE_VALUE) break;

if (GetLastError ()! = ERROR_PIPE_BUSY) return 1;

if (! WaitNamedPipe (lpszPipename, 20 000)) return 1;

Sleep (ShooterSleep);

while (1)

{

// получение дескриптора семафора «Счет»

hSemaphoreCount = OpenSemaphore (SEMAPHORE_ALL_ACCESS, 0, «SemaphoreCount»);

// «засыпание» потока для выполнения очередности счета

Sleep (ShooterSleep);

// если семафор в сигнальном состоянии, то идет прямой счет

// иначе выход из цикла, далее — обратный счет

if (WaitForSingleObject (hSemaphoreCount, 0) == WAIT_OBJECT₀) MsgToServer (1);

else break;

}

// обратный счет

MsgToServer (2);

// «засыпание» для выполнения очередности обратного счета

Sleep ((5000-ShooterSleep) *2);

// закрытие дескрипторов

CloseHandle (hPipe);

CloseHandle (hSemaphoreCount);

return 0;

}

// —————————————————————————————————————-

алгоритм логический математический свойство

Заключение

В теоретической части были рассмотрены виды и свойства алгоритмов.

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

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

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

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

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

Список использованных источников

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2011. — 1296 с.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с.

3. Альфа и Омега [Электронный ресурс]. Режим доступа: http://alfa2omega.ru. Дата доступа: 13.12.2012.

4. Игошин В.И. Математическая логика и теория алгоритмов. — М.: Издательский центр «Академия», 2009. — 448 с.

5. Кнут Д. Искусство программирования, том 1. Основные алгоритмы — М.: Издательский дом «Вильямс», 2007. — 720с.