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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// ---------------------------------------------------------------------------

#include <vcl. h>

#include <iostream. h>

#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 [0] [Count-1] = IntToStr (Count) +"-й";

break;

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

case (2):

Form1->StringGrid1->Cells [1] [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 [2] [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 <vcl. h>

#include <iostream. h>

#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)

{

hPipe = CreateFile (lpszPipename,

GENERIC_READ |

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, 20000)) return 1;

}

Sleep (ShooterSleep);

while (1)

{

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

hSemaphoreCount = OpenSemaphore (SEMAPHORE_ALL_ACCESS, 0, "SemaphoreCount");

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

Sleep (ShooterSleep);

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

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

if (WaitForSingleObject (hSemaphoreCount,0) == WAIT_OBJECT_0) MsgToServer (1);

else break;

}

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

MsgToServer (2);

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

Sleep ( (5000-ShooterSleep) *2);

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

CloseHandle (hPipe);

CloseHandle (hSemaphoreCount);

return 0;

}

// ---------------------------------------------------------------------------

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

Заключение