კომპიუტერულ მეცნიერებათა დეპარტამენტის სამეცნიერო სემინარი

2012 წლის 29 მარტს, 10 საათზე  კომპიუტერულ მეცნიერებათა დეპარტამენტში ჩატარდება სამეცნიერო სემინარი თემაზე:


მომხსენებელი:  პროფ. ა. გამყრელიძე.
მისამართი: თსუ  XI კორპუსი, აუდიტორია 204

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