סמינר קיץ למורים מובילים "חזית המחקר במדעי המחשב"

תמונות מהסמינר

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

תקצירי ההרצאות מופיעים בהמשך

סדר יום

 

יום ב' 23 ביוני 2003

 

פתיחה וברכות

 

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

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

           הסרט מההרצאה ניתן לצפייה כאן  (מומלץ לצפייה רק בפס רחב. מדובר על קובץ גדול מאד 74M)

 

הרצאה: ד"ר שולי וינטנר, אונ' חיפה – "בלשנות ממוחשבת – הרצאת מבוא"

           השקפים מההרצאה (קובץ PDF)

 

הרצאה: ד"ר שאול מרקוביץ, טכניון – " כיצד משחק המחשב שחמט" (בינה מלאכותית)

 

סדנה בהנחיית ד"ר שאול מרקוביץ: "בניית תוכניות משחקות כפרויקט תכנות לתלמידי תיכון"

 

הרצאה: מר צבי ינאי – "תנאים לחדשנות מחשבתית"

 

שיחת מפמ"ר

 

 

יום ג' 24 ביוני 2003

 

הרצאה: פרופ' נפתלי תשבי, אונ' עברית ירושלים – "אתגרים חישוביים בביולוגיה מודרנית"

 

הרצאה: ד"ר דפנה שינוולד, יב"מ – "איך מספרים סיפור בקיצור" (דחיסת מידע)

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

 

הרצאה: ד"ר אילן נוימן, אונ' חיפה – "מבוא לקריפטוגרפיה מודרנית"

 

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

           השקפים מהעבודה בקבוצות (קובץ word)

           רשימת מקורות מומלצים לצפייה , מקור נוסף

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

 

שיחת סיכום

תקצירים:

אחד במחיר של שניים - גישה אחידה לקירוב בעיות אופטימיזציה (אלגוריתמים מקורבים)

פרופ'ח ראובן בר-יהודה, הפקולטה למדעי המחשב, הטכניון

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

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

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

מאמרים הקשורים להרצאה זו ניתן למצוא באתר האינטרנט http://www.cs.technion.ac.il/~reuven  

בלשנות ממוחשבת — הרצאת מבוא

ד"ר שולי וינטנר, החוג למדעי המחשב, אוניברסיטת חיפה

בלשנות חישובית היא תחום מחקר, המקשר בין בלשנות ובין מדעי המחשב.

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

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

כיצד משחק המחשב שחמט (בינה מלאכותית — הרצאה)

ד"ר שאול מרקוביץ, הפקולטה למדעי המחשב, הטכניון

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

תנאים לחדשנות מחשבתית (הרצאה מיוחדת)

מר צבי ינאי

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

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

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

אתגרים חישוביים בביולוגיה המודרנית

פרופ' נפתלי תשבי, בית הספר למדעי המחשב, האוניברסיטה העברית

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

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

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

איך מספרים סיפור בקיצור (דחיסת מידע)

ד"ר דפנה שינוולד, מעבדות המחקר של יבמ בחיפה

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

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

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

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

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

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

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

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