פורטל:מדעי המחשב/תמונה נבחרת/גלריה

עריכהתמונה נבחרת

1

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

3

אוטומט סופי לא דטרמיניסטי
במצב Q1 אם הקלט הוא הספרה 1 האוטומט יכול לעבור למצב Q2 או למצב Q4. אותו הדבר לגבי קליטת הספרה 0 - האוטומט יכול לבחור לעבור או למצב Q6 או למצב Q8.

4

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

5

ההיסטוריה של שפות התכנות וההקשרים ביניהן

6


עץ בינארי לא מאוזן (אינו עץ AVL)	אותו העץ לאחר איזון (זהו עץ AVL)

עץ AVL הוא עץ חיפוש מאוזן, שבו הפרש גובהם של תת-העצים הבנים של כל צומת הוא לכל היותר 1. תכונה זו מבטיחה שניתן יהיה לחפש בעץ ולהכניס או להוציא ממנו נתונים בסיבוכיות של $\ O(\log n)$ במקרה הגרוע ביותר, כאשר $\ n$ הוא מספר האיברים בעץ.

7

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

8

שם	סימול גודל	ערכים וחזקאות (בביטים)	בסיס 16	בסיס 10
kilo	K	2¹⁰ = 1,024	= 16^2.5	> 10³
mega	M	2²⁰ = 1,048,576	= 16⁵	> 10⁶
giga	G	2³⁰ = 1,073,741,824	= 16^7.5	> 10⁹
tera	T	2⁴⁰ = 1,099,511,627,776	= 16¹⁰	> 10¹²
peta	P	2⁵⁰ = 1,125,899,906,842,624	= 16^12.5	> 10¹⁵
exa	E	2⁶⁰ = 1,152,921,504,606,846,976	= 16¹⁵	> 10¹⁸
zetta	Z	2⁷⁰ = 1,180,591,620,717,411,303,424	= 16^17.5	> 10²¹
yotta	Y	2⁸⁰ = 1,208,925,819,614,629,174,706,176	= 16²⁰	> 10²⁴

יחידות מידה מבוססות סיביות

9

דוגמה לרדוקציה פולינומית מבעיית הספיקות ‎CNF-SAT‎ לבעיית כיסוי הקודקודים
כאן הפסוק הנתון הוא $(A\lor B)\land (\lnot A\lor \lnot B\lor \lnot C)\land (\lnot A\lor B\lor C)$
וההשמה המספקת את הפסוק היא ${\Big \{}A,B',C{\Big \}}$

10

תיאור מחלקות הסיבוכיות והקשרים ביניהן כאשר מקבלים את ההשערה הרווחת כי P≠NP

11

מבחן טיורינג הוא כינוי למבחן שהציע אלן טיורינג בשנת 1950, במאמר שפרסם בכתב העת Mind, כדרך לוודא האם למכונה יש בינה מלאכותית. המבחן נעשה בדרך הבאה: שופט (C) מקיים דיאלוג בשפה טבעית, עם שני גורמים סמויים מעיניו, האחד מהם אדם (B) והשני מכונה (A). אם השופט אינו מסוגל לקבוע בביטחון מי האדם ומי המכונה, אז המכונה עברה בהצלחה את המבחן.

12

8
7
6
5
4
3
2
1
	א	ב	ג	ד	ה	ו	ז	ח

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

13

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

14

קוד של C# לחישוב שורשים של פונקציה בעזרת שיטת ניוטון-רפסון ושיטת החצייה.

15

מערכת הצפנה המבוססת על מפתח פומבי
(אליס ובוב מעבירים ביניהם מידע. איב מצותתת)

16

$\,{\bigg \Downarrow }$

דוגמה למיון סלים

17

  MULTIPLY B BY B GIVING B-SQUARED.  
  MULTIPLY 4 BY A GIVING FOUR-A.  
  MULTIPLY FOUR-A BY C GIVING FOUR-A-C.  
  SUBTRACT FOUR-A-C FROM B-SQUARED GIVING RESULT-1.  
  COMPUTE RESULT-2 = RESULT-1 ** .5.
  SUBTRACT B FROM RESULT-2 GIVING NUMERATOR.
  MULTIPLY 2 BY A GIVING DENOMINATOR.
  DIVIDE NUMERATOR BY DENOMINATOR GIVING X.

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

18

בתורת הקודים, מרחק המינג בין שתי מחרוזות בעלות אורך זהה, הוא מספר המקומות שבהם סימנים מקבילים בשתי המחרוזות שונים זה מזה.
בתמונה: לכל שני קודקודים סמוכים, מרחק המינג 1. מרחק המינג בין המחרוזת 0100 למחרוזת 1001 הוא 3 (מספר הצלעות במסלול האדום).

19

דוגמה ליצירת פנים אנושיות באמצעות גרפיקה ממוחשבת

20

סמלים אמריקאים של השערים הלוגיים ונוסחאותיהם הבוליאניות

21

מחקר מתמטי של אומנות האוריגמי היפנית גילה שחישוב דרך הקיפול של דגמי אוריגמי היא בעיה NP שלמה.

22

דוגמה להעברת מפתח קוונטית

23

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

24


סדר סריקת הקודקודים בחיפוש לעומק (DFS)	סדר סריקת הקודקודים בחיפוש לרוחב (BFS)

25

// HelloWorld.java
public class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}

גרסת JAVA לתוכנית Hello world

26

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

27

סכמת שיטת ההצפנה DES

28

דוגמת הרצה של אלגוריתם מיון ערימה

29

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

בתמונה: שכיחות אותיות בעברית.

30

מטריצת שכנות (adjacency matrix) היא שיטת יצוג מקובלת לגרף כללי.
כל צומת מיוצג על ידי שורה ועל ידי עמודה. תא $\ (i,j)$ במטריצה מכיל "1" אם ישנה בגרף קשת מהצומת של $\ i$ לצומת של $\ j$ , ו-"0" אחרת.

31

 <head>
 	<title>VBScript Example</title>
 </head>
 <body> <% 
 	'Grab current time from Now() function.
 	Dim timeValue
 	timeValue = Now  %>
 	The time, in 24-hour format, is
       <%=Hour(timeValue)%>:<%=Minute(timeValue)%>:<%=Second(timeValue)%>.
 </body>

קוד מקור בשפת התכנות VBScript אשר מציג את השעה הנוכחית

32

דוגמת הרצה של האלגוריתם של פרים, אלגוריתם חמדן המשמש למציאת עץ פורש מינימלי בגרף לא מכוון

33

$\,A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0\end{cases}}$

פונקציית אקרמן היא דוגמה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית

34

אוטומט מחסנית המקבל את השפה חופשית ההקשר $\{0^{n}1^{n}\mid n\geq 0\}$

35

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

36

      If ''condition'' then
        Begin
          ''statementTrue'';
        End
      Else
        Begin
          ''statementFalse'';
        End;

תחביר פקודת if בשפת Pascal

37

מפת כרומוזום X אנושי (מתוך אתר NCBI); מיפוי גנום האדם הוא אחד מהישגי הביואינפורמטיקה

38

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

39

איטרציה אחת של אלגוריתם מיון מהיר.
5 הוא "איבר הציר"; האיברים הצבועים באדום הם האיברים הגדולים מ-5; האיברים הצבועים בכחול הם האיברים שקטנים או שווים ל-5.

40

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

41

מכונת טיורינג שקוראת מספר בינארי וכותבת את המספר הנגדי לו בשיטת המשלים ל-2

42

באמצעות תוכנה לזיהוי תווים אופטי, המחשב יכול לפענח את התווים בקובץ תמונה

43

גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה

44

השלבים הראשונים באלגוריתם של ג'ונסון למציאת מסלולים קצרים בגרף ממושקל ומכוון בין כל שני זוגות צמתים.

משמאל לימין: הגרף המקורי עם משקלות שליליים ; הוספת צומת חדש

\ q

וקשת במשקל 0 מ-

\ q

אל כל

\ v\in V

והרצת אלגוריתם בלמן פורד על הצומת

\ q

; תיקון המשקלות בגרף המקורי.

45

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

46

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

47

סימון	הגדרה	הגדרה מתמטית
$f(n)\in O(g(n))$	חסם עליון אסימפטוטי	$\limsup _{n\to \infty }\left\|{\tfrac {f(n)}{g(n)}}\right\|<\infty$
$f(n)\in o(g(n))$	זניח אסימפטוטית	$\lim _{n\to \infty }{\tfrac {f(n)}{g(n)}}=0$
$f(n)\in \Omega (g(n))$	חסם תחתון אסימפטוטי	$\liminf _{n\to \infty }\left\|{\tfrac {f(n)}{g(n)}}\right\|>0$
$f(n)\in \omega (g(n))$	שולט אסימפטוטית	$\lim _{n\to \infty }{\tfrac {f(n)}{g(n)}}=\infty$
$f(n)\in \Theta (g(n))$	חסם הדוק אסימפטוטית	$0<\liminf _{n\to \infty }\left\|{\tfrac {f(n)}{g(n)}}\right\|\leq \limsup _{n\to \infty }\left\|{\tfrac {f(n)}{g(n)}}\right\|<\infty$

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

48

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

49

    with Ada.Integer_Text_IO;

    procedure Factorial is
         Counter   : Integer := 5;
         Factorial : Integer := 1;
    begin
         while Counter > 0 loop
           Factorial := Factorial * Counter;
           Counter   := Counter - 1;
         end loop;

         Ada.Integer_Text_IO.Put (Factorial);
    end Main;

שימוש בלולאת While בתוכנית מחשב בשפת Ada המחשבת !5

50

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

51

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

52


תמונה עם "רעשים"	התמונה לאחר ניקוי באמצעות פילטרים

עיבוד תמונה

53

הגדרה כנוסחת נסיגה :

$F_{n}={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\F_{n-1}+F_{n-2}&{\mbox{if }}n>1.\\\end{cases}}$

הגדרה מפורשת:

$\ F_{n}={\frac {1}{\sqrt {5}}}\left(\phi _{+}^{n}-\phi _{-}^{n}\right)$ כאשר $\ \phi _{\pm }={\frac {1\pm {\sqrt {5}}}{2}}$

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

54

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i-1;
        while j ≥ 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j-1;
        end;
        A[j+1] := value;
    end;
end;

פסאודו קוד של מיון הכנסה

55

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

56


0_hex	=	0_dec	=	0_oct	0	0	0	0
1_hex	=	1_dec	=	1_oct	1	0	0	0
2_hex	=	2_dec	=	2_oct	0	1	0	0
3_hex	=	3_dec	=	3_oct	1	1	0	0

4_hex	=	4_dec	=	4_oct	0	0	1	0
5_hex	=	5_dec	=	5_oct	1	0	1	0
6_hex	=	6_dec	=	6_oct	0	1	1	0
7_hex	=	7_dec	=	7_oct	1	1	1	0

8_hex	=	8_dec	=	10_oct	0	0	0	1
9_hex	=	9_dec	=	11_oct	1	0	0	1
A_hex	=	10_dec	=	12_oct	0	1	0	1
B_hex	=	11_dec	=	13_oct	1	1	0	1

C_hex	=	12_dec	=	14_oct	0	0	1	1
D_hex	=	13_dec	=	15_oct	1	0	1	1
E_hex	=	14_dec	=	16_oct	0	1	1	1
F_hex	=	15_dec	=	17_oct	1	1	1	1

טבלת המרה בין מספרים בבסיסים שונים.
משמאל לימין: בסיס בינארי (בסיס 2), בסיס אוקטלי (בסיס 8), השיטה העשרונית (בסיס 10), בסיס הקסדצימלי (בסיס 16)

57

תהליך (Process) עם שני תהליכונים (Thread)
מערכות הפעלה מודרניות מאפשרות לנהל במסגרת ריצה של תהליך מספר תהליכונים הרצים במקביל. במערכות אלו כל תהליך חדש מתחיל את ביצועו באמצעות 'תהליכון ראשי' אשר עשוי בהמשך ליצור תהליכונים נוספים. מנגנון הריצה באמצעות תהליכונים מאפשר לספק למשתמש במערכת ההפעלה מהירות תגובה ורציפות פעולה כאשר התהליך (יישום) מבצע כמה משימות במקביל.

58

הגרף השלם

\ K_{5}

הגרף השלם

\ K_{4}

גרף מישורי הוא גרף שניתן לצייר במישור מבלי שהקשתות יחתכו זו את זו (חוץ מאשר בצומתי הגרף).
בתמונה:

\ K_{4}

הוא גרף מישורי ואילו

\ K_{5}

אינו מישורי.

59

תיאור פעולת חיפוש עבור מבנה נתונים מסוג עץ B

60

דוגמה לבעיית הסוכן הנוסע:

מציאת הדרך הקצרה ביותר, מבין 43,589,145,600 דרכים אפשריות, לעבור ב-15 ערים מרכזיות בגרמניה.

61

מודל צופן זרם סינכרוני

62

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

63

רשימת בעיות NP-שלמות.
מכל בעיה בגרף, קיימת רדוקציה לבעיה הבאה.

64

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

65

גרף מכוון שבו מסומנים הרכיבים הקשירים היטב.

66

תרשים המתאר פעולת מהדר התומך במספר שפות ובמספר יעדי הרצה

67

דוגמת הרצה של אלגוריתם מיון מיזוג עבור מערך בגודל 7 המכיל את הערכים: 38,27,43,3,9,82,10.

68

במחשב קוונטי, קיוביט (סיבית קוונטית) הוא מצב קוונטי של חלקיק בודד בעל 2 רמות אנרגיה, אשר לרוב מצוינות כ- $|0\rangle$ ו- $|1\rangle$ , או כ- $|\uparrow \rangle$ ו- $|\downarrow \rangle$ .

69

רשימה מקושרת רגילה

רשימה מקושרת דו-כוונית

רשימה מקושרת מעגלית

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

70

תבנית:תמונה מומלצת 27 באפריל 2017

71

פורטל:מדעי המחשב/תמונה נבחרת/71

< בחזרה לפורטל

פורטל:מדעי המחשב/תמונה נבחרת/גלריה

תפריט ניווט

חיפוש