סיבוכיות - Complexity
פרקי ההרצאה: סיבוכיות - Complexity
תמלול ההרצאה: סיבוכיות - Complexity
הטקסט המלא של הדקות הראשונות בהרצאה «סיבוכיות - Complexity» בקורס הווידאו של PracticU – כתוביות בעברית עם זמן התחלה לכל פסקה. כך תוכלו לקרוא ולחפש את הנושאים לפני שמתחילים ללמוד.
קומפלקסיטי סיבוכיות ההרצאה הזאת עוסקת במשהו שנקרא סיבוכיות שזה עוד איזשהו פרמטר שאפשר למדוד איתו או לעשות איתו ניהול סיכונים יש כל מיני סוגי סיבוכיות אנחנו נדבר על כמה סוגים אנחנו נדבר על סוג אחד ספציפי שאני חושב שהוא קל לממש אותו קל להבין אותו והוא נראה הוא מאוד ידידותי למשתמש נקרא לזה ככה הנושא הזה של סיבוכיות התקשר אלינו להרצאה
שם אנחנו נבוא ונראה איך עושים בדיקות מבוססות ניהול סיכונים. lesson objectives מטרות השיעור what is complexity אנחנו נדבר מה זה סיבוכיות מה היא באה למדוד מה היא באה לבדוק types of complexity methods נדבר על סוגי סיבוכיות בדגש על סיבוכיות סוג מסוים שנקרא cyclomatic complexity.
וואי סקלומטי קומפלקסיטי נדבר למה דווקא אנחנו בוחרים להתמקד בסיבוכיות בשיטת סיבוכיות הזאתי נדבר על סקלומטי קומפלקסיטי נדגים אותה נסביר אותה ואחרי זה יהיה מספר תרגילים שיבואו שתיתנו לכם את האפשרות להתנסות בלמדוד סקלומטי קומפלקסיטי מהי סיבוכיות?
The level of complication of a module or requirements סיבוכיות היא רמה של עד כמה מודול או דרישה הוא מסובך the greater the complexity of requirements the greater the risk is ככל שמודול הוא יותר מסובך או ככל שדרישה היא יותר מסובכת למימוש או יש בה יותר לוגיקה ככה היא תהיה יותר מסוכנת כי הסיכון הוא שבגלל הסיבוכיות בגלל
הפרובלמטיות לממש אותה הסיכון שלא נממש אותה כמו שצריך הוא יותר גדול יש הרבה סוגים של סיבוכיות מתמטיקה כל נושא הסיבוכיות הוא מעולם המתמטיקה מעולם הגרפים תורת הגרפים קשה מאוד או יחסית המדד למדידת סיבוכיות הוא קשה לעשות אותו לפני שיש קוד כתוב הרבה דברים הרבה רעיונות מהסיבוכיות מתבססים על זה שיש קוד כתוב כבר ממוכן וזה בעיה כי כי בסך הכל הרבה דברים או ניהול הסיכונים
צריך להתבסס גם על לפני שהקוד הכתוב, כי אם הקוד כבר נכתב אז הרבה דברים כבר מאוחר מדי להתכונן אליהם. measures that affect complexity מה הדברים שמשפיעים על סיבוכיות?
size, הגודל של הדרישה, הגודל של הקוד, control flow, איך אפשר, הזרימה, זרימת הנתונים, data structure, באיזה בסיס נתונים משתמשים, איך הדאטה שמור, איך המבנה של המודול module structure כמה איפים יש לו כמה קייסים יש לו כמה עצי החלטה מה גודל עץ ההחלטה וכדומה טייפס אוף קומפלקסיטי יש כמה סוגים אנחנו נדבר עליהם סייקלומטיק קומפלקסיטי
סיבוכיות סייקלומטית או מעגלית based on the number of decision in the software היא מבוססת על מספר ההחלטות או עץ ההחלטה של המודול או של הדרישה. All-State Complexity Algorithmic Complexity Counting the Operators + If and Operants זאת הסיבוכיות הזאת היא סיבוכיות אלגוריתמית היא סופרת את האופרטורים שאופרטורים זה סימנים
כמו חיבור חיסור פעולות חשבון if case while וכדומה ואופרנדים, אופרנדים זה חמש ה-string end לא הפעולה ה-logic end, הפעולה ה-logic end היא אופרטור וכדומה.
זאת סיבוכיות שאפשר למדוד אותה רק כשהתוכנה גמורה. יש תוכנות שסופרות את מספר האופרטורים, את מספר האופרנדים ומכניסות אותם לנוסחה של על סטייט קומפלקסיטי.
הנרין קפואה קומפלקסיטי זה coupling between modules using parameters, Global variables and function calls זה שיטה למדידת סיבוכיות שמתבססת על קשר זוגי בין מודולים פרמטרים משתנים משתנים גלובליים משתנים מקומיים קריאות לפונקציות וכדומה.
שוב גם זאת שיטה שאפשר למדוד אותה אפשר לעשות אותה רק כשהתוכנה גמורה שהכל כבר רשום הקודק רשום. There are many other types of complexity יש עוד הרבה סוגים של סיבוכיות.
We will talk only about cyclomatic complexity. אנחנו נתעסק רק בסייקלומטיק קומפלקסיטי או בסיבוכיות מעגלית. וואי סייקלומטיק קומפלקסיטי?
למה דווקא סייקלומטיק קומפלקסיטי? מה היתרונות שלו? מה החסרונות שלו? can be done before the code is written. אז אפשר לעשות אותה לפני שבכלל נכתב קוד.
למה? כי היא מתבססת על עץ החלטה, ועץ החלטה אפשר לצייר לפני שיש קוד. למעשה, אצל ההחלטה מתארגמים אחר כך לקוד דרר סטאדיז, טום מכבי, The show correlation between software cyclomatic complexity and its error frequency.
טום מכבי עשה מחקרים ויש עוד מחקרים נוספים שנעשו ב-MIT ובכל מיני ארגונים גדולים שמצאו קורלציה מאוד יפה ומאוד נכונה בין ה-cyclomatic complexity של תוכנה לבין מספר הטעויות שקרו בה או מספר הארורים.
או מבחינתנו זה גם כלומר שהדרישה לא התקיימה כמו שצריך. It can be used in the test plan itself אפשר להשתמש בסייקלומטי קומפלקסיטי בכל מה שקשור לטסט פלן. למה?
כי סייקלומטי קומפלקסיטי נותן לי את גודל עץ ההחלטה. מה שהוא למעשה ייתן לי זה כמה מסלולים מינימליים או מספר המסלולים המינימלי שאפשר לעבור בעץ החלטה.
to perform מאוד קל לממש אותו. The Cyclomatic Complexity אוקיי, סיבוכיות המעגלית מה היא למעשה? Measures the number of linear independent paths through a module.
Cyclomatic Complexity מודדת למעשה את מספר הקשרים הליניאריים או מספר הדרכים במודול. שמה זה אומר? זה אומר מספר הדרכים בעת החלטה. כמה דרכים יש לי להגיע לכדי החלטה בעת החלטה?
Give the result that be compared to other results. התוצאה שמקבלים הוא מספר, הוא מספר סופי. המספר הזה אפשר להשוות אותו למספרים אחרים ולכן הוא איזשהו פרמטר איכותי.
פרמטר טוב הוא פרמטר מדיד. The cyclomatic number specifies the minimum number of test cases required to traverse every basis path. המספר שאנחנו מקבלים, המספר הסופי של ה-cyclomatic complexity, חוץ מזה שהוא אומר לי עד כמה המודול או הדרישה או התוכנה מסובכת בהשוואה למספרים
אחרים שאחרי זה נסתכל עליהם זה גם המספר הזה בא ואומר לי כמה מה מספר הבדיקות המינימלי כדי להגיע לעבור על עץ ההחלטה שזה טוב כי זה נותן לנו את החסם התחתון כלומר את המינימום בדיקות שצריך כדי לבוא ולהגיד עברנו על כל עץ החלטה.
ברור שאפשר לעשות יותר אבל לא תמיד צריך לעשות יותר. Derived from Graph Theory כל הרעיון של Cyclomatic Complexity הוא נלקח מתורת הגרפים במתמטיקה ובמדעי המחשב, מדידת המסלולים הקצרים, מסלולים ארוכים וכדומה.
איך מחשבים את ה-Cyclomatic Complexity? ה-Cyclomatic Complexity שווה ל-e פחות n ועוד 2. e שווה ל-number of edges in the graph. אמרנו שיש לנו עץ החלטה, העץ החלטה הזה זה גרף.
הוא מורכב מקודקודים, מצמתים וקשתות. P מייצג את מספר הקשתות בגרף N שווה ל-number of nodes in the graph, מספר הצמתים בגרף ו-P ש-P זה 2 זה the number of connected components.
P מייצג את מספר הקומפוננטות המחוברות המקושרות בסייקלומטי קומפלקסיטי הוא תמיד 2 ולכן סייקלומטי קומפלקסיטי אחרי שציירנו את עץ ההחלטה ובדרך כלל עץ החלטה צריך לצייר אותו כדי לדעת לעבור עליו טוב יותר ולהבין אותו