HUJI CS Theory Page
algorithms, coding theory, combinatorics, complexity, cryptography, distributed computing, game theory, learning theory, logic, optimization, quantum computing, randomness and computation, specification, verification
התחום "תיאוריה של מדעי המחשב” עוסק בשאלה: אלו בעיות חישוב ניתנות לביצוע בטבע? בהקשר זה נחקרים כיוונים רבים, החל ממציאת אלגוריתמים לפתרון בעיות ספציפיות, הוכחות שחישובים מסוימים בלתי ניתנים לביצוע בזמן סביר, פרוטוקולים להצפנה והגנה מפני מאזינים פוטנציאליים, שאלות הקשורות לביזור חישובים בין משתתפים רבים, ועוד ועוד. המחקר מתבצע בעזרת כלים של פורמליזם מתמטי, כאשר המוטיבציה העיקרית היא הבנת בעיות מהותיות הקשורות לעיבוד אינפורמציה במודלי חישוב שונים.
לדוגמא, מסתבר שיש משימות חישוביות רבות הנראות טבעיות למדי, (למשל מציאת הדרך הקצרה ביותר לסוכן נוסע לעבור בכל הערים במסלולו) שאין אפשרות לפתור אותן בעזרת מחשב בכל זמן סביר. הסיבה לאי היכולת הזו היא מכשול עקרוני, שלא יפתר עם התפתחויות הטכנולוגיה - בכל טכנולוגיה אפשרית, הבעיה הזו פשוט קשה מדי. למכשולים כאלו יש גם צד חיובי: משימות קשות לחישוב הן הבסיס לתורת ההצפנה, אשר מאפשרת למסחר העולמי להתבצע בצורה מאובטחת ברשת האינטרנט.
שאלה נוספת הנחקרת בתיאוריה של מדעי המחשב נוגעת לקשר בין היכולת לבצע חישובים ובין חוקי הפיסיקה. לדוגמה, האם מחשבים המבוססים על עקרונות תורת הקוונטים יכולים להיות חזקים באופן מהותי מאלה המבוססים על הפיסיקה הקלאסית? ומה עם תופעות ביולוגיות כפעולות חישוב? על שאלה זו ניתן להסתכל גם מזווית אחרת: ניתן לחשוב על תופעות רבות בטבע כעל תהליך חישובי. האם ניתן להסביר תופעות בפיסיקה, ביולוגיה או כלכלה בעזרת תובנות שמקורן בניתוח תהליכי חישוב?
שאלות רבות בתיאוריה של מדעי המחשב קשורות לתחומים מגוונים במתמטיקה, בין השאר לקומבינטוריקה, אלגברה, גיאומטריה, טופולוגיה, תורת החבורות, ועוד. בעוד שהידע הקיים בתחומים אלו יכול להיות שימושי לפתרון שאלות הקשורות לחישוב, התיאוריה של מדעי המחשב גם מעלה שאלות רבות בתחומים אלו שהתשובות להן עדיין אינן ידועות. יתר על כן, במקרים רבים רעיונות אשר צצו תוך כדי מחקר במדעי המחשב התבררו כשימושיים במתמטיקה, ואף הובילו לפתרון בעיות מתמטיות שהיו פתוחות זמן רב.
קבוצת התיאוריה עוסקת בחקר שאלות הקשורות לכל מגוון הנושאים שהוזכרו.
מהי תיאוריה? -
