מדעי המחשב הוא ענף מדעי העוסק בלימוד הבסיס התאורטי למידע ולחישוביות, והחלתם של אלה על מערכות מחשב.
למדעי המחשב מספר רב של ענפי-משנה; חלקם מדגישים את היבטי החישוביות של תוצאות פרטניות (לדוגמה, גרפיקה ממוחשבת), אחרים עוסקים בחקר התכונות של בעיות חישוביות כלליות (לדוגמה, סיבוכיות), וענפי-משנה אחרים מתמקדים בפתרון הבעיות הכרוכות ביישום מעשי של חישובים ואלגוריתמים. ענף משמעותי במדעי המחשב הוא חקר ויישום שפות פורמליות לפתרון בעיות חישוביות מסוימות (לדוגמה, באמצעות שפת תכנות).
שפת תכנות היא אוסף של חוקים תחביריים (Syntax) וסמנטיים (Semantic) שבאמצעותם ניתן להגדיר למחשב באופן מפורט את הפעולות שעליו לבצע במצבים שונים, על סוגי קלט שונים. המושג שפת מחשב (Computer Language), הוא מושג רחב מאשר שפת תכנות (Programming Language) ולכן השימוש בו נפוץ יותר.
שפת התכנות במהותה נועדה לגשר בין המחשב, ששפתו, הקרויה שפת מכונה, מורכבת מרצפי סיביות, לבין המתכנת שמעדיף לתקשר בצורה מילולית יותר, כמו גם לאפשר תקשורת טובה בין המתכנתים. השימוש בשפת תכנות לשם כתיבת תוכנית מחשב קרוי תכנות. על מנת להקל על המלאכה, שפת התכנות מציעה מבחר כלים המשמשים להפשטה, ארגון וביאור הקוד, כגון מבני בקרה (לולאות, תנאים, מתגים וכדומה), פרוצדורות, עצמים, וכו'.
עבודותיו בקריפטוגרפיה נוגעות בכל היבט של התחום. אחת הראשונות בהן הייתה אלגוריתם ההצפנה RSA, המהווה בסיס למרבית תוכנות ההצפנה הנהוגות היום. האלגוריתם פותח בשנת 1977, בעת ששמיר שהה במכון הטכנולוגי של מסצ'וסטס, והוא קרוי על־שם ראשי התיבות ממציאיו: ריבסט, שמיר ואדלמן.
תרומות אחרות של שמיר כוללות את מושג חלוקת הסוד, קריפטאנליזה דיפרנציאלית ורעיון השימוש בפונקציות אקראיות ליצירת שיטות חתימה יעילות.
מתרומותיו הידועות לסיבוכיות היא ההוכחה כי מחלקת הסיבוכיות IP, שמציינת את השפות שיש להן מערכת הוכחה אינטראקטיבית יעילה מבחינת המוודא, זהה למחלקה PSPACE שכוללת את השפות שניתנות להכרעה באמצעות שימוש בזיכרון שגודלו פולינומי.
נועם חומסקי הוא פרופסור לבלשנות במכון הטכנולוגי של מסצ'וסטס (MIT), הוגה דעות אנרכיסט, פעיל למען זכויות אדם ופרשן פוליטי המזוהה עם השמאל הרדיקלי.
בעבודתו האקדמית הוא מייסד אסכולת הבלשנות הגנרטיבית, והוגה היררכיית חומסקי, שהיא שיטת מיון של שפות פורמליות.
ההיררכיה שהוא הציע מחלקת דקדוקים פורמליים לקבוצות על פי כוח הבעה עולה. כלומר, כל קבוצה עוקבת יכולה ליצור מערך רחב יותר של שפות פורמליות מזו שקדמה לה. לטענתו של חומסקי, מודליזציה של הבטים מסוימים בשפה טבעית דורשת דקדוק פורמלי מורכב יותר (כפי שהוא נמדד בהיררכיית חומסקי) מאשר מודליזציה של שפות אחרות. לדוגמה, בזמן ששפה רגולרית חזקה מספיק לתאר מורפולוגיה אנגלית, היא אינה חזקה מספיק כדי לתאר תחביר אנגלי. בנוסף להיותה רלוונטית לבלשנות, היררכיית חומסקי נעשתה חשובה במדעי המחשב, ויש לה קשרים חשובים גם לתורת האוטומטים.
פונקציית גיבוב (Hash function) היא פונקציה שממירה קלט חופשי באורך משתנה לפלט באורך קבוע, בדרך כלל קצר בהרבה. לפונקציות אלו שימושים בבעיות אלגוריתמיות רבות, ובהן מיון וחיפוש בטקסטים ארוכים ובקריפטוגרפיה. בתמונה תיאור שלדי של פונקציית גיבוב.
גרף הינו אחד ממבני הנתונים השימושיים ביותר. בדוגמה לעיל, עץ פורש מינימלי, אשר מתאר את אוסף הקשתות בעל המשקל הנמוך ביותר, אשר מכסה את כלל צמתי הגרף.
מדעי המחשב, בהיותם מדע, מתבססים על יסודות מתמטיים רבים מתחום האלגברה, הקומבינטוריקה והלוגיקה.
מדעי המחשב מציעים מגוון של מבני נתונים מופשטים המהווים מודל מתמטי נוח עבור בעיות יום-יומיות. שימוש במודלים אלו מאפשר גיבוש, ניתוח ומיטובאלגוריתמים עבור בעיות אלו.
חישוביות הינה תחום תאוריה בסיסי במדעי המחשב אשר עוסק ביכולת החישוב של מחשב: מה ניתן ומה לא ניתן לחשב על ידי מחשב. הניתוח המדעי מבוסס על מודל מתמטי עבור מכונת חישוב אשר נקרא מכונת טיורינג.
סיבוכיות חישובית היא ענף של תחום החישוביות אשר מתמקד בפונקציות אשר ניתן לחשב במחשב, ועוסק ביעילות הביצוע של אותו חישוב: כמה מהר ניתן לעשותו, מה הזיכרון המינימלי הנדרש וכיוצא בזה.
אלגוריתם הוא דרך שיטתית (כלומר כזו שצעדיה מוגדרים היטב) לביצוע של משימה מסוימת במספר סופי של צעדים. מתכון להכנת עוגה הוא דוגמה לאלגוריתם, אך בדרך-כלל משמש מושג זה לפתרון בעיות במתמטיקה או במדעי המחשב. כל תוכנית מחשב היא אלגוריתם, או אוסף של אלגוריתמים.
בינה מלאכותית היא ענף של מדעי המחשב העוסק ביכולתם של מחשבים לפעול באופן המציג יכולות השמורות עד כה לבינה האנושית בלבד. מכיוון שמחשב יכול לבצע פעילויות מוגדרות במהירות רבה ביותר, לעיתים נוצרת התחושה שהוא מדמה פעולה אינטליגנטית, כגון יכולת משחק שחמט או ניהול שיחה.
בשנת 1950 הוגדר הכלי שבעזרתו ניתן לקבוע האם מכונה הגיעה לרף האינטליגנציה האנושית, במבחן הקרוי מבחן טיורינג:
"אם יינתן לאדם, היושב בחדר סגור, לנהל שיחה באמצעות ממשק מחשב (Console) עם ישות שנמצאת בחדר השני, כאשר אותה ישות תהיה או אדם או מכונה, והמשוחח לא יוכל לזהות האם מולו ניצב אדם או מכונה, או-אז המכונה תחשב לתבונית.
שימוש בגרפיקה ממוחשבת (ובפרט בגרפיקת תלת־ממד) לצורך יצירת אנימציה קרוי אנימציה ממוחשבת. לטכנולוגיה זו שימושים רבים בקולנוע, בטלוויזיה ובמשחקי מחשב.
היכולת של הגרפיקה הממוחשבת (ובפרט גרפיקת תלת־ממד) לייצר תמונות ריאליסטיות משמשת גם באדריכלות, רפואה ובתחומי תעשייה אחרים.
תחום אחר בגרפיקה הממוחשבת, עיבוד תמונה, משמש בעיקר לעיבוד תמונות שצולמו במצלמה. בעזרת שיטות אלה אפשר לתקן פגמים שנפלו בצילום, לשנות את תכונות התמונה כולה או חלקים ממנה, וכן ליצור אפקטים מיוחדים כגון מורפינג.
חישוב קוונטי הינו תחום במדעי המחשב בו מכונת החישוב פועלת על פי עקרונות הפיזיקה הקוונטית ומוגבלת אך ורק על ידי חוקים פיזיקליים אלו. להבדיל ממכונת החישוב ה"קלאסית" (מכונת טיורינג הפועלת לפי חוקי הפיזיקה הקלאסית), המחשב הקוונטי יודע לעבד ביטים-קוונטיים, קיוביטים, בעלי התכונה המוזרה שמצבם אינו בהכרח '0' או '1' אלא יכול להיות סופרפוזיציה שלהם. מודל חישובי זה מאפשר ביצוע אלגוריתמים קוונטיים בעלי מקביליות גבוהה, ויעילות טובה יותר מהאלגוריתם הקלאסי הרגיל.
כח החישוב של מחשב קוונטי אינו גדול יותר מאשר של מחשב רגיל, אך כאמור יעילותו גבוהה יותר. פעולות כמו מציאת גורם ראשוני של מספר גדול, או מציאת מפתח של צופן, ניתנות לביצוע במחשב קוונטי ביעילות פולינומית, לעומת היעילות האקספוננציאלית של מחשב קלאסי.
תורת הקודים היא תחום במתמטיקה ובמדעי המחשב שעוסק בהעברה יעילה של מידע דרך מערכת מציאותית שיוצרת שגיאות ברצף.
כאשר מעבירים מידע דרך מוליך טוב ככל שיהיה (גלי רדיו, קווי טלפון), נופלות טעויות במידע כתוצאה מרעשי רקע שנוצרים מסיבות טכניות בעיקר. שגיאה קטנה ככל שתהיה יכולה לעוות את המידע המתקבל ולהפוך אותו לחסר משמעות, או לבעל משמעות שונה מהרצוי. הבעיה קיימת מאז ומעולם גם בשפת הדיבור והכתיבה. ניתן לראות טעויות דפוס שנובעות מהחלפת אותיות כמעט בכל ספר שיוצא לשוק.
בעיה זו נעשתה חריפה במיוחד בתקשורת בין מחשבים, בה שינוי של ביט אחד במסר יכול להרוס את החישוב כולו.
בתורת הקודים מפותח מושג הקוד וכן גם כלים שמאפשרים הבחנה ותיקון שגיאות במידע המתקבל.
•
מערכת הוכחה אינטראקטיבית •
קוד המינג •
קוד ריד-סולומון •
קריפטוגרפיה 
