פורטל:מדעי המחשב/מאמר נבחר/אוסף

מתוך ויקיפדיה, האנציקלופדיה החופשית

1

עץ פילוגנטי מבוסס על נתוני RNA ובו נראית ההפרדה בין חיידקים, חיידקים קדומים ואיקריוטיים
עץ פילוגנטי מבוסס על נתוני RNA ובו נראית ההפרדה בין חיידקים, חיידקים קדומים ואיקריוטיים

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

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

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

2

משחק מגדלי האנוי עשוי עץ לבוד
משחק מגדלי האנוי עשוי עץ לבוד

מגדלי האנויאנגלית: Towers of Hanoi) הוא משחק חידה מתמטי, שמקורו בסוף המאה ה-19. המשחק הוא אמצעי הדגמה פופולרי לעקרון הרקורסיה ולמושגים בסיסיים אחרים בקומבינטוריקה ובמדעי המחשב.

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

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

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

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

3

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

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

4

שפת תכנות היא אוסף של חוקים תחביריים (Syntax) וסמנטיים (Semantic) שבאמצעותם ניתן להגדיר למחשב באופן מפורט את הפעולות שעליו לבצע במצבים שונים, על סוגי קלט שונים. המושג שפת מחשב (Computer Language), הוא מושג רחב מאשר שפת תכנות (Programming Language) ולכן השימוש בו נפוץ יותר.

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

5

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

לפי קוד המינג, ממוספרות n הסיביות של מילת הקוד משמאל לימין, כאשר המספר של הסיבית השמאלית ביותר הוא 1, של זו שמימין לה 2, וכן הלאה. כל הסיביות שמספרן הסידורי הוא חזקה שלמה של 2 (סיבית מספר 8,4,2,1, וכן הלאה) הן סיביות ביקורת, ואילו שאר הסיביות (3,5,6,7 וכן הלאה) הן סיביות נתונים.

6

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

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

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

7

שער הדמר של קיוביט בודד
שער הדמר של קיוביט בודד

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

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

8

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

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

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

9

משולש שרפינסקי - רקורסיה של משולשים אשר יוצרת סריג פרקטלי
משולש שרפינסקי - רקורסיה של משולשים אשר יוצרת סריג פרקטלי

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

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

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

אלגוריתם רקורסיבי הוא אלגוריתם אשר על מנת לפתור בעיה מסוימת, מפעיל את עצמו על מקרים פשוטים יותר של הבעיה (ובמקרים רבים: על תתי בעיות).

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

10

Data Encryption Standard (בראשי תיבות: DES), הוא תקן הצפנת נתונים שפותח ב־1975 על ידי IBM בשיתוף פעולה עם הסוכנות לביטחון לאומי. האלגוריתם התקבל בשנת 1976 כחלק מדרישת תקן עבור הממשל האמריקאי להצפנת נתונים בעולם האזרחי ושימש בתפקיד זה עד נובמבר 2001, אז הוחלף בתקן החדש Advanced Encryption Standard, שהינו בטוח ומהיר מקודמו. למרות זאת, צופן DES עדיין נמצא בשימוש נרחב בעיקר בתחום הבנקאות.

צופן DES הוא צופן סימטרי איטרטיבי, כלומר פונקציית ההצפנה מתבצעת באופן חוזר ונשנה שש-עשרה פעמים ומשתייך לתת-המחלקה של צופנים סימטריים הקרויה צופן גושים (Block Ciphers), המצפין גושי מידע גדולים (במקרה של DES באורך 64 סיביות), בעזרת מפתח סודי באורך 64 סיביות (שמתוכם רק 56 סיביות בשימוש). המפתח יכול להיות פונקציה של קוד סודי או סיסמה קצרה. להבדיל מצופן אסימטרי ההנחה היא שהשולח והמקבל מחזיקים במפתח זהה, שאותו העבירו מראש אחד לשני באופן מאובטח.

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

11

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

כל מערכות ההוכחה האינטראקטיביות נדרשות לקיים שתי תכונות בסיסיות:

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

12

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

13

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

14

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

15

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