1 of 38

רקורסיות

צביקה ברגר

תגבור אלגוריתמים

זיהוי משולשים

צביקה ברגר

בס"ד

2 of 38

כפל מטריצות

  •  

בס"ד

3 of 38

כפל מטריצות

  •  

בס"ד

4 of 38

כפל מטריצות

  • FMM כפל מטריצות מהיר (מהיר מוגדר כחזקה קטנה מ-3) -
  • BMM כפל מטריצות בוליאניות (כל איבר הוא 0 או 1) -

​

  • נשים לב שב-BMM ניתן להשתמש בנוסחה:

​

​

​

בס"ד

5 of 38

תזכורת: ייצוג גרף – מטריצת שכנויות

בס"ד

6 of 38

ייצוג גרף – רשימה מקושרת

בס"ד

7 of 38

סגור טרנזיטיבי של גרף

בס"ד

8 of 38

בעיית זיהוי משולשים

בס"ד

9 of 38

זיהוי משולש - FMM

בס"ד

10 of 38

אלגוריתמים קומבינטוריים

בס"ד

11 of 38

אלגוריתמים קומבינטוריים – זיהוי משולשים

בס"ד

12 of 38

אלגוריתמים קומבינטוריים – הוכחה

בס"ד

13 of 38

BMM בעזרת זיהוי משולשים - הגדרה

בס"ד

14 of 38

BMM בעזרת זיהוי משולשים - נאיבי

בס"ד

15 of 38

BMM בעזרת זיהוי משולשים - יעיל

בס"ד

16 of 38

מציאת משולש - שיעורי בית

בס"ד

17 of 38

מציאת משולש - פתרון

בס"ד

18 of 38

דיווח על כל המשולשים בגרף - תרגול

בס"ד

19 of 38

דיווח על כל המשולשים בגרף

בס"ד

20 of 38

דיווח על כל המשולשים בגרף

בס"ד

21 of 38

דיווח על כל המשולשים בגרף

בס"ד

22 of 38

דיווח על כל המשולשים בגרף

בס"ד

23 of 38

דיווח על כל המשולשים בגרף

בס"ד

24 of 38

בס"ד

נבדוק את כל שלשות הקשתות האפשריות

עבור כל קשת בסיס (u,v) נעבור על כל הקודקודים ונבדוק האם יש שני קשתות המחברות את הקשת (u,v) לאותו קודקוד

עבור כל קשת (u,v) נחשב את החיתוך בין שני הקבוצות השכנים של הקודקודים u,v. החיתוך יביא לנו את השכנים המשותפים לשני הקודקודים ולכן כל קודקוד בחיתוך יוצר משולש עם הקשת (u,v)

דיווח על כל המשולשים בגרף

 

25 of 38

Question 1

בס"ד

26 of 38

מבחן 2022 מועד א

בס"ד

27 of 38

פתרון

בס"ד

28 of 38

פתרון

בס"ד

29 of 38

Question 2

בס"ד

30 of 38

מבחן 2022 מועד ב

בס"ד

31 of 38

פתרון

בס"ד

32 of 38

Question 3

בס"ד

33 of 38

מבחן 2022 מועד ג

בס"ד

34 of 38

פתרון

בס"ד

35 of 38

Question 4

בס"ד

36 of 38

מבחן 2019 מועד א

בס"ד

37 of 38

פתרון

בס"ד

38 of 38

Question?

בס"ד