Verbum

АЛГАРЫ́ТМАЎ ТЭО́РЫЯ,

раздзел матэматыкі, які вывучае агульныя ўласцівасці алгарытмаў; тэарэт. аснова кібернетыкі, вылічальнай матэматыкі.

У інтуітыўным паняцці алгарытмы выкарыстоўваліся ў матэматыцы на працягу яе існавання. Дакладнае паняцце алгарытму сфарміравалася ў пач. 20 ст. і ўпершыню з’явілася ў працах матэматыкаў франц. Э.Барэля (1912) і ням. Г.Вейля (1921). Сістэматычная распрацоўка алгарытмаў тэорыі пачалася ў 1936, калі амер. матэматык А.Чэрч удакладніў паняцце алгарытмічна вылічальнай функцыі і прывёў прыклад невыліч. функцыі, англ. А.Цьюрынг і амер. Э.Пост удакладнілі паняцце алгарытму ў тэрмінах ідэалізаваных выліч. машын (машыны Цьюрынга—Поста); сав. матэматык А.М.Калмагораў прапанаваў выкарыстанне алгарытмаў тэорыі для абгрунтавання інфармацыі тэорыі (1965).

Адзін з гал. Кірункаў алгарытмаў тэорыі — вывучэнне невырашальнасці (вырашальнасці) алгарытмічных праблем, напр., у самой алгарытмаў тэорыі — праблема спынення універсальнай машыны Цьюрынга; у матэм. логіцы — праблема распазнавання тоесна праўдзівых формул злічэння прэдыкатаў 1-й ступені; у алгебры — праблема тоеснасці для паўгруп; у тапалогіі — праблема гомеамарфізму; у тэорыі лікаў — 10-я праблема Д.Гільберта. Даследаванні прывялі да ўзнікнення паняцця ступені невырашальнасці, вывучэння адпаведных матэм. структур і паказалі, што алгарытмічныя праблемы невырашальнасці маюць найб. ступень.

Літ.:

Мальцев А.И. Алгоритмы и рекурсивные функции. 2 изд. М., 1986;

Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М., 1980.

Р.Т.Вальвачоў.

т. 1, с. 233

ДВАЙКО́ВАЯ СІСТЭ́МА ЛІЧЭ́ННЯ,

пазіцыйная сістэма лічэння з асновай 2. Мае толькі 2 знакі — лічбы 0 i 1. Лік 2 лічыцца адзінкай 2-га разраду і запісваецца ў выглядзе 10 (чытаецца: «адзін—нуль»), лік 4—3-га разраду і запісваецца як 100 і г.д. Кожная адзінка наступнага разраду ўдвая большая за папярэднюю. Каб лік, запісаны ў дзесятковай сістэме лічэння, запісаць у Д.сл., яго выражаюць праз ступені ліку 2, напр., 45₁₀ = 1∙2​⁵ + 0∙2​⁴ + 1∙2​³ + 1∙2​² + 0∙2​¹ + 1∙2​⁰ = 101101₂. Выкарыстоўваецца ў тэарэт. пытаннях і для апрацоўкі інфармацыі на лічбавых ЭВМ (уваходныя і выхадныя даныя прадстаўляюць у дзесятковай сістэме лічэння).

У Д.с.л. найб. проста выконваюцца ўсе арыфм. дзеянні, напр., табліца множання зводзіцца да роўнасці 11 = 1. Аднак гэта сістэма нязручная з-за грувасткага запісу лікаў, напр., лік 9000 у Д.с.л. будзе 14-разрадным. Каб скараціць даўжыню запісаў праграм для ЭВМ, кожныя 3 ці 4 двайковыя лічбы замяняюць адным сімвалам (з алфавіта 0, 1, ..., 7 або 0, 1, ..., 9, A B, C, D, E, F адпаведна) і атрымліваюць запіс у васьмярковай ці шаснаццатковай сістэме лічэння. Гл. таксама Лічэнне.

М.П.Савік.

т. 6, с. 73

ДЗЕСЯТКО́ВАЯ СІСТЭ́МА ЛІЧЭ́ННЯ,

найбольш пашыраная пазіцыйная сістэма лічэння з асновай 10. Мае 10 сімвалаў — лічбы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Мяркуюць, што выбар у якасці асновы ліку 10 бярэ пачатак ад лічэння на пальцах. Узнікла на аснове нумарацыі, якая зарадзілася ў Індыі ў 5 ст., назву арабскай атрымала таму, што ў Еўропе з ёй пазнаёміліся ў 10—12 ст. па лац. перакладах з араб. мовы; у Расіі Дз.с.л. пачала пашырацца з 17 ст.

Пазіцыйны прынцып Дз.с.л. азначае, што адзін і той жа знак (лічба) мае розныя значэнні ў залежнасці ад таго месца, на якім ён стаіць, і таму асобныя сімвалы патрэбныя толькі пры запісе першых 10 лікаў. Лік 10 (аснова Дз.с.л.) утварае адзінку 2-га разраду, 10 адзінак 2-га разраду (лік 100 = 10​²) — адзінку 3-га разраду і г.д. (адзінка кожнага наступнага разраду ў 10 разоў большая за адзінку папярэдняга). Для запісу ліку ў Дз.с.л. выяўляюць колькасць адзінак найвышэйшага разраду, потым у астачы — колькасць адзінак разраду, на 1 меншага, і г.д. Атрыманыя лічбы запісваюць побач. напр.. 4 · 10​² + 7 · 10 + 3 · 10° = 473. Гл. таксама Лічэнне.

М.П.Савік.

т. 6, с. 107

ВЕ́КТАР

(ад лац. vector вядучы, нясучы),

1) накіраваны адрэзак пэўнай даўжыні. Абазначаецца лац. літарамі тлустага шрыфту a, A (AB — калі пачатак вектара ў пункце A, канец у пункце B) ці светлага шрыфту з рыскай або стрэлкай над імі: a̅, $\overrightarrow{\mathrm{a}}$, A̅B̅, A$\overrightarrow{\mathrm{B}}$. Даўжынёй (модулем) вектара наз. даўжыня адрэзка AB і абазначаецца AB ці |A$\overrightarrow{\mathrm{B}}$|.

Два вектары роўныя, калі яны паралельныя ці аднолькава накіраваныя і маюць аднолькавую даўжыню. Вектар, пачатак і канец якога супадаюць, наз. нуль-вектарам, даўжыня яго роўная нулю. Яму не прыпісваецца ніякі напрамак. Вектар, даўж. якога роўная адзінцы, наз. адзінкавым. На плоскасці ці ў прасторы ўсякі вектар можа быць паказаны накіраваным адрэзкам, адкладзеным ад пачатку каардынат. Таму вектар можна задаваць трыма сапраўднымі лікамі (x, y, z) — праекцыямі вектара на восі прамавугольнай сістэмы каардынат (каардынатамі вектара). У n-мернай прасторы вектар вызначаецца як упарадкаваная сістэма n сапраўдных лікаў (x₁, x₂, ..., x_n).

З дапамогай вектара ў матэматыцы, фізіцы і механіцы апісваюцца сілы, скорасці, паскарэнні і інш. велічыні, зададзеныя лікам і напрамкам. Гл. таксама Вектарнае злічэнне.

2) У пераносным сэнсе — пэўны кірунак у якой-н. сферы дзейнасці ці адносін (напр., у палітыцы, эканоміцы і г.д.).

А.А.Гусак.

т. 4, с. 63

А́ЛГЕБРА,

навука пра сістэмы аб’ектаў той ці інш. прыроды, у якіх устаноўлены аперацыі, па сваіх уласцівасцях падобныя на складанне і множанне лікаў (алг. аперацыі). Задачы і метады алгебры ствараліся паступова, у выніку пошукаў агульных прыёмаў рашэння аднатыпных арыфм. задач (пераважна састаўлення і рашэння ўраўненняў).

Вялікі ўплыў на развіццё алг. ідэй і сімволікі зрабіла «Арыфметыка» Дыяфанта (3 ст.). Тэрмін «алгебра» паходзіць ад назвы твора Мухамеда аль-Харэзмі «Альджэбр аль-мукабала» (9 ст.), які мае агульныя метады рашэння алгебраічных ураўненняў (АУ) 1-й і 2-й ступеняў. У канцы 15 ст. замест грувасткіх слоўных апісанняў алг. дзеянняў у матэм. творах з’яўляюцца знакі «+» і «-», потым знакі ступеняў, кораняў, дужкі. У канцы 16 ст. Ф.Віет першы выкарыстаў літарныя абазначэнні. Да сярэдзіны 17 ст. ў асн. склалася сучасная алг. сімволіка. У далейшым погляд на алгебру мяняўся. Алгебра 17—18 ст. займалася літарнымі вылічэннямі (рашэнне АУ, тоеснае пераўтварэнне формул і інш.) у адрозненне ад арыфметыкі, якая аперыруе канкрэтнымі лікамі. Да сярэдзіны 18 ст. алгебра склалася прыблізна ў аб’ёме цяперашняй т.зв. элементарнай алгебры. Алгебра 18—19 ст. з’яўляецца ў асн. алгебрай мнагачленаў. Першай гіст. задачай алгебры было рашэнне АУ з адным невядомым. У 16 ст. італьян. матэматыкамі была знойдзена формула для рашэння ўраўненняў 3-й ступені (формула Кардана), потым метад рашэння ўраўненняў 4-й ступені (метад Ферары). Амаль 3 стагоддзі вёўся пошук формулы для рашэння ўраўненняў вышэйшай ступені. У 17 ст. ўпершыню выказана А.Жырарам, а ў канцы 18 ст. К.Гаўсам даказана асн. тэарэма алгебры аб існаванні камплекснага кораня для адвольных АУ з камплекснымі каэфіцыентамі. У 1824 Н.Абель даказаў, што ўраўненне вышэй 4-й ступені ў агульным выпадку ў радыкалах невырашальнае, а ў 1830 Э.Галуа знайшоў крытэрый вырашальнасці ў радыкалах АУ. Разам з тэарэмай АУ з адным невядомым разглядаліся сістэмы АУ з многімі невядомымі, у прыватнасці сістэмы лінейных ураўненняў, у сувязі з чым узніклі паняцці матрыцы і дэтэрмінанта. З сярэдзіны 19 ст. даследаванні ў алгебры паступова пераносяцца з тэорыі АУ да вывучэння адвольных алг. аперацый. Абстрактнае паняцце алг. аперацыі ўзнікла ў сярэдзіне 19 ст. ў сувязі з даследаваннем прыроды камплексных лікаў, а таксама ў выніку з’яўлення прыкладаў алг. аперацый над элементамі зусім інш. прыроды, чым лікі, — складанне і множанне матрыц і інш.

У пачатку 20 ст. алгебра стала разглядацца як агульная тэорыя алг. аперацый на аснове аксіяматычнага метаду (сфарміравалася пад уплывам прац Ц.Гільберта, Э.Штэйніца, Э.Арціна, Э.Нётэр і інш.). Сучасная алгебра вывучае мноствы адвольнай прыроды з зададзенымі на іх алг. аперацыямі (г.зн. алгебра ці універсальныя алгебра). Доўгі час вывучаліся толькі некалькі тыпаў універсальных алгебраў — групы, кольцы, лінейныя прасторы. Пазней пачалося вывучэнне абагульненняў паняцця групы — паўгрупы, квазігрупы і лупы. Разам з асацыятыўнымі кольцамі і алгебрай пачалі вывучацца і неасацыятыўныя кольцы і алгебра. Асацыятыўна-камутатыўныя кольцы і палі з’яўляюцца асн. аб’ектам вывучэння камутатыўнай алгебры, з якой цесна звязана алгебраічная геаметрыя. Важным тыпам алгебры з’яўляюцца структуры. Лінейныя прасторы, модулі, а таксама іх лінейныя пераўтварэнні і сумежныя пытанні вывучае лінейная алгебра, часткай якой з’яўляюцца тэорыі лінейных ураўненняў і матрыц. Да лінейнай алгебры прымыкае полілінейная алгебра. Першыя працы па агульнай тэорыі адвольных універсальных алгебраў належаць Г.Біркгафу (1830-я г.). У тыя ж гады А.І.Мальцаў і А.Тарскі заклалі асновы тэорыі мадэляў — мностваў з зададзенымі на іх адносінамі. У выніку цеснага збліжэння тэорыі універсальных алгебраў з тэорыяй мадэляў узнік новы раздзел алгебры, сумежны з алгебрай і матэматычнай логікай, — тэорыя алг. сістэм, якая вывучае мноствы з зададзенымі на іх алг. аперацыямі і адносінамі (гл. Алгебра логікі). Дысцыпліны, сумежныя з алгебрай і інш. часткамі матэматыкі, вызначаюцца ўнясеннем ва універсальныя алгебры дадатковых структур, узгодненых з алг. аперацыямі і адносінамі: тапалагічная алгебра, у т. л. тапалагічныя групы і групы Лі, тэорыя ўнармаваных кольцаў, дыферэнцыяльная алгебра, тэорыі розных упарадкаваных алгебраў. Да сярэдзіны 1950-х г. сфарміравалася гамалагічная алгебра, карані якой ляжаць у алгебры і тапалогіі.

Алг. паняцці і метады выкарыстоўваюцца ў геаметрыі, тэорыі лікаў, функцыян. аналізе, тэорыі дыферэнцыяльных ураўненняў, метадах вылічэнняў і інш. Алгебра мае вял. дачыненне да фізікі (выяўленні груп у квантавай фізіцы), крышталяграфіі (дыскрэтныя групы), кібернетыкі (тэорыі аўтаматаў і кадзіравання), матэм. эканомікі (лінейныя няроўнасці) і інш. Сістэм. даследаванні па алгебры на Беларусі пачалі Дз.А.Супруненка (1945) і С.А.Чуніхін (1953). Вядуцца пераважна ў Ін-це матэматыкі АН Беларусі, БДУ, Гомельскім ун-це ў школах У.П.Платонава, А.Я.Залескага, Л.А.Шамяткова.

Літ.:

Математика, её содержание, методы и значение. Т. 1—3. М., 1956;

Бурбаки Н. Очерки по истории математики: Пер. с фр. М., 1963.

Р.Т.Вальвачоў.

т. 1, с. 233

ГРА́ФАЎ ТЭО́РЫЯ,

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

Першыя задачы графаў тэорыі былі звязаны з рашэннем галаваломак і матэм. забаўляльных задач (напр., задачы аб Кёнігсбергскіх мастах, аб расстаноўцы ферзей на шахматнай дошцы, аб перавозках, кругасветным падарожжы, задача 4 фарбаў і інш.). Адным з першых вынікаў у графаў тэорыі быў крытэрый існавання абходу графа без паўтораў рэбраў (Л.Эйлер, 1736). У 19 ст. з’явіліся работы, у якіх пры рашэнні практычных задач атрыманы важныя вынікі ў графаў тэорыі (задачы пабудавання эл. ланцугоў, падліку хім. рэчываў з рознымі тыпамі малекулярных злучэнняў і інш.). У 20 ст. задачы, звязаныя з графамі, з’явіліся ў тапалогіі, алгебры, тэорыі лікаў, тэорыі імавернасці і інш. Найб. развіццё графаў тэорыя атрымала з 1950-х г. у сувязі са станаўленнем кібернетыкі і развіццём выліч. тэхнікі.

На Беларусі даследаванні па графаў тэорыі вядуцца ў БДУ (уплыў розных параметраў на ўласцівасці графаў), Ін-це матэматыкі (розныя прадстаўленні графаў, алгарытмічныя аспекты графаў тэорыі), Ін-це тэхн. кібернетыкі (графы ў задачах аптымальнага ўпарадкавання) Нац. АН.

Літ.:

Лекции по теории графов. М., 1990.

Ю.Н.Сацкоў.

т. 5, с. 411

ГРАФІ́ЧНЫЯ ВЫЛІЧЭ́ННІ,

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

Лікі пры графічных вылічэннях алг. выразаў адлюстроўваюцца ў выбраным маштабе накіраванымі адрэзкамі. Пры графічным складанні і адніманні лікаў адпаведныя адрэзкі адкладваюць на прамой у пэўным (аднімаемае — у процілеглым) напрамку адзін за адным так, каб пачатак наступнага адрэзка супадаў з канцом папярэдняга. Сума (рознасць) — адрэзак, пачатак якога супадае з пачаткам 1-га, а канец — з канцом апошняга. Множанне і дзяленне ажыццяўляюцца будаваннем прапарцыянальных адрэзкаў, што адсякаюць на старанах вугла паралельныя прамыя, і выкарыстаннем адпаведных дачыненняў. Для графічнага ўзвядзення ў цэлую дадатную (адмоўную) ступень паслядоўна паўтараюць множанне (дзяленне). Для графічнага рашэння ўраўнення $𝑓\text{(}x\text{)}$ = 0 будуюць графік функцыі у = $𝑓\text{(}x\text{)}$ і знаходзяць яго пункты перасячэння з воссю абсцыс [пры рашэнні ўраўненняў 𝑓₁(x) = 𝑓₂(x) знаходзяць абсцысы пунктаў перасячэння крывых y₁ = 𝑓₁(x) і y₂ = 𝑓₂(x)]. Графічнае вылічэнне вызначанага інтэграла заснавана на замене графіка падінтэгральнай функцыі ступеньчатай ломанай, плошча пад якой лікава роўная дадзенаму інтэгралу. Для графічнага дыферэнцыравання будуецца графік вытворнай па значэннях тангенса вугла нахілу датычнай у розных пунктах графіка дадзенай функцыі. Графічнае рашэнне дыферэнцыяльнага ўраўнення dy/dx = 𝑓(x,y) зводзіцца да будавання поля напрамкаў на плоскасці: у некаторых пунктах малююць напрамкі датычнай dy/dx да інтэгральнай крывой, што праходзіць праз іх. Шуканую крывую праводзяць так, каб датычныя да яе мелі зададзеныя напрамкі. Часта папярэдне будуюць сям’ю ліній 𝑓(x,y) = C (ізаклінаў) для розных значэнняў C. У кожным пункце такой лініі вытворная пастаянная і роўная C. Гл. таксама Лікавыя метады, Набліжанае вылічэнне, Набліжанае інтэграванне.

С.У.Абламейка.

т. 5, с. 415