ⓘ Free online encyclopedia. Did you know? page 205




                                               

קשת ירחית

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

                                               

משטח נגיעה

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

                                               

בחירה מהירה (אלגוריתם)

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

                                               

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

אלגוריתם גרובר הוא אלגוריתם קוונטי לחיפוש במבנה נתונים שאינו ממויין. האלגוריתם הומצא בשנת 1996 על ידי לוב גרובר. בעוד אלגוריתם קלאסי הפותר בעיה דומה מצריך O {\displaystyle \left.O\right.} גישות אל מערך הנתונים על מנת למצוא ערך מבוקש, האלגוריתם של ...

                                               

חיפוש אקספוננציאלי

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

                                               

חיפוש בינארי

חיפוש בינארי הוא אלגוריתם לחיפוש, כלומר למציאת מקומו של איבר במערך ממוין. סוג החיפוש הנ״ל נקרא ״בינארי״ מכיוון שהאלגוריתם מחפש או בצד הימני או בצד השמאלי של המערך, או פה או פה. כמו לומר: או 0 או 1, דהיינו ״בינארי״ ולכן ״חיפוש בינארי״.

                                               

חיפוש לעומק איטרטיבי מעמיק

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

                                               

חיפוש מקומי

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

                                               

מיון (אלגוריתם)

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

                                               

מיון בועות

מיון בועות, הידוע גם בכינוי מיון החלפה הוא מיון השוואתי פשוט הפועל בסיבוכיות של Θ {\displaystyle \ \Theta }. המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך: האלמנטים הכבדים בכיוון אחד, והקלים בכיוון ההפוך, וכך גם בינם לבין עצמם.

                                               

מיון בחירה

מיון בחירה הוא אלגוריתם מיון השוואתי פשוט אך לא יעיל. זמן הריצה הממוצע של האלגוריתם הוא Θ n 2 {\displaystyle \Theta \leftn^{2}\right} פעולות. מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש Θ 1 {\displaystyle \Theta \left1\right}.

                                               

מיון בסיס

מיון בסיס הוא אלגוריתם מיון של מספרים המסתמך על כך שמספר הספרות בייצוג המספרים חסום על ידי קבוע. ניתן לממש מיון בסיס כמיון יציב, כלומר מיון ששומר על הסדר הפנימי בין שני ערכים זהים. מיון הבסיס מתבצע בדרך כלל בזמן ריצה של O n ⋅ k {\displaystyle \ O ...

                                               

מיון הכנסה

מיון הכנסה הוא אלגוריתם מיון השוואתי פשוט. הוא יעיל עבור רשימות קטנות ועבור רשימות שהן כבר ממויינות ברובן. זמן הריצה הממוצע של האלגוריתם הוא O n 2 {\displaystyle O\leftn^{2}\right} פעולות בדומה למיון בועות.

                                               

מיון חיצוני

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

                                               

מיון אקראי

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

                                               

מיון מסרק

מיון מסרק הוא אלגוריתם מיון פשוט יחסית שתוכנן במקור על ידי Włodzimierz Dobosiewicz ב-1980. לאחר מכן הוא התגלה מחדש על ידי סטיבן לייסי וריצרד בוקס בשנת 1991. מיון מסרק הוא שיפור של מיון בועות.

                                               

מיון ספגטי

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

                                               

מיון שייקר

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

                                               

מיון מיזוג

מיון מיזוג הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים. סיבוכיות זמן ריצה: O) {\displaystyle \ O)}. סיבוכיות זיכרון: O {\displaystyle \ O}

                                               

מיון מנייה

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

                                               

מיון ערימה

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

                                               

מיון של

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

                                               

מערכות מורכבות מסתגלות

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

                                               

סיבוכיות מעגלים

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

                                               

סיבוכיות מקום

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

                                               

שיטת הפוטנציאל

בשיטה מגדירים "פונקציית פוטנציאל", Φ, המקבלת מצב של המבנה ומחזירה מספר חיובי שבאופן אינטואיטיבי ניתן לחשוב עליו כעל "אנרגיה פוטנציאלית" של המצב. את העלות לשיעורין מחשבים בעזרת השינוי בפוטנציאל, יחד עם העלות האמיתית. כלומר, אם נסמן את המצבים ב-D i ...

                                               

אלגוריתם דויטש-גוזה

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

                                               

אלגוריתם שור

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

                                               

Bixby (עוזרת וירטואלית)

Bixby היא עוזרת וירטואלית שפותחה על ידי סמסונג. ב־20 במרץ 2017 הודיעה סמסונג על השקת עוזרת דיגיטלית מופעלת בקול בשם "Bixby". ביקסבי הוצגה לצד Samsung Galaxy S8 וסמסונג גלקסי S8+. Bixby זמינה גם במכשירי גלקסי ישנים יותר שפועלת בהם מערכת ההפעלה אנד ...

                                               

CarPlay

CarPlay הוא תקן המאפשר לרדיו או ליחידת הראש ברכב להפוך למסך ובקר עבור מכשיר האייפון של חברת אפל. הוא זמין עבור אייפון 5 ואילך עם מערכת הפעלה iOS 7.1 לפחות. קיה ויונדאי היו הראשונות אשר שילבו את מערכת CarPlay כבר בשנת 2014 בדגמי Soul של קיה; ב־201 ...

                                               

Google Assistant

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

                                               

ד"ר סבייטסו

ד"ר סבייטסו היא תוכנת בינה מלאכותית וסינתזת דיבור שיצאה לאור בשנת 1991, ונוצרה על ידי חברת Creative Labs. התוכנה הייתה סימולציה של פסיכולוג שניהל דיאלוג עם המשתמש. התוכנה יועדה למחשבים אישיים מבוססי מערכת ההפעלה MS-DOS.

                                               

אוטומט מחסנית

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

                                               

אוטומט סופי

בתורת החישוביות במדעי המחשב, אוטומט סופי הוא מכונה מופשטת בעלת זיכרון מוגבל בגודלו, המגדירה שפה פורמלית רגולרית. קיימים שני סוגים של אוטומטים סופיים: אוטומט סופי דטרמיניסטי – ‏אס"ד DFA –‏ Deterministic Finite Automaton אוטומט סופי לא דטרמיניסטי – ...

                                               

אוטומט סופי דטרמיניסטי

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

                                               

אוטומט סופי לא דטרמיניסטי

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

                                               

חוק 30

חוק 30 הוא חוק בינארי חד-ממדי של אוטומט תאי שהוצג על ידי סטיבן וולפרם בשנת 1983. וולפרם תיאר אותו כ"החוק האהוב עלי בכל הזמנים" ופירט עליו בספרו, "A New Kind of Science". לפי שיטת הסיווג של וולפרם, חוק 30 הוא חוק ברמה 3, המציג התנהגות כאוטית. חוק ...

                                               

סביבת מור

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

                                               

סביבת פון נוימן

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

                                               

תורת האוטומטים

קיימים שני סוגים של אוטומטים סופיים – אוטומט סופי דטרמיניסטי DFA –‏ Deterministic Finite Automaton ואוטומט סופי לא דטרמיניסטי NFA –‏ Nondeterministic Finite Automaton. ניתן לתאר אוטומט סופי דטרמיניסטי באמצעות קבוצה סופית של מצבים, המשמשים את האוט ...

                                               

ביטוי רגולרי

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

                                               

דקדוק חופשי-הקשר

בשפות פורמליות, דקדוק חופשי-הקשר הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה A → α {\displaystyle \ A\to \alpha } כאשר A {\displaystyle \ A} הוא משתנה דקדוקי ואילו α {\displaystyle \ \alpha } היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דק ...

                                               

דקדוק רגולרי

דקדוק רגולרי G {\displaystyle G} מוגדר על ידי הרביעייה G = N, Σ, P, S {\displaystyle G=N,\Sigma,P,S} בדומה לדקדוק חופשי-הקשר אך עם כללי יצירה מוגבלים יותר: A → a B {\displaystyle A\to aB} כך ש- B {\displaystyle B} הוא משתנה A → ϵ {\displaystyle A ...

                                               

מונואיד חופשי

קיימות מספר הגדרות שונות למונואיד חופשי. מונואיד חופשי {\displaystyle F,\cdot,1_{F},S} הוא רביעייה סדורה של קבוצה F {\displaystyle F}, פעולה ⋅: F × F → F {\displaystyle \cdot:F\times F\rightarrow F}, איבר 1 F ∈ F {\displaystyle 1_{F}\in F}, וקבוצ ...

                                               

שפה דלילה

בתורת החישוביות והסיבוכיות, שפה דלילה היא שפה שמכילה "קצת" מילים. באופן פורמלי: שפה L תיקרא דלילה אם קיים פולינום p {\displaystyle p} כך שעבור כל n ∈ N {\displaystyle n\in N} מספר המילים מאורך n בשפה קטן או שווה ל- p {\displaystyle p}. כלומר, ∀ n ...

                                               

שפה חופשית הקשר

במדעי המחשב, שפה חופשית הקשר היא שפה פורמלית אשר קיים דקדוק חסר הקשר המגדיר אותה; כלומר, שפה L {\displaystyle \ L} היא שפה חופשית הקשר אם קיים דקדוק חסר הקשר G {\displaystyle \ G} כך ש- L {\displaystyle \ L} היא אוסף כל המילים שניתן לגזור מהסימן ...

                                               

שפה רגולרית

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

                                               

מודל מרקוב חבוי

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

                                               

עץ חיפוש

עבור עץ G וצמתים v,u תת-עץ של G ששורשו v הוא עץ מכוון שצמתיו הם v עצמו וכל הצאצאים של v, והקשתות שלו הן הקשתות המחברות צמתים אלו ב- G. עלה הוא צומת ללא צאצאים. u אב-קדמון של v אם v צאצא של u. צומת פנימי הוא צומת שאינו עלה. גובה של צומת v הוא מספר ...

                                               

עץ 2-3

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