אלפבית (Alphabet)🔥 גבוה · מתוך 1 מבחנים▼
קבוצה סופית ולא ריקה של סמלים המשמשים לבניית מילים.
הרחבה ←
מילה (String)🔥 גבוה · מתוך 1 מבחנים▼
סדרה סופית של סמלים מתוך אלפבית נתון.
הרחבה ←
שפה (Language)🔥 גבוה · מתוך 1 מבחנים▼
קבוצה של מילים מעל אלפבית נתון.
הרחבה ←
אוטומט סופי דטרמיניסטי (DFA)🔥 גבוה · מתוך 1 מבחנים▼
מודל חישובי המקבל או דוחה מילים על בסיס מעברים דטרמיניסטיים בין מצבים.
הרחבה ←
אוטומט סופי לא דטרמיניסטי (NFA)🔥 גבוה · מתוך 1 מבחנים▼
מודל חישובי המאפשר מספר מעברים אפשריים ממצב נתון עבור סמל קלט נתון.
הרחבה ←
ביטוי רגולרי (Regular Expression)🔥 גבוה · מתוך 1 מבחנים▼
דרך קומפקטית לתיאור שפות רגולריות באמצעות אופרטורים מוגדרים.
הרחבה ←
למת הניפוח לשפות רגולריות (Pumping Lemma for Regular Languages)🔥 גבוה▼
כלי תיאורטי המשמש להוכחה ששפה מסוימת אינה רגולרית.
הרחבה ←
דקדוק חסר הקשר (Context-Free Grammar - CFG)🔥 גבוה · מתוך 1 מבחנים▼
מערכת כללים פורמלית ליצירת שפות, שבה צד שמאל של כל כלל הוא משתנה יחיד.
הרחבה ←
אוטומט מחסנית (Pushdown Automaton - PDA)🔥 גבוה▼
מודל חישובי בעל זיכרון מחסנית, המקביל בכוחו לדקדוקים חסרי הקשר.
הרחבה ←
למת הניפוח לשפות חסרות הקשר (Pumping Lemma for CFLs)🔥 גבוה · מתוך 1 מבחנים▼
כלי תיאורטי המשמש להוכחה ששפה מסוימת אינה חסרת הקשר.
הרחבה ←
מכונת טיורינג (Turing Machine - TM)🔥 גבוה · מתוך 1 מבחנים▼
מודל חישובי תיאורטי בעל סרט אינסופי, הנחשב למודל החזק ביותר של חישוב.
הרחבה ←
תזת צ'רץ'-טיורינג (Church-Turing Thesis)בינוני▼
ההשערה שכל פונקציה שניתנת לחישוב באופן אינטואיטיבי ניתנת לחישוב על ידי מכונת טיורינג.
הרחבה ←
שפה כריעה (Decidable Language)🔥 גבוה · מתוך 1 מבחנים▼
שפה שעבורה קיימת מכונת טיורינג שעוצרת על כל קלט ומכריעה אם הקלט בשפה או לא.
הרחבה ←
שפה ניתנת לזיהוי (Recognizable Language)🔥 גבוה · מתוך 1 מבחנים▼
שפה שעבורה קיימת מכונת טיורינג שעוצרת ומקבלת את כל המילים בשפה, ועשויה לא לעצור על מילים שאינן בשפה.
הרחבה ←
בעיית העצירה (Halting Problem)🔥 גבוה · מתוך 1 מבחנים▼
הבעיה הבלתי כריעה של קביעה האם מכונת טיורינג נתונה תעצור על קלט נתון.
הרחבה ←
רדוקציה (Reduction)🔥 גבוה · מתוך 1 מבחנים▼
טכניקה להוכחת אי-כריעות או שלמות NP של בעיה על ידי המרתה לבעיה אחרת.
הרחבה ←
מחלקת P (Class P)🔥 גבוה▼
מחלקת בעיות ההכרעה שניתנות לפתרון בזמן פולינומיאלי על ידי מכונת טיורינג דטרמיניסטית.
הרחבה ←
מחלקת NP (Class NP)🔥 גבוה · מתוך 1 מבחנים▼
מחלקת בעיות ההכרעה שניתנות לאימות בזמן פולינומיאלי על ידי מכונת טיורינג דטרמיניסטית.
הרחבה ←
בעיה שלמה ל-NP (NP-Complete Problem)🔥 גבוה · מתוך 1 מבחנים▼
בעיה במחלקת NP שכל בעיה אחרת ב-NP ניתנת לרדוקציה אליה בזמן פולינומיאלי.
הרחבה ←
אי-כריעות (Undecidability)🔥 גבוה · מתוך 1 מבחנים▼
תכונה של בעיה שאין אלגוריתם (מכונת טיורינג) שיכול לפתור אותה עבור כל קלט.
הרחבה ←
חישוביות (Computability)בינוני▼
ענף במדעי המחשב החוקר אילו בעיות ניתנות לפתרון אלגוריתמי.
הרחבה ←
סיבוכיות (Complexity)בינוני▼
ענף במדעי המחשב החוקר את משאבי החישוב (זמן וזיכרון) הנדרשים לפתרון בעיות.
הרחבה ←