ДИСКРЕ́ТНАЯ МАТЕМА́ТИКА

ДИСКРЕ́ТНАЯ МАТЕМА́ТИКА, раз­дел ма­те­ма­ти­ки, изу­чаю­щий свой­ст­ва дис­крет­ных струк­тур, ко­то­рые воз­ни­ка­ют как в са­мой ма­те­ма­ти­ке, так и в её при­ло­же­ни­ях. При этом дис­крет­ны­ми струк­ту­ра­ми на­зы­ва­ют­ся объ­ек­ты, для ко­то­рых важ­ней­шие ха­рак­те­ри­сти­ки при­ни­ма­ют ко­неч­ное или счёт­ное чи­сло зна­че­ний. К чис­лу та­ких струк­тур от­но­сят­ся, напр., ко­неч­ные груп­пы, ко­неч­ные гра­фы, не­ко­то­рые ма­те­ма­тич. мо­де­ли пре­об­ра­зо­ва­те­лей ин­фор­ма­ции, ко­неч­ные ав­то­ма­ты, Тью­рин­га ма­ши­ны. Это при­ме­ры струк­тур фи­нит­но­го (ко­неч­но­го) ха­рак­те­ра. Часть Д. м., изу­чаю­щая их, ино­гда на­зы­ва­ет­ся ко­неч­ной ма­те­ма­ти­кой. По­ми­мо фи­нит­ных струк­тур, Д. м. изу­ча­ет так­же дис­крет­ные бес­ко­неч­ные струк­ту­ры (напр., бес­ко­неч­ные ал­геб­ра­ич. сис­те­мы, бес­ко­неч­ные гра­фы, бес­ко­неч­ные ав­то­ма­ты).

Предмет и методы дискретной математики

Зна­чит. часть клас­сич. ма­те­ма­ти­ки за­ни­ма­ет­ся изу­че­ни­ем свойств объ­ек­тов не­пре­рыв­но­го ха­рак­те­ра. Ис­поль­зо­ва­ние дис­крет­ной или не­пре­рыв­ной мо­де­ли изу­чае­мо­го объ­ек­та свя­за­но как с са­мим объ­ек­том, так и с тем, ка­кие за­да­чи ста­вит пе­ред со­бой ис­сле­до­ва­тель. Са­мо де­ле­ние ма­те­ма­ти­ки на Д. м. и ма­те­ма­ти­ку, за­ни­маю­щую­ся не­пре­рыв­ны­ми мо­де­ля­ми, в зна­чит. ме­ре ус­лов­но, по­сколь­ку, с од­ной сто­ро­ны, про­ис­хо­дит об­мен идея­ми и ме­то­да­ми ме­ж­ду ни­ми, а с дру­гой – час­то воз­ни­ка­ет не­об­хо­ди­мость ис­сле­до­ва­ния мо­де­лей, об­ла­­даю­щих как дис­крет­ны­ми, так и не­пре­рыв­ны­ми свой­ст­ва­ми од­но­вре­мен­но. В ма­те­ма­ти­ке су­ще­ст­ву­ют раз­де­лы, ис­поль­зую­щие сред­ст­ва Д. м. для изу­че­ния не­пре­рыв­ных мо­де­лей (напр., ал­геб­раи­че­ская гео­мет­рия), и на­обо­рот, час­то ме­то­ды, раз­ви­тые для ана­ли­за не­пре­рыв­ных мо­де­лей, ис­поль­зу­ют­ся при изу­че­нии дис­крет­ных струк­тур (напр., асим­пто­ти­че­ские ме­то­ды в тео­рии чи­сел, в пе­ре­чис­ли­тель­ных за­да­чах ком­би­на­то­ри­ки). Од­на­ко спе­ци­фи­ка мн. раз­де­лов Д. м. свя­за­на с не­об­хо­ди­мо­стью от­ка­за от та­ких фун­дам. по­ня­тий клас­сич. ма­те­ма­ти­ки, как пре­дел и не­пре­рыв­ность, в свя­зи с чем для мн. за­дач Д. м. не­ко­то­рые ме­то­ды клас­сич. ма­те­ма­ти­ки ока­зы­ва­ют­ся не­при­ме­ни­мы­ми.

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

Исторический очерк

Эле­мен­ты Д. м. воз­ник­ли в глу­бо­кой древ­но­сти; раз­ви­ва­ясь па­рал­лель­но с др. раз­де­ла­ми ма­те­ма­ти­ки, они яв­ля­лись их со­став­ной ча­стью. Ти­пич­ны­ми бы­ли за­да­чи, свя­зан­ные со свой­ст­ва­ми це­лых чи­сел, позд­нее эти за­да­чи при­ве­ли к соз­да­нию тео­рии чи­сел. При­ме­ры та­ких за­дач: оты­ска­ние ал­го­рит­мов сло­же­ния и ум­но­же­ния на­ту­раль­ных чи­сел у древ­них егип­тян, во­про­сы де­ли­мо­сти на­ту­раль­ных чи­сел и за­да­чи сум­ми­ро­ва­ния в пи­фа­го­рей­ской шко­ле, а в бо­лее позд­нее вре­мя – воп­ро­сы, свя­зан­ные с раз­ре­ши­мо­стью урав­не­ний в це­лых чис­лах. Этот этап раз­ви­тия Д. м. свя­зан с име­на­ми Дио­фан­та, Евли­да, Пифа­го­ра­ и Эрато­сфе­на­. В 17–18 вв., в осн. в свя­зи с иг­ро­вы­ми за­да­ча­ми, поя­ви­лись эле­мен­ты ком­би­на­тор­но­го ана­ли­за и дис­крет­ной тео­рии ве­ро­ят­но­стей, а в свя­зи с об­щи­ми про­бле­ма­ми тео­рии чи­сел, ал­геб­ры и гео­мет­рии в 18–19 вв. воз­ник­ли та­кие важ­ней­шие по­ня­тия ал­геб­ры, как груп­па, по­ле, коль­цо, оп­ре­де­лив­шие даль­ней­шее раз­ви­тие и со­дер­жа­ние ал­геб­ры и имев­шие, по су­ще­ст­ву, дис­крет­ную при­ро­ду. На про­тя­же­нии 17–19 вв. раз­ви­тие Д. м. свя­за­но с име­на­ми Н. Абеля­, Э. Варин­га­, У. Гамиль­то­на­, Э. Га­луа, А. Кэли­, Ж. Лаг­ран­жа, А. Лежан­дра­, П. Фер­ма, Л. Эйле­ра­. В 19–20 вв. стрем­ле­ние к стро­го­сти ма­те­ма­тич. рас­су­ж­де­ний и ана­лиз ме­то­дов ма­те­ма­ти­ки при­ве­ли к вы­де­ле­нию ещё од­но­го раз­де­ла – ма­те­ма­тич. ло­ги­ки. В это вре­мя проб­ле­ма­ми Д. м. за­ни­ма­лись Л. Брау­эр, Дж. Буль, Н. Винер­, К. Гёдель­, Д. Гиль­берт, А. Чёрч, К. Шеннон­. В со­з­да­нии рос. шко­лы Д. м. участ­во­ва­ли И. М. Вино­гра­дов­, А. Н. Колмо­го­ров­, О. Б. Лупа­нов­ и С. В. Яблон­ский­.

Современные задачи дискретной математики

В 20 в. раз­ви­тие Д. м. оп­ре­де­ля­лось гл. обр. за­про­са­ми прак­ти­ки. Воз­ник­ла но­вая нау­ка – ки­бер­не­ти­ка и её тео­ре­тич. часть – ма­те­ма­тич. ки­бер­не­ти­ка, изу­чаю­щая ма­те­ма­тич. ме­то­да­ми раз­но­об­раз­ные про­бле­мы, ко­то­рые ста­вит пе­ред ки­бер­не­ти­кой прак­тич. дея­тель­ность че­ло­ве­ка. Ма­те­ма­тич. ки­бер­не­ти­ка яв­ля­ет­ся по­став­щи­ком идей и за­дач Д. м. Так, при­клад­ные во­про­сы, тре­бую­щие боль­ших вы­чис­ле­ний, сти­му­ли­ро­ва­ли по­яв­ле­ние и раз­ви­тие чис­лен­ных ме­то­дов ре­ше­ния за­дач, что при­ве­ло к соз­да­нию вы­чис­ли­тель­ной ма­те­ма­ти­ки. Ана­лиз по­ня­тий «вы­чис­ли­мость» и «ал­го­ритм» при­вёл к соз­да­нию тео­рии ал­го­рит­мов. За­да­чи хра­не­ния, об­ра­бот­ки и пе­ре­да­чи ин­фор­ма­ции спо­соб­ст­во­ва­ли воз­ник­но­ве­нию ин­фор­ма­ции тео­рии, тео­рии ко­ди­ро­ва­ния и тео­ре­тич. крип­то­гра­фии. Эко­но­мич. за­да­чи, за­да­чи элек­тро­тех­ни­ки, рав­но как и внут­рен­ние про­бле­мы ма­те­ма­ти­ки, по­тре­бо­ва­ли раз­ви­тия тео­рии гра­фов. За­да­чи опи­са­ния ра­бо­ты и кон­ст­руи­ро­ва­ния слож­ных управ­ляю­щих сис­тем со­ста­ви­ли пред­мет тео­рии управ­ляю­щих сис­тем и тео­рии ав­то­ма­тов.

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

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