Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Структурна теорема

След като бяха разгледани възможните начини на писане, въпросът за технологията на тяхното разработване изглежда съвсем естествен. До средата на 60-те години теорията за развитието на алгоритъма не съществуваше - процесът на развитие беше изцяло определен от опита и уменията на програмиста. С нарастването на сложността на програмите обаче се наложи да се създаде методология за тяхното развитие и тя се появи под формата на структурирано програмиране. Идеите за структурирано програмиране бяха изразени през 1965 г. от E. Dijkstra, но те не бяха обединени в цялостна система от правила. През същата година италианските математици К. Бом и Д. Якопини формулират теорема за структурата. Преди да разгледаме неговата същност, е необходимо да въведем някои понятия.

Тъй като алгоритъмът определя реда на обработка на информацията, той трябва да съдържа, от една страна, обработващи действия, а от друга страна, реда на обработката им, наречен поток на управление.

Горните блокове, свързани с обработката на данни, са разделени на прости и условни. Особеността на едно просто действие е, че той има един вход и един изход, за разлика от условния, който има два изхода в зависимост от това дали условието е вярно. Едно просто действие не означава, че е уникално - то може да бъде някаква последователност от действия.

Част от алгоритъма, организиран като просто действие, т.е. един вход (изпълнение винаги започва с едно и също действие) и един изход (т.е. след завършването на даден блок винаги започва същото действие), се нарича функционален блок.

От тази дефиниция по-специално следва, че всяко просто действие е функционален блок, докато условното не е.

Според разпоредбите на структурираното програмиране има само три различни варианта на организация на потока на контрол на действията на алгоритъма. Потокът за управление може да има следните свойства:

1) всеки блок се изпълнява не повече от един път;

2) всеки блок се изпълнява.

Контролният поток, в който се изпълняват и двете от тези свойства, се нарича линейно - в него последователно се изпълняват няколко функционални блока . Потокът на езика на блок-схемите съответства на структурата:

Очевидно е, че няколко блока, свързани с линейно управление могат да бъдат комбинирани в една функционална единица:

Вторият тип управляващ поток се нарича разклоняване - организира изпълнението на един от двата функционални блока в зависимост от стойността на проверяваното логическо условие. Структурна схема на структурата:

В този тип притежава (1), свойство (2) не. Ако структурата съдържа два функционални блока (S 1 и S 2 ), клонът се нарича завършен; Възможно е непълно разклоняване - единият от блоковете е празен (обикновено S 2 ).

Третият тип управляващ поток се нарича цикличен - той организира множество повторения на функционален блок, стига да е вярно логическото условие. За цикличен поток притежава (2), но (1) не притежава. Неговата блокова диаграма е показана на фигурата.

Тъй като разклоняващите и цикличните типове за управление имат един вход и един изход, те обикновено отговарят също на дефиницията на функционален блок. На рекурсивен начин въвеждаме концепцията за стандартен функционален блок:

1) всяко просто действие е стандартен функционален блок;

2) всяка от описаните три управляващи структури е стандартен функционален блок, ако всички включени в тях блокове са стандартни функционални;

3) няма други стандартни функционални блокове.

Определяме друга концепция:

Алгоритъм се нарича структурен, ако може да бъде представен от стандартен функционален блок.

С други думи, структурният алгоритъм е комбинация от трите структури, разгледани по-горе (понякога те се наричат основни алгоритмични структури). Разбира се, не всички алгоритми са структурни. Но структурните алгоритми имат редица забележителни предимства в сравнение с неструктурните:

· Яснота и простота на възприемането на алгоритъма (тъй като броят на началните структури, с които се формира, е малък);

· Проверяемост (за да се тества някоя от основните структури, достатъчно е да се провери коректността на функционалните блокове, включени в нея);

· Модифицируемост (тя се състои в простотата на промяна на структурата на алгоритъма, тъй като съставните блокове са относително независими).

След въвеждането на дефинициите можем да формулираме теоремата за структурата на Бом - Якопини:





Вижте също:

Тестови въпроси и задачи

Всеки неструктурен алгоритъм може да бъде конструиран еквивалентен структурен алгоритъм.

Ентропийни свойства

А.2. Добавяне и умножение на вероятностите

Пример 4.13

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru