თეორიული ინფორმატიკა - 1 - Finite Automata

დეტერმინისტული სასრული ავტომატები

საკითხავი მასალა 

1.1 Finite Automata (p. 31 – 47) 

(წიგნი: Introduction to the Theory of Computation (M. Sipser)) 

კალკულუს I-ის ლექციების სია

1)ფუნქციის ზღვარი, 1.1 – 1.3

2)უწყვეტობა, 1.4

3)ზღვრის ფორმალური განსაზღვრა, 1.5

4)წარმოებული, მხები, 2.2, 2.1

5)გაწარმოების წესები, 2.3

პირველი დავალება, 1.4 პარაგრაფის 1-7, 9, 13-23 კენტები, 22, 25, 29, 31, 33, 35.

1,2 და 3 ამოცანება არის g ფუნქციაზე, რომელის განსაზღვრის არეა [-2;2] და რომლის გრაფიც ნაჩვენებია სურათზე:

კალკულუსის დავალებების სია

1) 1.4 პარაგრაფის 1-7, 9, 13, 15, 17, 19, 21, 23, 22, 25, 29, 31, 33, 35.

ანონსი :D

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

ამოუხსნელი ამოცანები

ამათ უბრალოდ ჩემთვის ჩავინიშნავ, რომ არ გამომრჩეს რომელიმე

ლექცია 23, Sums & Asymptotics

 ეს ლექციაც ვიკადრე :)

ლექცია 20, Number Theory

1. აღწერეთ როგორ მოვახდინოთ ნებისმიერი კოდირებული მესიჯის (m*) დეკოდირება, თუ ვიცით ამის გაკეთება იმ შემთხვევისთვის, როცა m*=1. მითითება: ნახეთ მსჯელობა გვ. 294–ზე.

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

mფ = m*k (mod p)
 m * k *  k^(−1) =  m (mod p), ვინაიდან k *  k^(−1) = 1

გადავწეროთ:  m = mფ * k^(−1) (mod p).
როგორც ფერმამ დაგვიბარა: k^(-1) = k^(p-2).
 m = mფ * k^(p-2)
მოცემულობის თანახმად, ვიცით, რომ mფ = 1, ანუ m*k = 1 (mod p).
შესაბამისად:
m = k^(p-2).
აქედან გავიგეთ k^(p-2) (m ვიცოდით).
ზოგად mფ-ს ვპოულობთ მისი k^(p-2)-ზე გამრავლებით.
მადლობა ა.აზიზიანს დახმარებისთვის.

დისკრეტულის ლექციების სია

ამ პოსტში თავმოყრილია ყველა ლექციის ლინკი. პოსტების გადალაგება დაგვეზარა და...

ლექცია 21 Number theory, Arithmetic with an arbitrary modulus

1)დაასაბუთეთ, რომ φ(p^k)=p^k-p^(k-1), სადაც p ნებისმიერი მარტივი რიცხვია, ხოლო φ წარმოადგენს ეილერის ფუნქციას. 

ჯერ განვმარტოთ თუ რა არის φ(n), ანუ ეილერის ფუნქცია, ეილერის ფუნქცია n - ისთვის არის 1 დან n - მდე ყველა n - თან თანამარტივი რიცხვის რაოდენობა.

ჯერ 1 დან p^k-ს ჩათვლით სულ p^k რიცხვების სიმრავლე, რომელშიც სულ p^k ელემენტი იქნება. ამ სიმრავლეს ჩვენ უნდა გამოვაკლოთ ყველა ისეთი რიცხვი, რომელიც p^k - სთან თანამარტივი არაა, ეს რიცხვები იქნება:

1p;2p;3p;4p...........p^(k-1)p - ამ სიმრავლეში ელემენტების რაოდენობა იქნება p^(k-1), სულ კი p^k რიცხვი გვაქვს, შესაბამისად სხვაობაში გვექნება φ(p^k)=p^k-p^(k-1);

ლექცია 22 Number theory, RSA encryption

1)გაარჩიეთ RSA ალგორითი 303 გვერდზე და ახსენით რა
განაპირობებს საიდუმლო გასაღების საიდუმლოებას?
RSA ალგორითმი შედგება 4 ეტაპისგან:

1. ვაგენერირებთ ორ დიდ მარტივ რიცხვს p და q.
2. შემდეგ ამ ორ რიცხვს ვამრავლებთ და ვარქმევთ n-ს; n=pq;
3. ვარჩევთ ისეთ მთელ რიცხვს e-ს რომელიც ურთიერთმარტივია φ(n)-თან, შესაბამისად gcd(e,φ(n))=1; ეილერის ფუნქციის თანახმად φ(n)=φ(pq)=φ(p)*φ(q), რადგანაც p და q მარტივი რიცხვებია, შესაბამისად φ(p)=(p-1), იგივეა q-სთვისაც და შესაბამისად φ(n)=(p-1)(q-1) - აქ გავეცით პასუხი მეორე კითხვას; შესაბამისად gcd(e,(p-1)(q-1))=1; შემდეგ ჩვენ ვარქმევთ e - სა და n - ის წყვილს public key-ს, რომლის მფლობელიც შეიძლება იყოს ნებისმიერი ადამიანი.
4. ახლა ვაგენერირებთ ისეთ მთელ რიცხვ d - ს, რომ de = 1 mod(φ(n)); მთელი catch ისაა, რომ de შეიძლება წარმოვადგინოთ, როგორც φ(n)*t+1 სადაც t რაღაც მთელი რიცხვია.

ლექცია 25, Counting

problem 16.14

დავუშვათ 2 იგენტური 52 კარტიანი დასტა არეულია ერთმანეთში. რამდენგვარად შეგვიძლია 2 დასტად დავყოთ.

პასუხი:
104!/2^52. ახლა რატომ. 104! აღნიშნავს თანმიმდევრობას ამ კარტებისა. ვინაიდან გვაქვს 2-2 ერთნაირი კარტი, რომელთა ადგილების გაცვლა არაფერს არ ცვლის, გამოდის, რომ 2^52 ვარიანტია კარტების გადაადგილების ისე, რომ არაფერი არ შეიცვალოს. ჯამში 52 ასეთი წყვილია.

                  -by RatMatch

ლექცია 24, Counting

ამოცანა 12 ცალ დონათზე

გვინდა 12 დონათის ყიდვა. არის 5 სახეობა. რამდენნაირად შეგვიძლია ავირჩიოთ.

ავიღოთ 12 ყუთი და 4 გამომყოფი. გამოდის 16!/(4!*12!)
მოიდთ ამას ცოტა განვავრცობ. 12 დონათი რომ ვიყიდოთ, უნდა შევქმანთ "საზღვრები" ერთი სახის დონათებს შორის. ეს საზღვრები უნდა იყოს 4 ცალი, რომ 12 დონათი 5 ნაწილად დაიყოს. ხოლო ეს ფორმულა გვეუბნება, რამდენი ვარიანტია ამ 4 საზღვრის ჩასმის.

ლექცია 19, რიცხვთა თეორია

1. რიცხვი იდეალურია, თუ იგი ტოლია თავისი გამყოფების (თავისი თავის გარდა) ჯამის. მაგალითად, 6 იდეალურია, რადგან 6 = 1+2+3. ასევე, 28 იდეალურია, რადგან 28 = 1+2+4+7+14. ახსენით, რატომ იქნება 2^(k−1) * (2^k −1) იდეალური, როცა 2^k −1 მარტივია.

თუ 2^k-1 მარტივია, მაშინ 2^(k−1) * (2^k −1)-ის ერთადერთი გამყოფებია:

• 1, 2, 4, ... , 2^(k-1), რაც ჯამში ტოლია 2^k-1 -ის, და~
• 1*(2^k −1), 2*(2^k −1), 4*(2^k −1), ..... , 2^(k-2) * (2^k - 1), რაც ჯამში არის (2^(k-1) - 1) * (2^k - 1)

ამ ორის შეკრებით მიიღება 2^(k−1) * (2^k −1), ანუ რიცხვი იდეალურია.

ლექცია 18, ბრტყელი გრაფები

Planer graphs
1. რა რეზულტატს გვაძლევს ეილერის თეორემა (ბმული ბრტყელი გრაფების შესახებ), თუ გრაფი წარმოადგენს ხეს?

v-e+f=2 - ეილერის თეორემა. თუ გრაფი ხეა, f=1 და:
v-e=1

ლექცია 17, Recursive data types

Problem 11.3 (a,b)

Here is a simple recursive definition of the set, E, of even integers:
Definition. Base case: 0 ∈ E.
                Constructor cases: If n ∈ E, then so are n +2 and −n.
Provide similar simple recursive definitions of the following sets:
(a)
The set S ::= {2^k*3^m*5^n | k,m,n ∈ N} .

• 1∈S
• თუ n∈S, მაშინ 2*n, 3*n და 5*n ეკუთვნის S-ს.

(b)
The set T ::= {2^k*3^(2*k+m)*5^(m+n) | k,m,n ∈ N} .

• 1 ∈ S 
• თუ n ∈ S, მაშინ 18n, 15n, და 5n ეკუთვნის S-ს.

ლექცია 16, bipartite matchings

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

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

ახლა ვაჩვენოთ, რომ თუ პირობა სრულდება, გვაქვს დაწყვილება. წიყენებთ ინდუქციას |G|-ზე, გოგოების რაოდენობაზე.

Base Case: თუ |G| =1, მაშინ პირობის მიხედვით, მას ერთი ბიჭი მაინც მოსწონს, ანუ დაწყვილება არსებობს.

ინდუქციური ბიჯი: დავუშვათ |G|≥ 2. არის ორი ვარიანტი:

ვარიანტი 1: გოგოები ყოველ ქვესიმრავლეს მოსწონს ბიჭების მკაცრად დიდი ქვესიმრავლე. ამ შემთხვევაში ასე ვიქცევით: რომელიმე გოგოს ვაწყვილებთ ბიჭთან, რომელიც მას მოსწონს და ორივეს "ვუშვებთ". დარჩენილ ხალხზე ჩვენი პირობა მაინც სრულდება და დანარჩენ გოგოებს ინდუქციურად ვაწყვილებთ.

ვარიანტი 2: გოგოების რომელიმე ქვესიმრავლე X ⊂ G მოსწონს ტოლი რაოდენობის ბიჭი - Y ⊂ B. გოგოებს X-იდან ინდუქციურად ვაწყვილებთ Y-ის ბიჭებთან და "ვუშვებთ" მათ. დანარჩენი გოგოებიც შეგვიძლია ინდუქციურად დავაწყვილოთ, თუ ვაჩვენებთ რომ პირობა სრულდება. ამისათვის განვიხილოთ დარჩენილი გოგოების ზოგადი ქვესიმრავლე - X' ⊆ (G − X), ხოლო Y' იყოს მათ მიერ მოწონებული ბიჭების სიმრავლე. უნდა ვაჩვენოთ, რომ |X'|≤|Y'|. თავდაპირველად, X ∪ X'-ს გოგოებს მოსწონდათ Y ∪ Y'-ის ბიჭები. ასე რომ, პირობის თანახმად:

|X ∪ X'|≤|Y ∪ Y'| 

გავუშვით |X| გოგო მარცხენა სიმრავლიდან (დარჩა X') და მაგდენივე ბიჭი გავუშვით მარჯვენიდან (დარჩა Y'). მაშასადამე |X'|≤|Y '|, რისი დამტკიცებაც გვინდოდა.
ასე რომ, ორივე ვარიანტში შეგვიძლია გოგოები დავაწყვილოთ.

ლექცია 12, მარტივი გრაფები, ხარისხები, იზომორფიზმი

Problem 10.1 (a,b)

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

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

ბ) დაასკვენით, რომ წვეულებაზე სადაც ხალხი ერთმანეთს ხელს ართმევა, ისეთი ხალხის რაოდენობა, რომლებმაც კენტჯერ ჩამოართვეს ხელი, ლუწია.

ადამიანი ავღნიშნოთ წვეროთი, ხელისჩამორთმევა - წიბოთი და წინა ამოცანაზე დავდივართ.

ლექცია 11, stable marriage

Problem 9.14

a) სტუდენტები იყვნენ ბიჭები, კომპანიები - გოგოები. 2 განსხვავებული დაწყვილების საპოვნელად გამოიყენეთ ტრადიციული და არატრადიციული რიტუალები.

b)თუ ტრადიციული და არატრადიციული მეთოდები ერთნაირ დაწყვილებებს მოგვცემენ, გამოდის რომ ერთადერთი სტაბილური დაწყვილება გვაქვს, თუ არადა, არა :)

ლექცია 15, Coloring

 Problem 10.19

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