[השמעת מוסיקה] 

1 SPEAKER: בסדר, זה CS50, וזה הוא ההתחלה של שבוע ארבעה, וכפי שאולי שמעו או לקרוא, העולם כבר הסתיים. הולך בכל רחבי האינטרנט יש לו ידע ומודעות היו של באג בתכנית, שפת תכנות בשם Bash. זה כבר ממותג להפליא כShellshock, או דלת Bash, אבל מאמרים כמו אלה לא היה נדיר. ואכן, רבים מהם להביא זכרונות האחוריים של Heartbleed, שאולי שמתו לב ב לחץ חזרה באביב האחרון, ש היה דומה למדי דרמטי. עכשיו של אלו מכם כאן היום, כמה מכם יש לי, גם אם אתה לא מבין את מה ש זה הכול העניין של, שמע על Shellshock? בסדר, וכמה מכם יש להם מחשבים שהם פגיעים? אישור, לא צריך להיות הרבה, הרבה יותר ידיים עד עכשיו, מסיבות שנראה. 

בואו נסתכל על מה נמשך בתקשורת ולאחר מכן להסביר את זה קצת כאן לנו מבחינה טכנית. 

SPEAKER 2: יש לי מומחי אבטחה הזהיר כי יכל פגם חמור להיות על מנת להשפיע על מאות מיליון של משתמשי האינטרנט בעולם. אז מה הוא באג שהיה בדיוק כינוי Shellshock, ומה הוא עושה? ובכן, Shellshock ידוע גם בשם באג Bash, תוכנה זה מנצל. האקרים משתמשים הווירוס לסריקה פגיע מערכות הפעלה לינוקס ויוניקס מערכות הפעלה ולאחר מכן להדביק אותם. Bash הוא מעטפת שורת הפקודה. זה מאפשר לי נושא משתמשי פקודות להשיק תוכניות ותכונות בתוכנה על ידי הקלדת טקסט. זה משמש בדרך כלל על ידי מתכנתים, ו לא צריך להיות פתוח לעולם הרחב יותר, למרות Shellshock משנה ש. 

ובכן, worringly, כמה אנליסטים להזהיר שזה יכול להיות איום גדול יותר, בגלל Shellshock מאפשר מלא שליטה של ​​מכונה נגועה, ואילו Heartbleed מותר רק האקרים כדי לרגל במחשבים. זה כל כך רציני, זה דורג 10 מתוך 10 לחומרה על ידי הלאומי מסד נתוני פגיעות. 2/3 של כל שרתי האינטרנט נמצא ב סיכון, כולל כמה מחשבי מק. ובכן, לוודא שאתה תיקון המערכות שלך עכשיו. כל אחד אירוח ריצת אתר מערכות הפעלה המושפעות צריך לנקוט בפעולה בהקדם האפשרי. כל מי שיכול להרשות לעצמו את זה צריך להיראות ליישום הניטור ואינטרנט שלהם חומות אש כדי להשגיח על כל התקפות. SPEAKER 3: הדבר הגרוע ביותר שיכול לקרות הוא שמישהו היה כותב קוד ש באופן אוטומטי הייתי הולך ולסרוק האינטרנט וישפיע כל המחשבים האלה. וברגע שהם עושים את זה, גם, הדבר הגרוע ביותר שהם יכולים לעשות הוא פשוט למחוק הכל, או לסגור את האתרים. כדי שנוכל לראות נזק מנקודת מבט זו, שבו תהיה לנו אנשים זדוניים שרק תחליט לגרום הרס על ידי הבאת מערכות למטה או מחיקה קבצים, וכל מיני דברים כאלה. SPEAKER 2: יש כאלה שאומרים שזה אחד הקשים ביותר למדידה באגים בשנים, וזה יכול לקחת שבועות או אפילו חודשים כדי לקבוע את ההשפעה האולטימטיבית שלה. 

1 SPEAKER: אז כל זה נכון, אבל הדבר המצחיק כמעט בכל הוא, של הדימויים שראית, מלבד אולי המקלדת, יש מה לעשות עם באג כלשהו. שרתים וחוטי חשמל וכן הלאה, זה קשור סוג של נקודת השקה, אבל בליבה זה בעצם די מכיר את מה שקורה כאן. למעשה, תן לי ללכת ל מכשיר CS50 שלנו. תן לי ללכת קדימה ולמקסם חלון המסוף כאן. אתם וכבר משתמשים זו, או משובץ גרסתו, בgedit כדי לכתוב תוכניות, להקליד פקודות, וכן הלאה, וזה בעצם, ויש לו כבר שבועות, Bash, B-A-S-H. זה Bourne-שוב להפגיז, וזה רק דרך מפוארת לומר, זו היא תכנית שיש לי מהבהב הפקודה, ביעילות, שיושב שם ומחכה עבור קלט בשבילך. וזה את הפקודה ממשק שורה שדרכו אתם כבר פועלים פקודות ו סופו של דבר להרכיב ולאחר מכן פועל תוכניות. 

אבל Bash הוא גם תכנות שפה במובן הבא. אתה יודע שיש פקודות כמו cd וls וגם מצרימות ואחרים, אבל אתה יכול להגדיר פקודות משלך על ידי יישומם בBash. עכשיו אנחנו לא הולכים להיכנס לפירוט רב כלBash שפת תכנות, אבל יודע, למשל, שברגע, אין פקודה בשם "שלום". אז ניתן למצוא אותו ב אחד מהחבילות אלה. זה לא מותקן במחשב שלי. שאל את המנהל שלך. אבל אם אני רוצה שיהיה תכנית בשם "שלום" בBash או בהפקודה, אני באמת יכול להשתמש בתחביר זה ממש כמו ג זה לא בדיוק אותו הדבר, אבל זה נראה די דומה ל פונקציה, אם כי חסר כמה פרטים. לא קורים כלום, אבל עכשיו, אם אני מקליד "שלום," למעשה אתה יכול לכתוב תכנית, לא בC, לא בג'אווה, לא בתכנות אחר שפה, אבל בBash עצמו. 

עכשיו המפתח כאן הוא שכתבתי שם רציתי לתת פקודה חדשה זו, והסוגריים הם גם סמלי של זה להיות פונקציה. במאמר מוסגר, אתה יכול גם לעשות כיף דברים, ולמעשה, אפילו על מערכת ההפעלה Mac, זו היא תכנית בשם מסוף. זה מגיע מובנה בתוך כל אחד אחר מחשב שיש לו מק בחדר הזה, ואתה יכול לעשות דברים דומים בMac מערכת הפעלה, אבל אתה יכול ללכת יותר מעבר לזה. וזה קצת משיק, אבל זה סוג של כיף. נזכרתי הבוקר, כאשר חושבים זה דרך, של משחק קטן נהגתי לשחק עם אחד TFS לשעבר של CS50 לפי כל פעם שהוא היה קם מ המקלדת שלו עם המסך שלו לא נעולה, הייתי לבצע פקודה כמו זה- "להגיד שלום." ועכשיו כל פעם שהוא חזר לו מקלדת אחרי שפיניתי את המסך והוא היה מתיישב, תנסה לעשות קצת עבודה, רשימה של התוכן directory-- 

[אודיו השמעה] 

-שלום. שלום. 

1 SPEAKER: אז, בהגינות, זה לא היה ממש "שלום". בדרך כלל זה היה משהו דומה יותר לthat-- [אודיו השמעה] -Beep. 1 SPEAKER: --that אני would-- כך המחשב שלו היית לקלל אותו כל פעם שהוא למעשה התיישב ליד המקלדת שלו. ומהר מאוד הוא הבין לא לעזוב את המסך שלו נעול. אבל זה מצביע על הסוג כיף מטופש שאתה יכול להיות עם משהו כמו Bash. אבל זה קצת יותר רציני, כדי להיות בטוח, יותר מזה. ולמעשה, זו אחת רוב החרקים מסוכנים וארוך טווח זה באמת פגע בעולם גלובלי. באג זה קיים כבר עבור חלק 20 שנים, ואתה תהיה פגע בסתם בכל רגע והפשטות היחסית שלה. 

אז זה נציג הפקודה שאם אתה בעלי מק, פשוטו כמשמעו, ברגע זה ממש כאשר יש לך המכסה שלך פתוח, אתה יכול לנסות להקליד שב תכנית בשם מסוף. מסוף נמצא תחת יישומי Utilities-- לשם שינוי, אין לי למשתמשי Windows לדאוג threat-- המסוים הזה אבל אלו מכם עם מחשבי מקינטוש יכולים להקליד זה לחלון כמו שאני אעשה כאן, ואם אתה מקליד כי לתכנית זו נקרא מסוף, כמו שאני אעשה עכשיו, אם אתה רואה את המילה "פגיע" המחשב שלך הוא פגיע לניצול. 

עכשיו מה זה אומר בעצם? ואת זה הוא אמנם כמה תחביר די מטורף, אבל בואו לפחות להוציא חלק מההיבטים המעניינים. אז יש כמה תחביר שנראה קצת מוכר, לפחות מC ותכנות באופן כללי יותר. אני רואה כמה סוגריים, פסיק, סוגריים מסולסלים, וכאלה, אבל מתברר שזה דבר טיפשי כאן בצהוב היא למעשה פונקציה שלא עושה כלום. אמצעי המעי הגס לא לעשות כלום, ו פסיק אומר להפסיק לעשות שום דבר. אז בתוך אלה סוגריים מסולסלים, העובדה שיש לי שווה לחתום לצד שמאל, זה הוא למעשה יצירת הפקודה, או משתנה, בשם x, והקצאה את שצהוב קצת קוד שם. זה יכול להיות משהו כמו "הד שלום "או" אומר צפצוף "או משהו דומה לזה. אבל שים לב, אם העיניים שלך לנדוד יותר ימינה, יש עוד הקו הזה מאשר רק בסוף פסיק ש. "הד פגיע," ולאחר מכן מעבר לכך יש אפילו יותר. עוד נקודה ופסיק, -c bash :. 

אז סיפור ארוך קצר, הקו הזה של קוד הוא מספיק למשכנע מחשב זה פגיע לעושה משהו שאתה רוצה לעשות את זה, בגלל שיש באג בפיו Bash למרות Bash היה אמור להפסיק קווי קריאה של ימין הפקודה שם אחרי הטקסט הצהוב, לבאג בן 20 פלוס, Bash למעשה היה קריאה מעבר לפסיק ושדי הרבה עושה את מה שהוא אמר לי. 

אז מה המשמעות של שסופו של דבר? אני רק אמרתי "הד שלום" או "הד פגיע," אבל מה אם עשה משהו למעשה זדוני, כמו * -rf rm, שלא אתה עלול אי פעם שהקלדת לפני, ולמען אמת אתה כנראה לא צריך מוקדם מדי, כי אתה יכול לעשות הרבה נזק עם זה. למה? rm עושה מה, כמובן? מסיר. * אומר מה? כל. אז זה מה שנקרא קלף פראי, אז זה אומר למחוק את כל מה ב הספרייה הנוכחית. -r קורה למתכוון רקורסיבית, מה שאומר שאם מה שאתה מוחק היא ספרייה, ובתוך משם הוא קבצים אחרים וספריות אחרות, באופן רקורסיבי לצלול לתוך שם ולמחוק את כל זה. ו-f הוא הגרוע מכולם. מישהו יודע מה -f אומר כאן? חיל. אז תכריח את האמצעים, אפילו אם זה רעיון רע, לעשות את זה מבלי להציג הודעתי לאישור נוסף. אז, אתה יודע, אנחנו צוחקים על זה, אבל בכנות, אני כנראה הקלד מספר פעמים זה יום, כי המציאות הוא שזו הדרך המהירה ביותר ל למחוק כל מיני דברים שלמים. אבל גם אני עשיתי קצת נזק. 

אבל אם היית להערים על מחשב להגדרה כמה משתנים טיפש או פונקציה שנקראת x, אבל אז הטעיית המחשב לביצוע מעבר לגבולות ש פונקציה, מעבר לנקודה ופסיק ש, אכן אתה יכול להערים מחשב לביצוע משהו כמו rm -rf או פקודת דוא"ל או פקודת ההעתקה. כל דבר שאתה ממש יכול לעשות עם מחשב, בין אם מדובר במחיקת קבצים, יצירת קבצים, דואר זבל מישהו, תוקף כמה שרת מרחוק, אם אתה יכול לבטא את זה עם הפקודה, אתה יכול להערים מחשב לתוך עושה את זה. 

עכשיו מה דוגמא של איך אתה יכול לעשות את זה? ובכן, יש הרבה של מחשבים על Bash ריצת האינטרנט. כל משתמשים שלנו Mac הם ביניהם. הרבה שרתי Linux הם בין גם אותם, ושרתי יוניקס. Windows מקבלת שוב יחסית מהקרס אלא אם כן התקנת תוכנה מיוחדת. עכשיו הרבה שרתים, עבור למשל, שרתי אינטרנט מנוהלים, ולמעשה לינוקס היא אולי רוב מערכת הפעלה הפופולרית לרוץ על מחשבים באינטרנט שמשרתים את דפי אינטרנט. עכשיו כפי שנראה מאוחר יותר בסמסטר, כאשר אתה שולח בקשה מ Chrome browser-- שלך, Internet Explorer, whatever-- לשרת מרוחק, מתברר שלמרות ש שזה עתה הקליד www.example.com, הדפדפן שלך שולח הודעה זה קצת יותר מסתורי, כמו זה. 

אבל שים לב קצת משהו מוזר. שתי השורות הראשונות אף פעם לא ראיתי לפני, אבל הם לא נראים במיוחד מאיים. אבל שים לב למה שנגנבתי לשורה השלישית כאן. אם בחור רע היה לשלוח הודעה כמו זה מהמחשב שלו או שלה למקינטוש או פגיעים פגיע שרת לינוקס, הדבר המצחיק הוא שBash, כי הפקודה קטנה הפקודה פשוטה, הוא בכל מקום ולעתים קרובות משמש לביצוע במהות את התוכן של מסר שהוא מקבל. ולפי היגיון זה, אתה יכול טריק שרת אינטרנט, ולכן, על ידי שליחת משהו כמו User-Agent, אשר בדרך כלל צריך לומר: שמו של הדפדפן שלך. User-Agent Chrome, User-Agent אינטרנט Explorer, User-Agent פיירפוקס, זה רק הדפדפן שלך של דרך לזהות את עצמו. אבל אם בחור רע מאוד חוכמה אומרת, מ"מ מ"מ, אני לא הולך לספר לכם מה הדפדפן שלי הוא, אני במקום שאני הולך לשלוח לך את זה נסתר עתיד דבר עם -rf rm * בזה, אתה יכול, פשוטו כמשמעו, להערים שרת אינטרנט פגיע באינטרנט לביצוע בדיוק את זה ב יש למחיקה כל הקבצים. ולמען אמת, זה לא אפילו הגרוע ביותר שלה. אתה יכול לעשות כל דבר. אתה יכול להתחיל מופץ התקפות מסוג מניעת שירות אם שלח הודעה ל אשכולות של שרתי אינטרנט כולו ולאחר מכן היה לי כולם לרדת, ל למשל, על שרתי Harvard.edu, ואתה יכול למיין של מפץ לעזאזל מחוץ להם על ידי תנועה ברשת שהייתה מופעל אחרת על ידי האיש הרע הזה. 

אז, סיפור ארוך קצר, כמעט כולם בחדר הזה שבבעלותו מק הוא פגיע לזה. כסף הבטנה היא שאם אתה פועל בשרת אינטרנט במחשב הנייד שלך, ואלא אם כן יש בעצם מוגדר זה כדי לאפשר למשהו כמו SSH לתוכו, אתה בטוח בעצם. זה פגיע, אבל אין אחד מנסה להיכנס למחשב הנייד שלך, כך שאתה יכול סוג של להיות סמוך ובטוח. עם זאת, אפל בקרוב להיות עדכון לתקן את זה. העולם של לינוקס כבר שוחרר מספר התיקונים לפדורה ואובונטו וגרסאות אחרות של לינוקס, ואכן אם אתה מפעיל עדכון 50 במכשיר, אפילו שגם יהיה מעודכן ומתוקן. אבל שיש לו גם לא באמת היה פגיע, כי אלא אם כן יש לך התעסק קצת עם המכשיר ועשה את המחשב הנייד שלך בפומבי נגיש באינטרנט, שאינו כברירת מחדל, יש לך היה ממש בסדר כי של firewalling וטכניקות אחרות. 

אבל זה דוגמא קיצונית של באג שחיינו לפשוטו כמשמעו 20 שנים, ומי יודע אם מישהו כל הזמן הזה ידע על זה? ולמעשה, זו אחת האתגרים הבסיסיים שנראה מאוחר יותר ב סמסטר על אבטחה, הוא שבדיוק כמו בעולם האמיתי, החבר 'ה הטוב נמצא בעמדת הנחיתות. כדי לשמור את הרעים החוצה, יש לנו ל לוודא שכל דלת נעולה, שכל חלון הוא מאובטח, ש כל נקודת הכניסה לבית הוא מאובטח כדי לשמור את הרעים החוצה. אבל מה עושה האיש הרע צריך לעשות בעצם להתפשר הבית שלך ולגנוב ממך? הוא או הוא פשוט צריך למצוא אחד נעול דלת, חלון אחד שבור, או משהו לאורך שורות אלה, וזה אותו דבר באבטחת מחשב. אנחנו יכולים לכתוב מיליונים שורות של קוד תכנות ולהוציא מאות או אלפים שעות מנסות לקבל את זה נכון, אבל אם אתה עושה רק אחד טעות בנכונותו, אתה יכול לשים את המערכת כולה ו אכן במקרה זה, את כל האינטרנט ועולם בסיכון. 

אז אם אתם רוצים ללמוד עוד על זה, ללכת לכתובת אתר זו כאן. אין צורך בפעולה הלילה אלא אם כן אתה בין אלה נוחים יותר ש כבר פועל באינטרנט שלך שרת, ובמקרה כזה אתה צריך, למעשה, לעדכן את התוכנה שלך. 

וגם את זה הוא הכותרת של דיבור, ועכשיו נייר, שאנחנו כבר קשורים ב באתר קורס להיום. זה היה על ידי בחור קן תומפסון שם, ש היה קבלה מפורסמת מאוד הפרס במדעי מחשב, והוא נשא את הנאום הזה כמה שנים לפני, במהות באותו נושא זה. שואלת אנשים את השאלה, כדאי לך באמת אמון, סופו של דבר, תוכנה שניתן לכם? לדוגמא, יש לנו את כל כבר בכתיבת תוכניות, ואנחנו כבר קומפילציה שלהם עם קלאנג. והידע שלך, יש לך בכתב תוכניות בשום צורה לCS50 בו יש דלת אחורית של מיני, שיש דרך כי איש רע, אם להפעיל את תכנית, יכול להשתלט על המחשב שלך? כנראה שלא, נכון? מריו, וחמדן, ואשראי. כל אלה הם התוכניות הקטנות למדי. היית צריך להיות די רע אם אתה באמת עשה את כל המחשב שלך פגיע לאחר כתיבת 10 או 20 שורות קוד, או לפחות לא מודע לכמה של ההשלכות הביטחוניות. עכשיו אני אומר שבדיחות דעת, אבל אנחנו הולכים לראות היום והשבוע זה בעצם באמת, באמת קל להיות רע ולעשות את זה אפילו תוכניות קצרות פגיעות. 

אבל לעת עתה, לפחות, מבין כי השאלה נשאלת כאן הוא על קלאנג במהדר. למה יש לנו כבר לבטוח קלאנג לשתיים או שלושה השבועות האחרונים? מי יכול לומר שכל מי שכתב קלאנג לא היה לי מצב "אם" לשם שבעצם הזריק כמה אפסים ואלה לכל תכנית זה הידור שאתן לו או לה גישה המחשב שלך כאשר אתה ישן ומכסה המחשב הנייד שלך הוא פתוח והמחשב שלך פועל? נכון? יש לנו סוג כזה של ימין מערכת הכבוד אנחנו עכשיו שבו בוטחים שקלאנג הוא לגיטימי. אתה בוטח שהמכשיר הוא חוקי. אתה בוטח שפשוטו כמשמעו כל תכנית על Mac או PC שלך הוא אמין. וכמו באג פשוט זה מרמז, גם אם זה לא זדוני, זה בהחלט לא עשוי להיות המקרה. 

אז אתם צריכים לפחד כמו גיהינום. למען האמת, אין פשוט פתרון לזה אחר מ סוג של מודעות חברתיות של המורכבות הגוברים כי אנחנו בונים על גבי מערכות המחשב שלנו, ואיך יותר ויותר פגיע אנו עשויים להיות טובים מאוד. 

כעת, עם שאמרו, בריחה. אז הפריצה היא בעיה להגדיר שלוש, ו פריצה היא משחק מפעם שאולי אתה זוכר, אבל לנו בבעיה להגדיר שלוש, זה מאפשר לנו לקחת דברים לגבות חריץ כך שכאשר אנו כותבים תוכניות, אפילו בחלון מסוף כזה, אנחנו באמת יכולים לרוץ, סופו של דבר, תוכניות גרפיות לא בניגוד לאלה שהיו לנו גישה בגרד. אז זה צוות של יישום של בריחה, וזה רק זה לבנים שביר משחק, שאתה להזיז ההנעה שלך בחזרה ושוב, ואתה מכה את הכדור נגד לבנים צבעוניים אלה למעלה. אז זה מביא אותנו סוג של חזרה למקום שבי היינו יכול להיות מהר מאוד עם סריטות, ועכשיו עם C, יישום שלנו ממשקי משתמש גרפיים. 

אבל יותר מזה, זה סט בעיה מייצג הראשון שבו אנחנו נותנים לך חבורה של קוד. ואכן, אני מביא מפורש תשומת לב לכך, כי במיוחד עבור אלה פחות נוחים, זה בעיה להגדיר, לפחות במבט ראשון, הוא הולך להרגיש כמו אנחנו כבר לקחנו את זה צעד אחד קדימה. כי אנחנו כבר נתנו לך, עבור חלק מהחיפוש ומיון בעיות בpset, חבורה של קוד שכתבנו, וכמה הערות שאומר "לעשות", בו אתה צריך למלא את החסר. אז לא יותר מדי מפחיד, אבל זה הפעם הראשונה אנחנו מושיט לך קוד שאתה צריך לקרוא ראשון, להבין, ולאחר מכן להוסיף ל ולהשלים אותה. 

ולאחר מכן עם בריחה, אנחנו הולכים לעשות את אותו הדבר, נותן לך עוד כמה עשרות קווים קוד ש, בכנות, ייתן לך הרבה מסגרת ל את המשחק אבל להפסיק קצר יישום הלבנים ואת הכדור וההנעה, אבל אנחנו עושים ליישם כמה תכונות אחרות. ואפילו שבמבט ראשון, שוב, במיוחד אם פחות נוח, אולי נראה במיוחד מרתיע ו אתה חושב שיש כל כך הרבה פונקציות חדשות אתה צריך לעטוף את דעתך מסביב, וזה נכון. אבל יש לזכור, שזה ממש כמו גירוד. רוב הסיכויים הם שאתה לא משתמש בכל חלקי הפאזל בגרד. רוב הסיכויים הם שלא אכפת לך לעטוף המוח שלך סביב כולם משום שכל מה שנדרש היה מבט מהיר להבין, הו, זה מה שאני יכול לעשות עם זה פיסת הפאזל. ואכן, בבעיה להגדיר 3 מפרט, אנחנו נצביע לך בתיעוד שיהיה להכיר לך כמה פונקציות חדשות, וסופו של דבר תכנות בונה לך להשתמש. תנאים, לולאות, משתנים ופונקציות יהיה זהה ל מה שראינו עד כה. 

אז אכן, מה שאנחנו ייתנו לי אתה הוא כמה דוגמאות קוד ש מאפשר לך ליצור חלון זה נראה לא כמו זו, וסופו של דבר להפוך אותו ל משהו דומה לזה. אז לנצל את CS50, לדון שעות במשרד ועוד, ולהתנחם בעובדה ש כמות הקוד שאתה צריך לכתוב הוא למעשה לא כל כך הרבה. האתגר הראשון הוא פשוט להסתגל את עצמך לאיזה קוד שכתבנו. 

כל שאלות על pset3, Shellshock, או בדרך אחרת? 

קהל: זה נראה כמו עובר עם בריחה כי הקוד הוא כמעט סגנון מונחה עצמים, אבל חשבתי שC היה תכנית מונחת עצמים. 1 SPEAKER: שאלה מצוינת. אז במחפש דרך קוד הפצה, הקוד כתבנו לpset3, למוכר אלה, זה נראה כמו זה קטנים מונחה עצמים. תשובה קצרה היא, זה הוא. זה קירוב של איך אתה אולי לעשות קוד מונחה עצמים באמצעות שפה כמו C, אבל זה עדיין סופו של דבר פרוצדורלי. אין שיטות הפנימיים של המשתנים, כפי שתראו. אבל זה מזכיר ש. ואנו רואים תכונה ששוב כשנגיע לPHP וJavaScript לקראת סוף הסמסטר. אבל לעת עתה, לחשוב על זה כ רמז של מה לבוא. שאלה טובה. בסדר. אז למזג סוג היה איך אנחנו דברים שמאל בפעם האחרונה. ולמזג סוג היה מגניב ב מובן שזה היה כל כך הרבה יותר מהר, לפחות על סמך הבדיקות שטחיות שעשינו בשבוע שעבר, מאשר, למשל, בועה סוג, מיון בחירה, מיון הכנסה. ומה שהיה מסודר מדי הוא פשוט איך באופן תמציתי ונקי אתה יכול לבטא את זה. ומה שאנחנו לא אומרים שזה היה עליון מחויב בזמן הריצה של מיזוג למיין? כן? 

קהל: n להתחבר n? 

1 SPEAKER: n להתחבר n, תקין. n להתחבר n. ואנחנו נחזור למה ש באמת אומר או איפה שמגיע מ, אבל זה היה טוב יותר ממה שזמן ריצה שראינו לבועה בחירה וסוג ההכנסה? אז n בריבוע. n בריבוע גדול יותר מזה, וגם אם זה לא די ברור, יודע שn היומן הוא קטן יותר מאשר n, כך שאם אתה עושה פעמים n משהו קטן יותר מאשר n, זה הולך להיות פחות מ בריבוע n. זה קצת אינטואיציה יש. אבל שילמנו מחיר על זה. זה היה מהיר יותר, אבל נושא שהתחיל לצאת בשבוע שעבר היה איזון זה. יש לי את ביצועים טובים יותר זמן חכם, אבל מה הייתי צריך להוציא על אחרים יד, על מנת להשיג את זה? 

קהל: זיכרון. 1 SPEAKER: תגיד את זה שוב? קהל: זיכרון. 1 SPEAKER: זיכרון, או חלל באופן כללי יותר. וזה לא היה סופר ברור עם בני האדם שלנו, אבל תזכור שהמתנדבים שלנו היו צעד קדימה ודריכה בחזרה כאילו יש מערך כאן, וכאילו יש מערך שני כאן ש הם יכולים להשתמש, כי אנחנו מקום הדרוש כדי למזג את האנשים האלה. אנחנו לא יכולים פשוט להחליף אותם במקום. אז למזג מינוף סוג יותר מקום, ש אנחנו לא צריכים עם אלגוריתמים האחרים, אבל היתרון הוא שזה הרבה יותר מהר. ולמען אמת, בחלל העולם האמיתי זיכרון RAM days-- אלה, דיסק קשיח space-- הוא יחסית זול, ואז זה לא בהכרח דבר רע. 

אז בואו נעיף מבט מהיר, קטן יותר באופן שיטתי, על מה שעשינו ולמה אמר שזה n היה להיכנס n. אז הנה שמונה המספרים ו שמונה מתנדב שהיו לנו בפעם האחרונה. והדבר הראשון שמיזוג מיין אמר לנו לעשות היה מה? קהל: הפרד בשני. 1 SPEAKER: תגיד את זה שוב? קהל: הפרד בשני. 1 SPEAKER: הפרד בשני, תקין. זה מזכיר מאוד ספר טלפונים, של הפרד ולכבוש באופן כללי יותר. אז הסתכלנו על החצי השמאלי. ואז ברגע שאמרנו, סוג המחצית השמאלית של האלמנטים, מה היה לנו הבא אומרים? למיין את המחצית השמאלית של השמאל המחצית, אשר אפשר לנו, לאחר החלוקה לשתיים, תתמקד בארבעה ושני. 

איך אתה למיין את רשימה עכשיו, ב צהוב, בגודל שני, באמצעות מיזוג מיין? ובכן לחלק אותו לשתיים, ולמיין את המחצית השמאלית. וזה מקום שבי דברים הגיע לרגע קטן ומטופש. איך אתה למיין את רשימה זה של גודל אחד, כמו מספר זה ארבעה כאן? זה מסודרים. תסיים. 

אבל אז איך אתה למיין את רשימה גודל אחד כאשר זה המספר שתיים? ובכן, אותו דבר, אבל עכשיו מה שהיה שלישי וצעד מפתח במיינו מיזוג? אתה הייתי צריך למזג את השמאל מחצית ובמחצית הימנית. וברגע שעשינו את זה, אנחנו נראים בשעה ארבע, הסתכלנו על שתי. החלטנו בסדר, ברור ששתי מגיע ראשון, לכן אנחנו שמים שני בה מקום, ואחריו ארבעה. ועכשיו אתה צריך כדי להריץ אחורה סוג של, וזה סוג של מאפיין של אלגוריתם כמו מיזוג מיין, אחורה בזיכרון. מה הייתה השורה הבאה של הסיפור? מה שאני צריך להתמקד בשלב הבא? המחצית הימנית של השמאל מחצית, וזה שישה ושמונה. 

אז תן לי רק צעד דרך זה בלי להמשיך ולהציק לנקודה יותר מדי. שש ושמונה, אז שישה הוא מסודרים, שמונה ממוינים. מיזוג יחד אותם כמו ש, ועכשיו הצעד הגדול הבא הוא, כמובן, למיין את החצי ימני מ הצעד הראשון של אלגוריתם זה. אז אנחנו מתמקדים באחד, שלוש, שבע, חמש. לאחר מכן, אנו מתמקדים במחצית השמאלית. המחצית השמאלית של ש, המחצית הימנית של כי, ולאחר מכן למזג באחד ושלוש. ואז חצי הנכון, אז עזב את המחצית שלו, ולאחר מכן את המחצית הימנית שלו. מיזוג זה ב, ועכשיו מה שנשאר צעד? מיזוג המחצית השמאלית הגדולה וגדולה נכון מחצית, כך אחד הולכת שם למטה, אז שתיים, ואז שלוש, ארבעה, ואז חמש, אז שישה, שבע ושמונה. 

אז עכשיו למה זה חושף סופו של דבר, במיוחד אם n ולוגריתמים יותר בדרך כלל ולא לברוח לך, לפחות בזיכרון האחרון? ובכן, שים לב לגובה של הדבר הזה. היו לנו שמונה אלמנטים, ואנחנו חילק אותה על ידי שתי, על ידי שתי, על ידי שתי. אז להיכנס בסיס שתיים משמונה נותן לנו שלוש. ותאמין לי על שאם מעורפל קצת על זה. אבל להיכנס בסיס שניים משמונה הוא שלוש, כך עשינו שלוש שכבות של מיזוג. וכאשר אנו מוזגו אלמנטים, אלמנטים כמה לא שאנחנו מסתכלים על כל אחד משורות אלה? כולל של n, נכון? בגלל למזג השורה העליונה, למרות שאנחנו עשינו את זה טיפין טיפין, אנו סופו של הדבר נגעו בכל מספר פעם אחת. ובשורה השנייה, ל מיזוג רשימות אלה של גודל שני, היו לנו לגעת זה באלמנט פעם אחת. ואז כאן באמת ברור בשורה האחרונה, היו לנו לגעת כל אחד מאלה אלמנטים פעם אחת, אבל רק פעם אחת, כך כאן טמון, אם כן, n n היומן שלנו. 

ועכשיו רק כדי לעשות דברים קצת יותר רשמי רק לרגע, אם אתה היו לנתח את זה עכשיו בסוג של רמה גבוהה יותר ולנסות להחליט, גם איך אולי אתה הולך על להביע זמן הריצה של אלגוריתם זה רק מלהסתכל על זה ולא על ידי שימוש בדוגמה מאולצת? ובכן, כמה זמן היית אומר צעד כזה בצהוב היה לוקח, אם <2 תמורת n? זה O גדול של מה? אז אני רואה אחד, ולכן צעד אחד, אולי שני צעדים כי זה אם ואז לחזור, אבל זה זמן קבוע, נכון? אז אמר O (1), וזה איך אני להביע את זה. T, פשוט להיות זמן ריצה. n הוא בגודל של הקלט, כך T (n), רק דרך מפוארת לומר הריצה קלט נתון זמן בגודל n הולך להיות על הסדר זמן קבוע, בO (1). 

אבל חוץ מזה, מה עם זה? איך היית מבטא את זמן ריצה של הקו הצהוב הזה? T של מה? סוג של אתה יכול לרמות כאן ו לענות על השאלה שלי באופן מחזורי. אז אם זמן הריצה ב כללי רק שאנחנו אומרים הוא T (n). ועכשיו אתה סוג של חתירה לכאן ו אומר, גם, רק למיין את החצי השמאלי, ולאחר מכן למיין את החצי הימני. איך ייתכן שאנחנו באופן סמלי מייצגים זמן הריצה של הקו הצהוב הזה? T של מה? מה הגודל של הקלט? n על שתי. למה אני לא רק אומר את זה? ואז זה T אחר (n / 2) ולאחר מכן שוב, אם אני למזג את שני חצאים ממוינים, כמה אלמנטים אני הולך יש לגעת בסך הכל? n. אז אני יכול לבטא את זה, רק כדי להיות סוג של אשליה, כזמן הריצה באופן כללי. T (n) הוא בדיוק בזמן הריצה של T (n / 2), בתוספת T (n / 2), עזב את המחצית ותקין חצי, בתוספת O (n), שהוא כנראה n צעדים, אבל אולי, אם אני משתמש בשתי אצבעות, זה כפליים צעדים, אבל זה ליניארי. זה חלק ממספר הצעדים זה גורם של n, כך אנו עשויים לבטא את זה כמו זה. וזה מקום שבי עכשיו אנחנו דוגית ל אחורי של ספר לימוד המתמטיקה בתיכון שלנו אנחנו שהישנות סופו של דבר בסופו של שווה את זה, n פעמים להיכנס n, אם אתה באמת עושה את זה מתוך המתמטיקה יותר באופן רשמי. 

אז זה רק שתי נקודות מבט. מבחינה מספרית אחד עם בקידוד קשיח דוגמא מייצגת באמצעות שמונה מספרים, ועוד מבט כללי על איך שהגענו לשם. אבל מה שבאמת מעניין כאן הוא, שוב, הרעיון הזה של רכיבה על אופניים. אני לא משתמש ללולאות. אני סוג של הגדרה משהו במונחים של עצמו, לא רק עם זה פונקציה מתמטית, אלא גם במונחים של קוד פסאודו זה. קוד פסאודו זה רקורסיבית בשני שקוויה הוא למעשה אומר לו ללכת להשתמש עצמו כדי לפתור קטן יותר בעיה של גודל קטן יותר, ולאחר מכן שוב ושוב ושוב עד לשייף ואנו עד למקרה בסיס זה מה שנקרא. 

אז בואו ממש לצייר משכנע יותר לקחת משם מזה כדלקמן. תן לי ללכת לgedit ולקחת תסתכל על כמה קוד המקור של היום, בפרט דוגמא זו כאן. Sigma 0, אשר מוסיף כנראה המספרים אחד עד n. אז בואו לראות מה מוכר ולא מוכר כאן. ראשית יש לנו כמה כולל, כך ששום דבר חדש שם. אב טיפוס. אני מעורפל מעט על זה אחרי כמה ימים, אבל מה שאנחנו אומרים אב טיפוס של פונקציה הוא? קהל: [לא ברור]. 1 SPEAKER: מה זה? קהל: אנחנו מכריזים את זה. 1 SPEAKER: אנחנו מכריזים את זה. אז אתה מלמד קלאנג, היי, לא ממש מיישם את זה עדיין, אבל אי שם בקובץ זה, ככל הנראה, הוא הולך להיקרא פונקציה מה? סיגמא. וזו רק הבטחה ש זה הולך להיראות כך. זה הולך לקחת מספר שלם כ input-- ואני יכול להיות מפורש יותר ואומר int n --and זה הולך להחזיר int, אבל אמצעי פסיק, מ"מ, אני לעקוף ליישום זה קצת יותר מאוחר. שוב, קלאנג הוא מטומטם. זה הולך רק כדי לדעת מה אתה אומר את זה מלמעלה למטה, ולכן אנחנו צריכים לפחות לתת לי רמז של מה לבואו. 

עכשיו בואו נסתכל על עיקרי כאן. בואו לגלול למטה כאן ו לראות מה ראשי עושה. זה לא כל כך הרבה זמן של פונקציה, ו למעשה המבנה כאן הוא מוכר. אני מצהיר n משתנה, ולאחר מכן אני להציק למשתמש שוב ושוב עבור מספר שלם חיובי באמצעות getInt, ויציאה של לולאה זו רק ברגע שהמשתמש נענה. האם בעוד, אנחנו כבר רגילים להציק למשתמש בדרך. עכשיו זה מעניין. אני מצהיר int בשם "תשובה". אני להקצות את ערך ההחזרה של פונקציה שנקראת "סיגמא". אני לא יודע מה זה עושה, אבל אני זוכר שהכריז אותו לפני רגע. ואז אני מעביר ב ערך שהמשתמש הקליד ב, n, ולאחר מכן אני מדווח התשובה. ובכן בואו לגלול אחורה רק לרגע. בואו נלך קדימה לספרייה זו, להפוך את סיגמא 0, ובעצם להפעיל את התכנית ולראות מה קורה. אז אם אני הולך קדימה ולרוץ תכנית זו, ./sigma-0, ואני מקליד בצורה חיובית מספר שלם כמו שתי, Sigma, כסמל היווני מרמז, הוא רק הולך להוסיף את כל המספרים מ אפס בעד שתי. אז 0 בתוספת 1 ועוד 2. כך זה צריך בתקווה לתת לי 3. זה כל מה שהוא עושה. ובאופן דומה, אם אני מפעיל את זה שוב ואני נותן לה את המספר שלוש, זה 3 ועוד 2, אז זה 5, בתוספת 1 צריכים לתת לי 6. ואז אם אני מקבל באמת מטורף ו התחל להקליד במספרים גדולים יותר, זה צריך לתת לי גדולים יותר ויותר סכומים. אז זה כל מה. 

אז מה עושה סיגמא נראה? ובכן, זה די פשוט. זה איך אנחנו יכולים להיות מיושמים זה לבני הזוג של שבועות האחרונים. "Int" הולך להיות סוג ההחזרה. סיגמא היא שם, וזה לוקח מ 'משתנה במקום n. אני תשנה את זה למעלה. אז זה רק בדיקת שפיות. אנחנו תראו למה ברגע. עכשיו אני מצהיר משתנה אחרת, סכום, לאתחל אותו לאפס. אז יש לי את זה ללולאה חוזר ונשנה, כנראה לבהירות, מi = 1 בעד = מ ', שהוא כל מה שמשתמש הקליד ב, ולאחר מכן אני להגדיל את הסכום כזה. ולאחר מכן להחזיר את הסכום. 

אז כמה שאלות. אחד, אני טוען בתגובה שלי שזה נמנע סיכון של לולאה אינסופית. למה שעובר במספר שלילי לגרום, באופן פוטנציאלי, לולאה אינסופית? 

קהל: אתה לעולם לא תגיע מ '. 

1 SPEAKER: אף פעם להגיע מ '. אבל מ 'הוא עבר ב, אז בואו תחשוב על דוגמא פשוטה. אם מ 'הוא עבר בידי משתמש כשלילי אחד. ללא קשר לעיקרי. ראשי מגן עלינו מפני זה יותר מדי, אז אני פשוט להיות ממש אנאלי עם סיגמא לעשות גם בטוח שהקלט לא יכול להיות שלילי. אז אם מ 'הוא שלילי, משהו כמו שלילי אחד. מה הולך לקרות? ובכן, אני הולך לקבל אותחל לאחד, ואז אני הולך להיות קטן או שווה למ '? 

Stand by. שwas-- בוא לא, בואו nix הסיפור הזה. אני לא שואל את השאלה הזאת, משום ש הסיכון שאני מרמז לא הולך לקרות, כי אני הוא תמיד הולך להיות בסדר than-- גדול יותר, אני חוזר בי את השאלה הזאת. אישור. בואו נתמקד רק בחלק הזה כאן. מדוע אני מצהיר כמה מחוץ ללולאה? הודעה על קו 49 לי הכריז אני פנימי של הלולאה, אבל באינטרנט 48 לי הכריז כמה בחוץ. כן. קהל: [לא ברור]. SPEAKER 1: בטח. בראש ואני בהחלט לעשות אז קודם כל לא רוצה להכריז ולאתחל סכום לאפס בתוך לולאה בכל איטרציה, כי זה ברור יביס מטרה מסכם את המספרים. הייתי משתנה כל זמן הערך חזרה לאפס. וגם, מה עוד מסתורי יותר סיבה לאותה החלטת עיצוב? כן. 

קהל: [לא ברור]. 1 SPEAKER: בדיוק. אני רוצה לגשת אליו מחוץ של הלולאה מדי על מה קו? על 53. ובהתבסס על כלל האצבע שלנו מלפני כמה הרצאות, משתני scoped, באמת, ל סוגריים מסולסלים המקיפים אותם. אז אם אני לא מצהיר סכום בתוך של סוגריים המסולסלים החיצוניים אלה, אני לא יכול להשתמש בו בשורה 53. במילים אחרת, אם אני הכריז סכום בכאן, או אפילו בתוך ללולאה, לא יכולתי לגשת אליו ב53. משתנה יהיו יעיל ייעלם. אז כמה סיבות יש. אבל עכשיו בואו נחזור ולראות מה קורה. אז סיגמא נקרא. זה מוסיף עד 1 ועוד 2, או 1 ועוד 2 בתוספת 3, ולאחר מכן מחזיר את הערך, מאחסן אותו בתשובה, וprintf כאן לכן אני רואה על המסך. אז זה מה שאנחנו קוראים לאיטרטיבי גישה, שבי איטרציה רק משמעות הדבר היא באמצעות לולאה. ללולאה, לולאה בזמן, לעשות בזמן לולאה, פשוט עושה משהו שוב ושוב ושוב. 

אבל סיגמא הוא סוג של פונקציה מסודרת ב שאני יכול ליישם אותה באופן שונה. מה לגבי זה, ש רק כדי להיות די מגניב, תן לי באמת להיפטר של הרבה הסחת דעת כי פונקציה זו הוא באמת די פשוט. לגלף אותו בואו פשוט לארבעת קווי הליבה שלה כדי להיפטר מכל הערות וסוגריים מסולסלים. זהו סוג של פיצוצים יישום חלופה. בסדר, אולי לא אכפת לי-נושבת, אבל זה סוג של סקסי, בסדר, להסתכל על זה כל כך הרבה יותר בתמציתיות. עם רק ארבעה שורות של קוד, יש לי צק לשפיות זו. אם מ 'הוא פחות או שווה ל אפס, סיגמא לא הגיוני. זה אמור רק להיות ב מקרה זה למספרים חיוביים, אז אני פשוט הולך לחזור אפס באופן שרירותי כך שלפחות יש לנו כמה מה שנקרא מקרה בסיס. 

אבל כאן זה היופי. שלמותו של רעיון זה, והוסיף מספרים מ -1 עד n, או מ 'במקרה זה, ניתן לעשות זאת על ידי סוג של גלגול האחריות. ובכן, מה הוא הסכום של 1 עד מ '? ובכן, אתה יודע מה? זה אותו הדבר כסכום מ ' בתוספת הסכום של 1 עד מ 'מינוס 1. טוב אתה יודע מה? מה סיגמא של 1 מינוס מ '? ובכן, אם אתה סוג של מעקב זה באופן הגיוני, שזה אותו הדבר כמו מ 'מינוס 1 בתוספת סיגמא של מ 'מינוס 2. אז אתה יכול סוג של פשוט- זה כמו, אם אתה רק מנסה לעצבן את החבר והם שואלים אותך שאלה, אתה סוג של להגיב בשאלה, סוג של אתה יכול לשמור להעביר את האחריות. אבל מה מפתח הוא שאם אתה שומר מה שהופך את השאלה קטנה יותר ויותר וקטן יותר, אתה לא שואל מה זה סיגמא של n, מה סיגמא של n, מה סיגמא של n? אתה שואל מה סיגמא של n, מה סיגמא של n מינוס 1, מה סיגמא של 2 מינוס n? סופו של דבר השאלה שלך הולך להיות מה? מה הוא סיגמא של אחד או אפס, ערך כלשהו קטן מאוד, וברגע שאתה לקבל את זה, חבר שלך, אתה לא הולך לשאול את אותה השאלה שוב, אתה פשוט הולך להגיד, אה זה אפס. אנחנו סיימנו לשחק סוג זה של משחק מחזורי טיפש. 

אז רקורסיה היא הפעולה בתכנות של פונקציה שקורא לעצמו. תכנית זו, כאשר לוקט ולרוץ, היא הולך להתנהג בדיוק באותה הצורה, אבל מה מפתח הוא שבתוך של פונקציה שנקראת סיגמא, יש שורת קוד שבה אנחנו קוראים לעצמנו, אשר בדרך כלל להיות רע. לדוגמא, מה אם אני ראשון הידור זה, אז ודא sigma-- להפוך את סיגמא 1 ./sigma-1. מספר שלם חיובי, אנא, 50 1275. אז מה שנראה הפונקציה להיות, המבוסס על מבחן אחד, נכון. אבל מה אם אני מקבל קצת מסוכן ולמחוק את מקרה הבסיס מה שנקרא, ורק אומר, גם אני רק עושה זה יותר מסובך ממה שהיא. בואו פשוט לחשב את סיגמא על ידי לקיחה מ 'ולאחר מכן הוספה בסיגמא של מינוס מ 'אחד? ובכן, מה שהולך לקרות כאן? בואו להקטין את התצוגה. בואו להדר מחדש את התכנית, לשמור אותו, להדר מחדש את התכנית, ולאחר מכן ./sigma-1 מוכן התקרבות, הכנס מספר שלם חיובי בבקשה 50,. כמה מכם מוכנים לתודה לראות את זה? 

אישור. אז זה יכול לקרות ל מספר הסיבות, ולמען אמת זה שבוע אנחנו עומד לתת לך יותר מהם. אבל במקרה הזה, לנסות על דעת לאחור מה היה קורה כאן? אשמת פילוח, אמרנו אחרון זמן, מתייחס לקטע של זיכרון. קרה משהו רע. אבל מה זה היה מכאני שהשתבש כאן בגלל ההסרה שלי של שמקרה הבסיס מה שנקרא, שבו חזרתי ערך בקידוד קשיח? מה אתה חושב השתבש? כן. 

קהל: [לא ברור]. 1 SPEAKER: אה. שאלה טובה. אז בגודל של המספר שאני מסכם את קיבלתי כל כך גדול שהוא חרג גודלו של שטח הזיכרון. רעיון טוב, אבל לא משהו מהותי הולך לגרום התרסקות. שעלול לגרום להצפה מספר שלם, שבו הפיסות רק להתהפך ואז אנחנו טועים גדולים באמת מספר לכמו מספר שלילי, אבל זה עצמו לא יגרום להתרסקות. כי בסופו של יום int הוא עדיין 32 סיביות. אתה לא הולך ל לגנוב בטעות קצת 33rd. אבל מחשבה טובה. כן. 

קהל: [לא ברור]. SPEAKER 1: השיטה אף פעם לא מפסיק לרוץ, ואכן זה קורא לעצמו שוב ושוב ושוב ושוב ושוב, ואף אחד מן אלה פונקציות אי פעם לסיים בגלל השורה היחידה שלהם קוד קורא עצמם אחרי שוב ושוב ושוב. ומה באמת קורה כאן, ועכשיו אנחנו סוג של יכול לצייר ציורי הזה. תן לי ללכת אל תמונה רק לרגע. זוהי תמונה, ש סופו של דבר בשר את בפירוט רב יותר, ממה שקורה בתוך הזיכרון של המחשב שלך. ומתברר שעל החלק התחתון של התמונה הזאת הוא משהו שנקרא הערימה. זהו נתח של זיכרון, נתח של זיכרון RAM, זה פשוט השתמש בכל זמן פונקציה נקראת. כל פעם שאתה, המתכנת, לקרוא לפונקציה, מערכת ההפעלה, כמו Mac OS, Windows, או לינוקס, תופס חבורה של בתים, אולי כמה קילובייט, כמה מגה בייט אולי של זיכרון, מוסר אותם לך, ולאחר מכן מאפשרים לי אתה מפעיל הפונקציה שלך באמצעות כל מה שמשתנה שאתה צריך. ואם לאחר מכן לקרוא עוד פונקציה ופונקציה אחרת, אתה מקבל פרוסה נוספת של זיכרון ופרוסה נוספת של זיכרון. 

ואכן, אם מגשים הירוקים אלה מאננברג מייצג זיכרון ש, הנה מה שקורה הראשון פעם שאתה קורא סיגמא פונקציה. זה כמו לשים את מגש כמו זה על מה בתחילה ערימה ריקה. אבל אז אם מגש ש קורא לעצמו, אם אפשר לומר כך, קורא מקרה אחר של סיגמא, שזה כמו לשאול את מערכת ההפעלה, אוו, צריך זיכרון יותר קטן, תן לי את זה. ולאחר מכן הוא מקבל נערם על על גבי. אבל מה מפתח כאן הוא ש המגש הראשון הוא עדיין שם, משום שהוא מופעל מגש שני זה. עכשיו בינתיים, סיגמא קורא סיגמא, זה כמו לשאול ליותר זיכרון. מקבל נערם על כאן. סיגמא קורא סיגמא, שעוד מגש שמקבל נערם על כאן. ואם אתה ממשיך לעשות את זה, סופו של דבר, סוג של המפה זו חזותית לתרשים ש, מה קורה ל יקרה עם הערימה של מגשים? זה הולך יעלה על הסכום של זיכרון המחשב שלך יש. וברגע שהמגש הירוק הזה עולה על הקו האופקי מעל ערימה ומעל זה מילת ערימה, שאנחנו נחזור בעתיד, שזה דבר רע. הערימה היא שונה קטע של זיכרון, ואם אתה נותן להם ערימת מגשים וערימה על, אתה הולך תעלה קטע משלך של זיכרון, ותכנית אכן הולכת להתרסק. 

עכשיו במאמר מוסגר, את הרעיון הזה של רקורסיה, ולכן, בבירור יכול להוביל לבעיות, אבל זה לא בהכרח דבר רע. בגלל לשקול, לאחר כל, how-- ואולי זה לוקח קצת זמן להתרגל ל--how אלגנטי או כמה פשוט יישום זה של סיגמא היה. ואנחנו לא מתכוונים להשתמש רקורסיה כל כך הרבה בCS50, אבל בCS51, ובאמת כל כיתה שבו אתה לתפעל מבני נתונים כמו עצים, או עצי משפחה, כי יש כמה היררכיה, הוא סופר, סופר שימושי. עכשיו, במאמר מוסגר, כך שאתה כשאפתן מדעני מחשב מכיר חלק מגוגל בדיחות פנימיים, אם אתה הולך לגוגל ואתה מסתכל על מה שהוא הגדרה של, נניח, רקורסיה, להיכנס. אה-הא. במאמר מוסגר, אני עצרתי כמה. זה היה כמו 10 דקות של סחבת הבוקר. הודעה אם אתה גם גוגל "באלכסון", על ידי הטיית הראש שלך slightly-- ואז זה אחד הוא אולי הזוועתי ביותר של כל מאז שמישהו בילה כמו היום שלהם ביישום זה כמה שנות ago-- לבוא על. אה, wait-- זה באג. 

אז הפועל באחד מ אתרים הגדולים ביותר בעולם ביצים הקטנות טפשים אלה הפסחא. הם כנראה צורכים מספר לא טריוויאלי של שורות קוד רק כדי שנהיה לנו דברים קצת כיף כמו ש. אבל לפחות עכשיו אתה מקבל חלק מהבדיחות הפנימיים אלה. 

עכשיו בואו נסתכל על כמה מן שקרים לבנים אנחנו כבר אומרים לי של מנוח, ולהתחיל לקלף כמה שכבות מבחינה טכנית כך שאתה באמת מבין מה שקורה ואתה יכול להבין חלק מהאיומים, כמו Shellshock, ש עכשיו התחיל להיות על החזית של כולם תשומת לב, לפחות בתקשורת. אז הנה היא פונקציה פשוטה מאוד שמחזיר שום דבר, חלל. שמו הוא החלפה. זה לוקח בשני משתנים וזה מחזיר שום דבר. לוקח ובb. אז הפגנה מהירה. אנחנו הבאנו את אלה עד. אנחנו יכולים גם לקחת קצת לשבור כאן רק לרגע ויש לי משהו קטן לשתות. אם מישהו לא הייתי מתנגד להצטרף אותי כאן רק לרגע. מה הדעה עליך בחולצה בצבע החום? בואו למעלה. רק היום אחד. תודה לך, אם כי. בסדר, ויש לנו עולה שכאן? מה שמך? 

4 SPEAKER: לורה. 

1 SPEAKER: לורה. בואו למעלה. אז לורה, היום אתגר מאוד פשוט. נחמד לפגוש את יו. בסדר. אז יש לנו קצת חלב לכאן ו יש לנו כמה מיץ תפוזים כאן וכמה כוסות ש בהשאלה מאננברג היום. 

SPEAKER 4: Borrowed. SPEAKER 1: והולכים קדימה ואתן לך חצי כוס של זה. בסדר. ואנחנו אתן לך חצי כוס חלב. אה, ורק כדי שאתה יכול זוכר מה זה היה כמו, נזכרתי להביא זה למעלה ועל היום. אוקיי. אם לא אכפת לך, בואו נראה, אנחנו יכול לשים אותם על המשקפיים שלך אם אתה רוצה. זה יהיה העולם מהעיניים של לורה. בסדר. אז המטרה שלך, קבלה שתי כוסות נוזל כאן, חלב ומיץ תפוזים, הוא להחליף שני את התוכן כך ש מיץ תפוזים הולך לתוך כוס חלב והחלב נכנס כוס מיץ תפוזים. 

SPEAKER 4: האם אני מקבל עוד כוס? 1 SPEAKER: אני אף אני כל כך שמח שהשאלה, זה היה מדה הרבה יותר טוב אם אתה לא ביקש. אבל כן, אנחנו יכולים להציע לך שליש כוס זה ריק, כמובן. בסדר. אז להחליף את התוכן שם. נחמד מאוד. טוב מאוד. אתה עושה את זה בזהירות ראויה לציון. ושלב שלישי. בסדר. מצוין. מחיאות כפות גדולות יהיה טוב ללורה. בסדר. יש לנו מתנת פרידה קטנה בשבילך, אבל תנו לי לקחת את אלה. תודה רבה לך. אז דוגמא פשוטה, אם כי, על מנת להוכיח כי אם אתה עושה רוצה להחליף את התוכן של שתי מכולות, או בואו קוראים להם משתנה, אתה צריך קצת אחסון זמני לביים אחד מתוכן כל כך שאתה באמת יכול לעשות החלפה. אז אכן, קוד מקור זה עד כאן ב C הוא נציג בדיוק את זה. אם מיץ התפוזים היה והחלב היה ב, ואנחנו רוצים להחליף את שני, אתה יכול לנסות משהו יצירתי על ידי שפיכה אחד לתוך השני, אבל זה כנראה לא היית בסופו של טוב במיוחד. וכך אנו משתמשים כוס, שיחה שלישית זה TMP, T-M-P על ידי אמנה, ולשים את התוכן של OJ שב, לאחר מכן להחליף כוס אחת, לאחר מכן הניח את OJ לתוך כוס מקורית, ובכך השגת, בדיוק כפי ש לורה עשתה, ההחלפה. 

אז בואו לעשות בדיוק את זה. תן לי ללכת קדימה ולפתוח עד דוגמא זה נקרא למעשה "לא להחליף, "בגלל זה הוא לא כפשוט עשה כפי שאתה עלול לחשוב. אז בתכנית זו, תבחין ש אני משתמש stdio.h, חבר הוותיק שלנו. יש לי אב הטיפוס עבור החלפה שם למעלה, ש משמעות הדבר היא היישום שלה כנראה למטה, ובואו נראה מה זה עיקרי תכנית הולכת לעשות לי. אני מצהיר ראשון x int מקבל אחד, וint y מקבל שני. אז תחשוב על אלה כOJ וחלב, בהתאמה. ואז יש לי רק printf אומר x הוא זה וy הוא זה, רק כדי שאוכל מבחינה ויזואלית לראות מה קורה. אז יש לי printf בטענה שאני מחליף שני, ולאחר מכן אני מדפיס את טוען שהם החליפו, ואני להדפיס את x, y שוב. אז כאן למטה בהחלפה היא בדיוק מה שעשה לורה, ובדיוק את מה שראינו על המסך לפני רגע. 

אז בואו נלך קדימה ו יהיה מאוד מאוכזב. לא עושה שום החלפה, ולהפעיל לא החלפה, התקרבות על הפלט כאן. הזן x הוא 1, y הוא 2, החלפה החליף. x הוא עדיין 1, וy הוא עדיין 2. אז למרות שלמען אמת, זה נראה בדיוק כמו, אם כי יותר מבחינה טכנית, מה לורה עשתה, לא נראה לי לעבוד. אז מדוע זה כך? ובכן, מתברר שכאשר אנו כותבים תכנית כזאת ששניהם עיקריים, מודגשים כאן, ולאחר מכן פונקציה אחרת, כמו החלפה, מודגש כאן, ש הוא קורא, העולם נראה קצת משהו כמו מגשים אלה לפני רגע. כאשר עיקרי ראשון מקבל נקרא, זה כמו לשאול את מערכת הפעלה בשביל קצת זיכרון לכל מקומי משתנים כמו x ו y שיש עיקריים, והם בסופו ממש שם. אבל אם שיחות עיקריות להחליף, ועיקרי עובר להחליף שני טיעונים, וb, מיץ תפוזים וחלב, זה לא כמו ש מסירת מיץ התפוזים והחלב ללורה. מה מחשב עושה, זה עובר עותקים של מיץ התפוזים ועותקים של חלב ללורה, כך ש מה סופו של דבר בתוך מגש זה הוא ערך אחד ושני, או OJ וחלב, אך עותקים שלהם, כך שבשלב זה בסיפור, יש הוא OJ וחלב בכל אחד ממגשים אלה. יש אחד ושני בכל אחד ממגשים אלה, ופונקצית swap אכן פועלת. זה החלפתם בתוך של המגש השני העליון, אבל יש החלפה שלא היה השפעה. ועל סמך רק חלק עיקרון בסיסי שיש לנו דיבר על לפני, ואכן רק לפני כמה דקות, מה ש עשוי להסביר מדוע שינוי וb הפנימית של החלפה אין כל השפעה על x, y, אף על פי ש עברתי x ו y לפונקצית swap. מה מילת המפתח כאן ש אולי פשטני להסביר? אני חושב ששמעתי את זה כאן? קהל: חזור. SPEAKER 1: חזור? לא יחזור. בואו נלך עם אחד אחר. מה זה? 

קהל: [לא ברור]. 

1 SPEAKER: אוקיי, אז return-- שיכולנו לעשות את עבודת שיבה בסיפור, אבל יש הסבר פשוט יותר. קהל: היקף. SPEAKER 1: היקף. אני אקח את ההיקף. אז היקף, זוכר איפה x, y שלנו הכריזו. הם הכריזו בתוך של עיקרי ממש עד כאן. וb, בינתיים, הם הכריז ביעילות בתוך ההחלפה, לא די ב הפלטה אבל עדיין מתולתלת באזור הכללי של החלפה. וכך אכן, וb קיימים רק בתוך מגש זה מאננברג, זה נתח שני של קוד. אז אנחנו אכן משתנים העותק, אבל זה לא באמת כל כך מועיל. 

אז בואו נסתכל על רמה מעט נמוכה יותר זה. אני הולך לחזור אל ספריית המקור, ואני הולך ראשון להתקרב לכאן, ורק כדי לאשר שאני בזה חלון מסוף גדול יותר, התכנית עדיין מתנהגת ככה. נניח עכשיו שזה לא מכוון. ברור שאני רוצה להחליף ל עבודה, כך שזה מרגיש כמו באג. עכשיו אני יכול להתחיל להוסיף הרבה printf של לקוד שלי, להדפיס את x לכאן, y מעל כאן, כאן, ב כאן. אבל בכנות, זה כנראה מה ש אתה כבר עושה במשך כמה שבועות עכשיו, בשעתי עבודה ובבית בעת עבודה על psets מנסה למצוא כמה באגים. אבל תראה, אם יש לך כבר, הבעיה שהציבה שלוש מציגה לך לפקודה הנקראת GDB, שבו GDB, הבאגים גנו, יש עצמו חבורה של שלמה תכונות שלמעשה יכול נתת לנו להבין מצבים כמו זה, אבל יותר משכנע, לפתור בעיות ולמצוא באגים. אז אני הולך לעשות את זה. במקום ./noswap, אני במקום הולך לרוץ ./noswap GDB. במילים אחרות, אני הולך לרוץ שלי לא בש, החבר החדש שלנו התכנית היום. אני הולך לרוץ שלי noswap תכנית בתוך של תכנית אחרת זה נקרא GDB, אשר הוא הבאגים, ש היא תכנית שנועדה לסייע אתם בני האדם למצוא ולהסיר באגים. אז אם אני מכה הפעל כאן, יש סכום זוועתי של טקסט כי אתה באמת לא צריך לקרוא. זה בעצם הסחת דעת משורת הפקודה של, אשר אני הולך להכות בקרה-L לקום בחלק העליון יש. זוהי הפקודה GDB. אם אני רוצה להפעיל את התכנית עכשיו, כגיליון לרמות קטן על של היום שקופית מרמזת, הפעלה היא ראשונה פקודות שנועדנו להציג. ואני רק הולך להקליד רץ עד לכאן בתוך GDB, ואכן זה רץ התכנית שלי. עכשיו יש כמה נוסף תפוקות של המסך כזה, אבל זה אנאלי פשוט להיות GDB ואומר לנו מה קורה. אתה לא באמת צריך לדאוג על פרטים האישיים של עכשיו. אבל מה שבאמת מגניב על GDB, אם אני עושה את זה again-- בקרה-L מנקה את screen-- תן לי ללכת קדימה וסוג "לשבור ראשי," ובכך, כשאני מקיש Enter, הגדרה מה נקרא נקודת הפסקה בnoswap.c, שורה 16, המקום שבו GDB הבין את התכנית שלי למעשה הוא, הפונקציה שלי היא בעצם. זו אנו להתעלם לעת עתה אבל זה את הכתובת בזיכרון במיוחד של פונקציה זו. אז עכשיו כשאני מקליד לרוץ, שים לב למה זה מגניב כאן. התכנית שלי שוברת בי השורה אמר לי GDB כדי להשהות ביצוע ב. אז אני לא צריך עכשיו לשנות את הקוד שלי, להוסיף קצת printf של, הדר מחדש את זה, שידור חוזר זה, לשנות, להוסיף קצת printf של, לשמור אותו, להדר מחדש את זה, להפעיל אותו. אני רק יכול ללכת דרך התכנית שלי צעד אחר צעד אחר צעד במהירות אנושית, לא בסוג Intel-פנימי של מהירות. 

אז עכשיו שם לב הקו הזה מופיע כאן, ואם אני חוזר לתכנית שלי בgedit, שם לב שזה בעצם השורה הראשונה של קוד. יש שורה 16 ​​בgedit. יש שורה 16 ​​בתוך GDB, ואפילו למרות שממשק שחור ולבן זה אינו כמעט כמשתמש ידידותי, שזה אומר 16 קו שלא בוצעו עדיין, אבל זה עומד להיות. אז אכן, אם אני מקליד הדפסה x, לא printf, רק x הדפסה, אני מקבל ערך כלשהו מזויף יש אפס, כי x לא אותחל עדיין. אז אני הולך להקליד הבא, או, אם אתה רוצה להיות מפואר, רק n לבא. אבל כאשר אני מקליד הבא להיכנס, עכשיו שמתי לב שהוא נע על קו 17. אז מבחינה לוגית, אם אני כבר בוצע שורת 16 ועכשיו אני מקליד x הדפסה, מה אני צריך לראות? אחת. 

ועכשיו זה הוא אף מבלבל. 2 $ הוא רק דרך מפוארת של, אם אתה רוצה להתייחס לשווי שמאוחר יותר, אתה יכול להגיד "דולר לחתום על שני." זה כמו חזרה התייחסות. אבל לעת עתה, פשוט להתעלם מזה. מה שמעניין הוא מה בצד ימין של סימן השוויון. ועכשיו, אם אני מקליד הבא שוב וy הדפסה, אני צריך לראות 2. אני גם יכול כעת להדפיס x שוב, ולמען אמת, אם אני מקבל קצת מבולבל לגבי איפה אני, אני יכול להקליד רשימה לרשימה ורק לראות כמה הקשר סביב הנקודה אני בעצם ב. ועכשיו אני יכול להקליד הבא, וx יש 1. עכשיו אני מקליד הבא. אה, y הוא 2. ושוב, זה מבלבל, כי התפוקה של GDB הוא להיות מעורבב עם התפוקה שלי. אבל אם אתה לזכור, על ידי מציץ קדימה ואחורה בקוד שלך או להנחתו צד על ידי צד אולי, אתה תמצאו רואה שבאמת אני רק דריכה דרך התכנית שלי. 

אבל שים לב מה קורה בהמשך, פשוטו כמשמעו. הנה שורה 22. תן לי ללכת על זה, וכך הלאה ל23, ואם אני מדפיס x עכשיו, עדיין אחד. ואם אני מדפיס y עכשיו, עדיין אחד. אז זה לא תרגיל שימושי. אז בואו לעשות שוב זה. תן לי לחזור עד עליונה וסוג ריצה שוב. וזה אומר תכנית זה להיות מדובג החל כבר, התחיל מההתחלה. כן, בואו נעשיתי את זה שוב. והפעם בואו נעשה הבא, הבא, הבא, הבא, הבא, אבל עכשיו תתחיל להיות מעניין. עכשיו אני רוצה להיכנס החלפה, כך שאני לא להקליד הבא. אני מקליד צעד, ועכשיו שמתי לב לזה קפץ לי לשורת noswap.c 33. אם אני חוזר לgedit, מה שורת 33? זה הראשון בפועל שורת קוד הפנימי של החלפה. וזה נחמד, כי עכשיו אני יכול סוג של לחטט ולקבל סקרן על מה שקורה באמת שם. תן לי להדפיס tmp. וואו. מדוע tmp יש לי כמה ערך מטורף, מזויף אשפה? קהל: זה לא אותחל. 1 SPEAKER: זה לא אותחל. ואכן, בעת הפעלת תכנית, אתה נתון חבורה של זיכרון שלמה על ידי מערכת ההפעלה, אבל אתה לא אותחל כל ערכים, לכן כל מה שפיסות אתה רואה כאן, למרות שזה שלילי הגדול המטורף הזה מספר, רק אומר כי אלה הם השרידים מ כמה שימוש קודם של זיכרון RAM ש, אף על פי שיש לי לא את עצמי זקוק לו עדיין. אז עכשיו אני הולך קדימה וסוג הבא, ואם אני עכשיו הקלד tmp הדפסה, מה אני צריך לראות? לא משנה מה הערך של היה, הוא הטיעון הראשון, רק כמו x היה הראשון דבר שעבר ב, כך וx צריך להיות זהה, כך להדפיס tmp צריך להדפיס לי אחד. 

אז מה תראה בסט בעיה שלוש היא הדרכה של מיני על GDB, אבל מבין שזה הוא ההתחלה של מבט על כלי זה בעצם לעזור לך לפתור את הבעיות כל כך הרבה יותר ביעילות. מה אנחנו בסופו של הולך לעשות ביום רביעי הוא מתחיל לקלף כמה שכבות ולהסיר כמה גלגלים עזר. שמחרוזת הדבר שנקרא ש אנחנו השתמשנו במשך זמן מה, אנחנו הולכים לקחת לאט כי משם ממך ולהתחיל לדבר על משהו יותר אזוטרי הידועה בשם * char, אבל אנחנו הולכים לעשות זה נחמד ו בעדינות בהתחלה, למרות שמצביעים, כפי שהם נקראים, יכול לעשות כמה דברים רעים מאוד אם התעללו, על ידי התבוננות בקצת פלסטלינה מ ידידנו ניק Parlante מאוניברסיטת סטנפורד אוניברסיטה, פרופסור במחשב מדע מי להרכיב תצוגה זו של מה לבוא ביום רביעי. 

[וידאו השמעה] היי, בינקי. יתעורר. זה זמן בשביל כיף מצביע. 

'מה זה? למד על מצביעים? אה, טופי! [END הפעלת וידאו] 1 SPEAKER: זה מחכה לכם ביום רביעי. אנחנו אראה אותך אז. [וידאו השמעה] -ואז עכשיו, מחשבות עמוקות, על ידי ךייבן Farnham. 

"למה אנחנו לומדים C? למה לא +? 

[שחוק] 

[END הפעלת וידאו]