დისკრეტული მათემატიკა

დისკრეტული მათემატიკა, მათემატიკის დარგი, რ-იც სხვადასხვა ტიპის დისკრეტული ხასიათის სტრუქტურებს შეისწავლის.

ტერმ. „დ. მ-ის" (ლათ. discretus – განცალკევებული, წყვეტილი) მაგივრად ხშირად იხმარება ტერმინები „სასრული მათემატიკა" და „კომბინატორული მათემატიკა". ცნება „კომბინატორული" დღევანდელი გაგებით პირველად გამოიყენა გერმ. მათემატიკოსმა და ფილოსოფოსმა გ. ვ. ლაიბნიცმა თავის ცნობილ ნაშრომში „Dissertatio de Arte Combinatoria" (გამოქვეყნდა 1666), რ-იც ზოგიერთ კონკრეტულ მათ. კომბინატორულ შედეგს და მრავალ ახალ, ძალზე მნიშვნელოვან იდეას შეიცავდა. თუმცა უნდა აღინიშნოს, რომ ცალკეული დისკრეტული, ანუ კომბინატორული ხასიათის მათ. შედეგი ლაიბნიცამდე გაცილებით უფრო ადრე იყო მიღებული.

მაგ., ჯერ კიდევ ძვ. საბერძნეთში მთელ (ნატურალურ) რიცხვთა ამა თუ იმ თვისებასთან დაკავშირებით შემუშავებული იყო ალგორითმული ხასიათის სხვადასხვა სასრული პროცედურა, რ-თა მეშვეობით შესაძლებელი იყო წინასწარ მოცემული ნატურალური რიცხვებიდან გამომდინარე, სათანადო ნატურალური რიცხვის მიღება. ერთ-ერთი ასეთი პროცედურაა ე. წ. ევკლიდეს ალგორითმი, რ-ის საშუალებით ნებისმიერი ორი ნატურალური რიცხვისათვის მოიძებნება მათი უდიდესი საერთო გამყოფი.

XVII ს-ში, სხვადასხვა გვარის აზარტულ თამაშებთან დაკავშირებით, წარმოიშვა ალბათობის თეორიის ელემენტები. ამ თეორიის მრავალი ამოცანის ამოხსნისას საჭირო იყო გარკვეულ კომბინატორულ თანაფარდობათა დადგენა, რაშიც მნიშვნელოვანი როლი შეასრულა ფრანგი მათემატიკოსების (ბ. პასკალი, პ. ფერმა და სხვ.) შრომებმა. მათ დაამტკიცეს ძირითადი კომბინატორული დამოკიდებულებები, რ-ებიც ასე თუ ისე დაკავშირებული იყო ნიუტონის ბინომის კოეფიციენტებთან. მსგავს დამოკიდებულებათა მოძებნა და დადგენა იმდროინდელი სასრული კომბინატორიკის ან კობმინატორული ანალიზის კვლევის ძირითადი საგანი იყო.

ანალოგიური კომბინატორული ხასიათის დამოკიდებულებები ბუნებრივად მიიღება რ ი ც ხ ვ თ ა  კ ლ ა ს ი კ უ რ ი  თ ე ო რ ი ი ს ზოგიერთი პრობლემის კვლევის დროსაც (განსაკუთრებით იმ საკითხების კვლევისას, რ-ებიც რ ი ც ხ ვ თ ა  ა დ ი ტ ი უ რ  თ ე ო რ ი ა ს განეკუთვნება). დ. მ-ის არე თანდათანობით ფართოვდებოდა, იზრდებოდა მისი გამოყენების სფეროც. ყველაფერი ეს ხდებოდა ტრად. მათ. დისციპლინებისა და დარგების განვითარების ფონზე. სწორედ ძვ. ტრად. მათ. დარგებში წარმოიქმნებოდა ახ. ცნებები და ყალიბდებოდა ახ. მეთოდები, რ-ებმაც შემდგომ ძირითადი ადგილი დაიკავა დ. მ-ში. მაგ., ნებისმიერი ხარისხის განტოლების რადიკალებში ამოხსნის წმინდა ალგებრულმა კლასიკურმა ამოცანამ წარმოშვა კომბინატორული მათემატიკისათვის ისეთი მნიშვნელოვანი კონცეფცია, როგორიცაა ჯგუფის ცნება (იხ. ჯგუფთა თეორია).

თავდაპირველად შემოღებულ იქნა სასრული სიმრავლის გადანაცვლებათა ჯგუფის ცნება. შემდგომ გაირკვა, რომ დ. მ-ში უმთავრესად სასრული ან სასრულად წარმოქმნილი ჯგუფები გამოიყენება. დ. მ-ის ზოგიერთი საკითხისათვის დიდი მნიშვნელობა აქვს აგრეთვე სხვა ტიპის ალგებრულ სტრუქტურებს, მაგ., სასრულ ველებს, სასრულად ან თვლადად წარმოქმნილ ნახევარჯგუფებს, სასრული ბაზისის მქონე ვექტორულ სივრცეებს, მატრიცების სხვადასხვა რგოლებს, ბულის ალგებრებს და ა.შ. მათ. ანალიზის, კერძოდ, უსასრულო ხარისხოვანი მწკრივების თეორიის განვითარებამ საშუალება მისცა ლ. ეილერს ჩამოეყალიბებინა კომბინატორული მათემატიკისათვის კვლევის ისეთი მძლავრი მეთოდი, როგორიცაა წ ა რ მ ო მ ქ მ ნ ე ლ ი ფ უ ნ ქ ც ი ე ბ ი ს მეთოდი.

ამ მიდგომის საშუალებით წარმატებით ამოიხსნა კომბინატორიკისა და კომბინატორული ანალიზის მრავალი რთული ამოცანა. აღსანიშნავია, რომ ამავე მეთოდის მეშვეობით ბევრ კონკრეტულ შემთხვევაში შესაძლებელია მოიძებნოს რეკურსიულად (ანუ რეკურენტულად) რიცხვთა მოცემული მიმდევრობის ზოგადი წევრის ერთიანი ფორმულა, რაც საგრძნობლად აადვილებს ასეთ მიმდევრობასთან დაკავშირებული კომბინატორული საკითხების გამოკვლევას (საკმარისია გავიხსენოთ ე. წ. ფიბონაჩის რიცხვთა მიმდევრობა).

გეომეტრიაში თვალსაჩინო კომბინატორული ხასიათის სტრუქტურების განხილვამ და შესწავლამ დასაბამი მისცა გრაფთა თეორიას, რ-იც ამჟამად დ. მ-ის ერთ-ერთი ძირითადი დარგია. გრაფთა თეორიაში პირველი ნაშრომი ლ. ეილერს ეკუთვნის (1736). ამოცანა, რ-საც ეილერი განიხილავდა, სასრულ გრაფებში გარკვეული თვისების მქონე მარშრუტების მოძებნას ეხებოდა. ეილერის შრომა მრავალწახნაგების შესახებ ფუნდამენტურ როლს ასრულებს მათ. სხვადასხვა დარგში. ამ შრომაში მიღებულმა ფორმულამ მისცა დასაბამი კომბინატორულ (ალგებრულ) ტოპოლოგიას, კომბინატორულ გეომეტრიას, მრავალწახნაგათა თანამედროვე თეორიას (მაგ., უფრო ზოგად ეილერ-პუანკარეს ფორმულას მაღალგანზომილებიანი ევკლიდური სივრცის ამოზნექილი მრავალწახნაგებისათვის).

გრაფთა თეორია რამდენიმე მიმართულებით ვითარდებოდა: განიხილებოდა სასრულ გრაფთა გადათვლის ამოცანები (მაგ., პოიას გრაფთა გადათვლის თეორემა); იკვლევდნენ სასრული გრაფების პლანარობის პირობებს (მაგ., კურატოვსკი–პონტრიაგინის გრაფის პლანარობის კრიტერიუმი); შეისწავლეს გრაფების სხვადასხვა მახასიათებელი და ინვარიანტი; განიხილეს გრაფების გაფერადების ამოცანები, გრაფების დანაწილებისა და ამორჩევის ამოცანები (მაგ., ფ. რამზის ცნობილი თეორემა); გრაფების სხვადასხვა ტიპის რეალიზაციის ამოცანები; ექსტრემალური პრობლემები, დაკავშირებული სასრული გრაფების ამა თუ იმ თვისებასთან და ა. შ. სიმრავლეთა ზოგადი თეორიის განვითარებამ დააკავშირა გრაფთა თეორია აბსტრაქტული ბინარული დამოკიდებულებების თეორიასთან, რის შედეგადაც შესაძლებელი გახდა გრაფებზე მრავალნაირი ოპერაციების შესწავლა (მაგ., გრაფების სუპერპოზიციის ოპერაციის განხილვა). ამავე დროს, სიმრავლურ-თეორიულმა მეთოდებმა ბიძგი მისცა უსასრულო გრაფების თეორიის წარმოქმნას და მის უაღრესად სწრაფ განვითარებას. ამ პროცესში ჩამოყალიბდა კომბინატორული მათ. სრულიად ახ. თანამედროვე დარგი, ე. წ. უსასრულო (ინფინიტური) კომბინატორიკა.

აღსანიშნავია, რომ წმინდა სიმრავლურ-თეორიული მიდგომა და უსასრულო კომბინატორიკის მეთოდები წარმატებით გამოიყენება სასრული კომბინატორიკის რთული ამოცანების ამოსახსნელად. დ. მ-ის ერთ-ერთი უმნიშვნელოვანესი კონცეფციაა ალგორითმის ცნება. მათემატიკაში სხვადასხვა გვარის ალგორითმული პროცედურა დიდი ხნის წინ იყო ცნობილი, მაგრამ ალგორითმის მათემატიკურად ზუსტი ცნება მხოლოდ ახლო წარსულში ჩამოყალიბდა, უპირველეს ყოვლისა, მათ. ლოგიკის მძლავრი განვითარების შედეგად. რამდენიმე ავტორმა (ა. ტიურინგი, ე. პოსტი, კ. გედელი, ა. მარკოვი, ა კოლმოგოროვი და სხვ.) მოგვცა ალგორითმის ზუსტი განსაზღვრება. მათ მიერ შემოღებული განსაზღვრებები ეკვივალენტური აღმოჩნდა, ასე რომ, ამჟამად ალგორითმის ცნებაში იგულისხმება როგორც ტიურინგის მანქანა, ასევე პოსტის მანქანა, გედელის ნაწილობრივი რეკურსიული ფუნქცია, მარკოვის ნორმალური ალგორითმი, აგრეთვე ალგორითმი (კომპლექსი) კოლმოგოროვის აზრით.

მათ. თითქმის ყველა სფეროში განიხილება ამა თუ იმ ტიპის ზოგადი ხასიათის ამოცანები, რ-თვისაც ბუნებრივად დაისმის კითხვა: არსებობს თუ არა ისეთი ალგორითმი, რ-ის საშუალებით მოცემული ზოგადი ამოცანა ბოლომდე ამოიხსნება? ამჟამად ცნობილია, რომ პასუხი შეიძლება იყოს როგორც დადებითი, ასევე უარყოფითი. დ. მ. ფაქტობრივად მოიცავს ისეთ დარგებს, როგორიცაა: ინფორმაციის თეორია, თამაშთა მათ. თეორია, დისკრეტული გეომეტრია, სასრულგანზომილებიანი ამოზნექილი ანალიზი, ფორმალური სისტემების თეორია და სხვ.

საქართველოში დ. მ-ის მიმართულებით ძირითადი სამუშაოები სრულდება თსუ-ის ი. ვეკუას სახ. გამოყენებითი მათემატიკის ინ-ტსა და კიბერნეტიკის ინ-ტში. კვლევის მთავარი მიმართულებებია: გრაფთა თეორია (როგორც სასრული, ასევე უსასრულო გრაფები), კომბინატორული და დისკრეტული გეომეტრია, ალგორითმთა (რეკურსიულ ფუნქციათა) თეორია, მათ. კიბერნეტიკისა და მათ. ლოგიკის სხვადასხვა საკითხი.

საყურადღებოა რეკურსიულ ფუნქციათა თეორიასა (რ. ომანაძე) და კომბინატორულ გეომეტრიაში მიღებული შედეგები სასრულგანზომილებიანი ევკლიდური სივრცის ამოზნექილი სხეულებისა და დისკრეტული წერტილოვანი სისტემების შესახებ (ა.ხარაზიშვილი, გ. ნიჟარაძე, თ. საჟენიუკი, ე. ბალაძე, ტ. ჭაბუკიანი). მიღებულია აგრეთვე ზოგიერთი შედეგი სიმრავლეთა უსასრულო კომბინატორიკაში (ა. ხარაზიშვილი, ა. ყიფიანი). ამასთან დაკავშირებით, აღსანიშნავია აგრეთვე ქართვ. მათემატიკოსთა გამოკვლევები მათ. ლოგიკისა და ალგორითმების თეორიის სხვადასხვა მიმართულებით.

ლიტ.: Б у р б а к и  Н., Теория множеств, пер. с франц., М., 1965; К е м е н и  Дж., С н е л л  Дж., Т о м п с о н  Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1964; Р и о р д а н  Дж., Введение в комбинаторный анализ, пер. с англ., М., 1963; Х а р а з и ш в и л и  А. Б., Элементы комбинаторной теории бесконечных множеств, Тб., 1981; მ ი ს ი ვ ე , Введение в комбинаторную геометрию, Тб., 1985; Х а р а р и Ф., Теория графов, пер. с англ., М., 1973; Я б л о н с к и й  С. В., Введение в дискретную математику, М., 1979.

ა. ხარაზიშვილი