Кіріспе

3 типті басқару құрылымдары бар басқару ағыны графиктері кез келген есептелетін функцияны есептей алады. Құрылымдық бағдарлама теоремасы, сонымен қатар Бём – Жакопини теоремасы деп аталады, ол бағдарламалау тілі теориясының нәтижесі. Ол басқару ағыны графиктерінің класы (бұл жағдайда тарихи түрде блок-схемалар деп аталады) кіші бағдарламаларды тек үш нақты тәсілмен (бақылау құрылымдары) біріктірсе, кез келген есептелетін функцияны есептей алады. Бұл:
Бір кіші бағдарламаны орындап, содан кейін екінші кіші бағдарламаны орындау (тізбек)
Бульдік өрнектің мәніне сәйкес екі кіші бағдарламаның біреуін орындау (таңдау)
Бульдік өрнек шын болғанша кіші бағдарламаны қайталап орындау (итерация)

Осы шектеулерге, әсіресе бір шығуды білдіретін циклдық шектеуге (осы мақалада кейінірек сипатталғандай) қатысты, бастапқы бағдарламаның бағдарлама орны арқылы ұсынылған ақпаратын қадағалау үшін биттер түрінде қосымша айнымалыларды (түпнұсқа дәлелдемеде қосымша бүтін сандық айнымалыда сақталған) пайдалануға болады. Құрылыс Бёмнің P" бағдарламалау тіліне негізделген. Теорема құрылымдық бағдарламалаудың негізін құрайды, бұл бағдарламалау парадигмасы goto командаларынан бас тартып, тек кіші бағдарламаларды, тізбектерді, таңдау мен итерацияны қолданады.

Шығу тегі және нұсқалары

Теорема әдетте Дэвид Харелдің 1980 жылы жазған Böhm–Jacopini мақаласының "жалпыға танымал болғанын" және Клиниге жатқызылады.

Бём мен Якопини дәлелі

Бём мен Жакопинидің мақаласындағы дәлелдеу, ағын схемасының құрылымы бойынша индукция арқылы жүргізіледі. Бұл қайталанатын есептеулер саласындағы маңызды ұғым. Ол, кез келген есептеу қайтарымды бағдарлама арқылы орындала алса, оны тізбектер, таңдаулар және итерациялар сияқты басқару ағыны құрылымдарының құрылымдық комбинациясын пайдалана отырып, қайтарымды бағдарлама арқылы да орындауға болады деп жонекейді. Дәстүрлі, қайтарымсыз бағдарламамен орындалатын кез келген есептеуді қайтарымды бағдарлама арқылы да орындауға болады, бірақ әрбір қадамның қайтарымды болуы және қосымша шығыс болуы керек деген қосымша талаппен. Сонымен қатар, кез келген қайтарымсыз құрылымдалмаған бағдарламаны қосымша шығыссыз, тек бір итерацияны қолданатын құрылымдық қайтарымды бағдарлама арқылы да орындауға болады. Бұл теорема, құрылымдық бағдарламалау шеңберінде қайтарымды алгоритмдерді құрудың негізгі принциптерін қалыптастырады. Құрылымдық бағдарлама теоремасы үшін дәлелдеудің екі жергілікті әдісі белгілі. Дегенмен, оның қайтарымды нұсқасы үшін дәлелдеудің жаһандық әдісі танылса да, Бём мен Жакопини жасағанға ұқсас жергілікті тәсіл әлі белгісіз. Бұл айырмашылық, дәстүрлі есептеу парадигмаларымен салыстырғанда қайталанатын есептеудің негіздерін орнатудағы қиындықтар мен ерекшеліктерді көрсететін мысал.