מבוא למושגי מדעי המחשב
מדעי המחשב מאפשרים לנו לתכנת, אך ניתן לבצע תכנות רב מבלי להבין את המושגים הבסיסיים במדעי המחשב.
זה לא תמיד דבר רע. כשאנחנו מתכנתים, אנחנו עובדים ברמה גבוהה יותר של הפשטה.
כשאנחנו נוהגים ברכב, אנו עוסקים רק בשניים או שלושה דוושות, הילוך והגה. אתה יכול להפעיל מכונית בבטחה מבלי שיהיה לך מושג ברור כיצד היא עובדת.
עם זאת, אם ברצונכם להפעיל מכונית בגבולות היכולות שלה, עליכם לדעת הרבה יותר על מכוניות מאשר רק על שלוש הדוושות, העברת ההילוכים וההגה.
הדבר נכון גם לגבי תכנות. עבודה יומיומית רבה יכולה להתבצע ללא הבנה מועטה או לא של מדעי המחשב. אינך צריך להבין את תורת החישוב כדי לבנות טופס "צור קשר" ב- PHP.
עם זאת, אם אתם מתכננים לכתוב קוד הדורש חישוב רציני, תצטרכו להבין קצת יותר כיצד פועל חישוב מתחת למכסה המנוע.
מטרת מאמר זה היא לספק רקע בסיסי לחישוב. אם יש עניין, ייתכן שאעקוב אחר כמה נושאים מתקדמים יותר, אך כרגע אני רוצה להסתכל על ההיגיון שמאחורי אחד ממכשירי החישוב המופשטים הפשוטים ביותר - מכונת מצב סופית .
מכונות מדינה סופיות
מכונת מצב סופי היא הפשטה מתמטית המשמשת לתכנון אלגוריתמים.
במילים פשוטות יותר, מכונת מדינה תקרא סדרת תשומות. כאשר הוא קורא קלט, הוא יעבור למצב אחר. כל מדינה מציינת לאיזה מצב לעבור, עבור קלט נתון. זה נשמע מסובך אבל זה באמת די פשוט.
דמיין מכשיר שקורא פיסת נייר ארוכה. לכל סנטימטר נייר מודפסת עליו אות אחת - האות 'a' או האות 'b'.
כאשר מכונת המדינה קוראת כל אות, היא משנה את מצבה. הנה מכונת מדינה פשוטה מאוד:
המעגלים הם " מצבים " שהמכונה יכולה להיות בהם. החיצים הם המעברים . לכן, אם אתה נמצא במצב s וקורא 'a', תעבור למצב q . אם תקרא 'a', תישאר במצב s .
אז אם נתחיל ב- s ונקרא את קלטת הנייר למעלה משמאל לימין, נקרא את ה- a ונעבור למצב q .
לאחר מכן נקרא 'b' ונחזור למצב s .
עוד 'ב' ישמור אותנו על s , ואחריו 'a' - שיחזיר אותנו למצב q . מספיק פשוט, אבל מה הטעם?
ובכן, מתברר שאפשר להריץ קלטת דרך מכונת המדינה ולספר משהו על רצף האותיות, על ידי בחינת המצב אליו נקלעתם.
במכונת המצב הפשוטה שלנו לעיל, אם נסיים במצב s , הקלטת חייבת להסתיים באות 'b'. אם נסיים במצב q , הקלטת מסתיימת באות 'a'.
זה אולי נשמע חסר טעם, אבל יש הרבה מאוד בעיות שניתן לפתור בעזרת גישה מסוג זה. דוגמה פשוטה מאוד תהיה לקבוע אם דף HTML מכיל את התגים הבאים בסדר זה:
מכונת המדינה יכולה לעבור למצב שמראה שהיא קראה את תג ה- html, לולאה עד שהיא מגיעה לתגית הראש, לולאה עד שהיא מגיעה לתג close head וכו '.
אם זה מצליח להגיע למצב הסופי, יש לך את התגים המסוימים בסדר הנכון.
ניתן להשתמש במכונות של מדינה סופית גם לייצוג מערכות רבות אחרות - כגון מכניקה של מד חניה, מכונת פופ, משאבת דלק אוטומטית וכל מיני דברים אחרים.
מכונות מדינה סופיות דטרמיניסטיות
מכונות המדינה שבחנו עד כה הן מכונות מדינה דטרמיניסטיות . מכל מדינה, יש מעבר אחד בלבד לכל קלט מותר. במילים אחרות, לא יכולים להיות שני מסלולים שיוצאים ממצב כשקוראים את האות 'a'. בהתחלה, זה נשמע טיפשי אפילו לעשות הבחנה זו.
מה מועיל מערכת החלטות אם אותה קלט יכול לגרום למעבר למדינה אחת? אתה לא יכול להגיד למחשב if x == trueואז לבצע doSomethingBigאו לבצע doSomethingSmall, נכון?
ובכן, אתה יכול סוג של מכונת מדינה.
הפלט של מכונת מדינה הוא המצב הסופי שלה. זה עובר את כל העיבודים שלו ואז קוראים את המצב הסופי ואז מבצעים פעולה. מכונת מדינה לא עושה דבר בזמן שהיא עוברת ממדינה למדינה.
הוא מעבד, וכשזה מגיע לסוף, המדינה נקראת ומשהו חיצוני מפעיל את הפעולה הרצויה (למשל, מחלק פחית סודה). זהו מושג חשוב כשמדובר במכונות מדינה סופיות לא דטרמיניסטיות .
מכונות מדינה סופיות לא דטרמיניסטיות
מכונות מדינה סופיות שאינן דטרמיניסטיות הן מכונות מדינה סופיות כאשר קלט נתון ממדינה מסוימת יכול להוביל ליותר ממצב אחד אחר.
לדוגמא, נניח שאנחנו רוצים לבנות מכונת מדינה סופית שתוכל לזהות מחרוזות אותיות ש:
- התחל באות 'a'
- ואחריהם אפס או יותר מופעים של האות 'ב'
- או, אפס או יותר מופעים של האות 'c'
- מסתיימים באות הבאה של האלף-בית.
מחרוזות תקפות יהיו:
- abbbbbbbbc
- abbbc
- acccd
- acccccd
- ac (אפס מופעים של b)
- מודעה (אפס הופעות של c)
אז הוא יזהה את האות 'a' ואחריה אפס או יותר מאותה האות של 'b' או 'c', ואחריה האות הבאה של האלף-בית.
דרך פשוטה מאוד לייצג זאת היא באמצעות מכונת מצב שנראית כמו זו שלמטה, כאשר מצב סופי של t אומר שהמחרוזת התקבלה ותואמת את התבנית.
אתה רואה את הבעיה? מנקודת המוצא s , איננו יודעים באיזו דרך לעבור. אם אנו קוראים את האות 'a', איננו יודעים אם ללכת למדינה q או r.
ישנן מספר דרכים לפתור בעיה זו. האחת היא באמצעות חזרה על המסלול. אתה פשוט לוקח את כל הדרכים האפשריות ומתעלם או חוזר מאלה שבהם אתה נתקע.
זה בעצם איך שרוב המחשבים שמשחקים בשחמט עובדים. הם בוחנים את כל האפשרויות - ואת כל האפשרויות של אותן אפשרויות - ובוחרים בדרך שנותנת להם את מספר היתרונות הגדול ביותר על פני יריבם.
האפשרות האחרת היא להמיר את המכונה הלא דטרמיניסטית למכונה דטרמיניסטית.
אחת התכונות המעניינות של מכונה לא דטרמיניסטית היא שקיים אלגוריתם להפוך כל מכונה לא דטרמיניסטית למכונה דטרמיניסטית. עם זאת, לעתים קרובות זה הרבה יותר מסובך.
למרבה המזל עבורנו, הדוגמה שלמעלה מורכבת רק מעט יותר. למעשה, זה פשוט מספיק כדי שנוכל להפוך אותו למכונה דטרמיניסטית בראשנו, ללא עזרה של אלגוריתם פורמלי.
המכונה למטה היא גרסה דטרמיניסטית של המכונה הלא דטרמיניסטית שלמעלה. במכונה למטה, מצב סופי של t או v מגיע לכל מחרוזת שמקבלת על ידי המכונה.
המודל הלא דטרמיניסטי כולל ארבעה מצבים ושישה מעברים. המודל הדטרמיניסטי כולל שש מצבים, עשרה מעברים ושני מצבים סופיים אפשריים.
זה לא כל כך הרבה יותר, אבל המורכבות בדרך כלל גוברת באופן אקספוננציאלי. מכונה לא דטרמיניסטית בגודל בינוני יכולה לייצר מכונה דטרמיניסטית ענקית לחלוטין .
ביטויים רגילים
אם עשית כל סוג של תכנות, כנראה נתקלת בביטויים רגולריים. ביטויים רגולריים ומכונות מצב סופיות שוות ערך מבחינה פונקציונלית. כל דבר שתוכל לקבל או להתאים בביטוי רגולרי, יכול להתקבל או להתאים למכונת מדינה.
לדוגמה, ניתן להתאים את הדפוס שתואר לעיל לביטוי הרגולרי: a(b*c|c*d)
לביטויים רגולריים ולמכונות מדינה סופיות יש גם אותן מגבלות. בפרט, שניהם יכולים להתאים או לקבל רק דפוסים שניתן לטפל בהם בזיכרון סופי.
אז לאיזה סוג של דפוסים הם לא יכולים להתאים? נניח שאתה רוצה להתאים רק מחרוזות של 'a' ו- 'b', כאשר יש מספר 'a' ואחריו מספר שווה של 'b'. או n 'a ואחריו n ' b, כאשר n הוא מספר כלשהו.
דוגמאות לכך יהיו:
- ab
- aabb
- aaaaaabbbbbb
- אאאאאאאאאאאאאאאאאאאאאאבבבבבבבבבבבבבבּבּבּבּ
בהתחלה זה נראה כמו עבודה קלה עבור מכונת מדינה סופית. הבעיה היא שנגמרו לך מדינות במהירות, או שתצטרך להניח מספר אינסופי של מדינות - ובנקודה זו היא כבר לא מכונת מדינה סופית .
נניח שאתה יוצר מכונת מדינה סופית שיכולה לקבל עד 20 'a ואחריה 20' b. זה עובד בסדר, עד שתקבל מחרוזת של 21 'a ואחריה 21' b - בשלב זה תצטרך לשכתב את המכונה שלך כדי לטפל במחרוזת ארוכה יותר.
לכל מחרוזת שתוכלו לזהות, יש זמן ארוך יותר שהמכונה שלכם לא יכולה לזהות מכיוון שנגמר לו הזיכרון.
זה ידוע בשם Lemma Pumping שבעצם אומר: "אם לדפוס שלך יש קטע שניתן לחזור עליו (כמו זה) לעיל, התבנית אינה רגילה".
במילים אחרות, לא ביטוי רגיל ולא אוטומט סופי ניתן לבנות כי תכיר את כל המחרוזות אל התאים לדפוס.
אם תסתכל בזהירות, תבחין כי סוג זה של דפוס שבו לכל 'a' יש 'b' תואם, נראה דומה מאוד ל- HTML. בתוך כל זוג תגים, ייתכן שיהיה לך מספר זוגי תגים תואם אחר.
לכן, אמנם ייתכן שתוכל להשתמש בביטוי רגיל או במכונת מצב סופי כדי לזהות אם לדף HTML יש את ; ואלמנטים בסדר הנכון, אינך יכול להשתמש בביטוי רגיל כדי לדעת אם דף HTML שלם תקף או לא - מכיוון ש- HTML אינו תבנית רגילה.
>,
מכונות טיורינג
אז איך מזהים דפוסים לא קבועים ?
יש מכשיר תיאורטי שדומה למכונת מדינה, המכונה מכונת טיורינג. זה דומה למכונת מדינה סופית בכך שיש לה רצועת נייר עליה היא קוראת. אבל, מכונת טיורינג יכולה למחוק ולכתוב על קלטת הנייר.
הסבר על מכונת טיורינג ייקח יותר מקום שיש לנו כאן, אך יש כמה נקודות חשובות הרלוונטיות לדיון שלנו במכונות מדינה סופיות וביטויים רגולריים.
מכונות טיורינג הינן שלמות מבחינה חישובית - כלומר כל מה שניתן לחשב, יכול להיות מחושב במכונת טיורינג.
מכיוון שמכונת טיורינג יכולה לכתוב וגם לקרוא מהקלטת הנייר, היא אינה מוגבלת למספר סופי של מדינות. ניתן להניח כי קלטת הנייר אורכה אינסופית. כמובן שלמחשבים בפועל אין כמות אינסופית של זיכרון. אבל בדרך כלל הם מכילים מספיק זיכרון כדי שלא תפגע בגבול סוג הבעיות שהם מעבדים.
מכונות טיורינג נותנות לנו מכשיר מכני דמיוני המאפשר לנו לדמיין ולהבין כיצד פועל תהליך החישוב. זה שימושי במיוחד בהבנת גבולות החישוב. אם יש עניין אעשה מאמר נוסף על מכונות טיורינג בעתיד.
מדוע זה משנה?
אז מה הטעם? איך זה יעזור לך ליצור את הטופס הבא של PHP?
ללא קשר למגבלותיהם, מכונות המדינה הן מושג מרכזי מאוד למחשוב. בפרט, חשוב כי עבור כל מכונת מצב לא דטרמיניסטית שתוכלו לעצב, קיימת מכונת מצב דטרמיניסטית שעושה את אותו הדבר.
זוהי נקודת מפתח, מכיוון שמשמעותה שאתה יכול לעצב את האלגוריתם שלך בכל דרך שהכי קל לחשוב עליה. ברגע שיש לך אלגוריתם עובד, אתה יכול להמיר אותו לכל צורה שהיא היעילה ביותר.
ההבנה שמכונות מדינה סופיות וביטויים רגולריים הן שוות ערך מבחינה פונקציונלית פותחת כמה שימושים מעניינים להפליא למנועי ביטוי רגיל - במיוחד כשמדובר ביצירת כללים עסקיים שניתן לשנות ללא הידור מחדש של מערכת.
בסיס במדעי המחשב מאפשר לך לקחת בעיה שאתה לא יודע לפתור ולנמק: “אני לא יודע איך לפתור X, אבל אני יודע לפתור את Y. ואני יודע להמיר פתרון עבור Y לפיתרון ל- X. לכן אני יודע עכשיו לפתור את X. "
אם אתה אוהב מאמר זה, תוכל ליהנות מערוץ היוטיוב שלי שבו אני יוצר מדי פעם סרטון או סרט מצויר על היבט כלשהו של יצירת תוכנה. יש לי גם רשימת תפוצה לאנשים שרוצים לקבל דוא"ל מדי פעם כשאני מפיק משהו חדש.
פורסם במקור ב blog.markshead.com ב -11 בפברואר 2018.