תורת האינפורמציה – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־04:30, 13 בדצמבר 2019

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

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

היסטוריה

אבי תורת האינפורמציה הוא המדען האמריקאי קלוד אלווד שאנון. ב-1948 פרסם שאנון את המאמר המכונן "A Mathematical Theory of Communication"^[1], אשר יצר לראשונה את הבסיס המתמטי עבור מערכות תקשורת. במאמר זה הגדיר שנון את הסיבית כיחידת מידע ואת האנטרופיה של מקור מידע, שניתן לתארה ככמות הביטים המינימלית הנדרשת כדי לקודד מסר שיוצר מקור המידע, וכן סיפק הגדרה מתמטית כללית של ערוץ תקשורת כקשר סטטיסטי בין הודעות כאשר הן נשלחות מהמקור לאותן הודעות כאשר הן מגיעות אל היעד. שאנון הראה לראשונה כי בעזרת פעולות קידוד מתאימות על ההודעות, ניתן להגיע לתקשורת אמינה (קצב שגיאות קטן כרצוננו), כל עוד קצב העברת המידע (הנמדד בסיביות לשנייה) קטן מהאינפורמציה ההדדית בין המקור והיעד שאותה משרה הערוץ, גודל המוגדר כקיבולת הערוץ (Channel capacity). לעומת זאת, העברת מידע בקצב גבוה מקיבולת הערוץ אינה אפשרית - קצב השגיאות יהיה גבוה עד כדי אובדן קשר סטטיסטי בין ההודעות הנשלחות והמתקבלות. תוצאה זו הייתה מפתיעה ולא שוערה לפני כן, אך היא הוכחה בפועל במערכות תקשורת רבות מספור בעקבות עבודתו של שאנון.

מאמרו של שאנון היה לאחד המאמרים המשפיעים ביותר על המדע במאה ה-20, ונכון ל-2014 הוא מצוטט מעל 60 אלף פעמים במאמרים אקדמאים שונים^[2]. בעקבותיו פותחו שיטות לחישוב קיבול של ערוצי תקשורת תאורטיים ומעשיים שונים, וחסמים על קצבי שגיאות בשיטות קידוד ופענוח שונות.

תיאור מתמטי של בסיס התיאוריה

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

אינפורמציה עצמית

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

כפועל יוצא מכך שאנון הגדיר את המידע המוכל בהודעה מסויימת $m$ כ- $I(m)=-\log _{2}p(m)$ כאשר $p(m)=Pr(M=m)$ . היא ההסתברות לבחירת הודעה $m$ מכל ההודעות האפשריות המגדירות את מרחב ההודעות $M$ . הגדרה זו משתמשת בתכונת הלוגריתם אשר מגדילה את ערכם של ערכים קטנים מאוד, ואילו משאיפה לאפס ערכים המתקרבים לאחד ובכך מעניקה משמעות גבוהה להודעות בעלות הסתברות נמוכה להתקבל. למידע המוכל בהודעה $m$ נהוג לקרוא בתורת האינפורמציה אינפורמציה עצמית (באנגלית:Self-information) של הודעה $m$ .

אנטרופיה

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

H(M)\;{\overset {\underset {\mathrm {def} }{}}{=}}\;\mathbb {E} (I(m))=\sum _{m\in M}p(m)I(m)=-\sum _{m\in M}p(m)\log _{2}p(m).

כאשר

\mathbb {E}

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

H(M)=-{\bigl [}p\log _{2}p+(1-p)\log _{2}(1-p){\bigr ]}

במקרה בו p שווה ל: 1/3 נקבל:

H(M)=-{\biggl [}{\frac {1}{3}}\log _{2}{\frac {1}{3}}+{\frac {2}{3}}\log _{2}{\frac {2}{3}}{\biggr ]}=0.91829...(bit)

ניתן להראות בטכניקות מתחום חשבון וריאציות כי כאשר ההסתברות לקבלת הודעה שווה בין כל ההודעות האנטרופיה היא מקסימלית ושווה ל- ${\mathsf {MAX}}(H)=\log _{2}|M|$ כאשר $|M|$ מייצג את מספר האיברים הקיים במרחב $M$ , תכונה הנקראת עוצמתו של $M$ . ניתן לקבל אינטואיציה לתופעה זו באמצעות ההגדרה האיכותית של האנטרופיה. כאשר כל ההודעות מתקבלות בהסתברות שווה, אזי אין כל דרך להעדיף בחירת הודעה אחת על אחרת, ולכן יכולת הניבוי היא מינימלית, כלומר המרחב הוא הכי בלתי צפוי שיכל להיות. כמו כן בזכות כך שאנטרופיה המינימלית מתקבלת כאשר ההתפלגות אחידה, ניתן לראות באנטרופיה מדד לעד כמה ההתפלגות הנמדדת שונה מהתפלגות זו.

אנטרופיה משותפת

האנטרופיה המשותפת של שני משתנים מקריים $X,Y$ מוגדרת כאנטרופיה של ההתפלגות המשותפת של $X,Y$ :

H(X,Y)\;{\overset {\underset {\mathrm {def} }{}}{=}}\;\mathbb {E} _{p(x,y)}[-\log _{2}p(X,Y)]=-\sum _{\{x\}}\sum _{\{y\}}p(x,y)\log p(x,y)

כאשר המשתנים הם בלתי תלויים האנטרופיה המשותפת היא פשוט סכום האנטרופיות של שניהם.

אנטרופיה מותנית

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

$H(Y|X)\;{\overset {\underset {\mathrm {def} }{}}{=}}\;\sum _{\{x\}}p(x)H(Y|X=x)=$

$=-\sum _{\{x\}}p(x)\sum _{\{y\}}p(y|x)\log p(y|x)$

$=-\sum _{\{x\}}\sum _{\{y\}}p(x,y)\log p(y|x)$

$=-{\boldsymbol {E}}_{p(x,y)}[\log p(Y|X)]$

ומכאן ניתן באמצעות כמה הצבות אלגבריות פשוטות לגזור את כלל השרשרת לאנטרופיה:

$H(X,Y)=H(X|Y)+H(Y)$

ובהכללה ל-i משתים בלתי תלויים:

$H(X_{1},X_{2},...,X_{n})=\sum _{i=1}^{n}H(X_{i}|X_{i-1},...,X_{1})$

ומכאן שכאשר המשתנים הם בלתי תלויים:

$H(X_{1},X_{2},...,X_{n})=\sum _{i=1}^{n}H(X_{i})$

אינפורמציה משותפת

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

$I(X;Y)=\sum _{\{x\}}\sum _{\{y\}}p(y)p(x|y)\log _{2}{\frac {p(x|y)}{p(x)}}=\sum _{\{x\}}\sum _{\{y\}}p(x,y)\log _{2}{\frac {p(x,y)}{p(x)p(y)}}$

זהות חשובה בתחום היא ש:

$I(X;Y)=H(X)-H(X|Y)$

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

$I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y)$

יישומים

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

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

ראו גם

לקריאה נוספת

Mcdonnell, M. D., Ikeda, S., & Manton, J. H. (2011). An introductory review of information theory in the context of computational neuroscience. Biological Cybernetics, 105(1), 55-70.
David J.C. MacKay, Information Theory, Inference, and Learning Algorithms. Cambridge University Press 2003.

קישורים חיצוניים

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

הערות שוליים

^ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
^ על פי Google Scholar
^ Denning, P. J., & Bell, T. (2012). The Information Paradox. American Scientist, 100(6), 470-477.

[1] C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948

[2] על פי Google Scholar

[פרדוקס-3] Denning, P. J., & Bell, T. (2012). The Information Paradox. American Scientist, 100(6), 470-477.

[1]

[2]

[3]

@@ שורה 17: / שורה 17: @@
 === אנטרופיה ===
-כאשר באים לבחון מאפיינים של מרחבי הודעות, דהיינו הקבוצה המגדירה את כל ההודעות היכולות להיבחר, יש צורך להגדיר מדדים המתארים תכונות כוללות של המרחב. אחת מהתכונות הללו היא רמת אי הסדר של בחירת ההודעות. כלומר המידה בה מרחב הודעות הוא בלתי צפוי בהקשר של בחירת הודעה ספציפית ממנו. ככל שקשה יותר לנבא איזה הודעה תבחר מן המרחב, נאמר כי האנטרופיה של המרחב גדולה יותר. למידה זו נהוג לקרוא האנטרופיה של מרחב הודעות בדיד <math>M</math>. מבחינה כמותית האנטרופיה של מרחב הודעות  <math>M</math> מוגדרת כממוצע האינפורמציה העצמית של כל ההודעות <math>m</math> השיכות למרחב. בכתיב מתמטי נאמר: <math display="block">H(M)\;\overset{\underset{\mathrm{def}}{}}{=}\;\mathbb{E}(I(m))=\sum_{m\in M}p(m)I(m)= -\sum_{m\in M}p(m)\log_2 p(m).</math>כאשר <math>\mathbb{E}</math> המייצג את תוחלת המרחב. ניתן להראות בטכניקות מתחום תורת הוואריאציות כי כאשר ההסתברות לקבלת הודעה שווה בין כל ההודעות האנטרופיה היא מקסימלית ושווה ל-<math>\mathsf{MAX} (H)= \log_2|M|</math> כאשר <math>|M|</math> מייצג את מספר האיברים הקיים במרחב <math>M</math>, תכונה הנקראת עוצמתו של <math>M</math>. ניתן לקבל אינטואיציה לתופעה  זו באמצעות ההגדרה האיכותית של האנטרופיה. כאשר כל ההודעות מתקבלות בהסתברות שווה, אזי אין כל דרך להעדיף בחירת הודעה אחת על אחרת, ולכן יכולת הניבוי היא מינימלית, כלומר המרחב הוא הכי בלתי צפוי שיכל להיות.
+כאשר באים לבחון מאפיינים של מרחבי הודעות, דהיינו הקבוצה המגדירה את כל ההודעות היכולות להיבחר, יש צורך להגדיר מדדים המתארים תכונות כוללות של המרחב. אחת מהתכונות הללו היא רמת אי הסדר של בחירת ההודעות. כלומר המידה בה מרחב הודעות הוא בלתי צפוי בהקשר של בחירת הודעה ספציפית ממנו. ככל שקשה יותר לנבא איזה הודעה תבחר מן המרחב, נאמר כי האנטרופיה של המרחב גדולה יותר. למידה זו נהוג לקרוא האנטרופיה של מרחב הודעות בדיד <math>M</math>. מבחינה כמותית האנטרופיה של מרחב הודעות  <math>M</math> מוגדרת כממוצע האינפורמציה העצמית של כל ההודעות <math>m</math> השיכות למרחב. בכתיב מתמטי נאמר: <math display="block">H(M)\;\overset{\underset{\mathrm{def}}{}}{=}\;\mathbb{E}(I(m))=\sum_{m\in M}p(m)I(m)= -\sum_{m\in M}p(m)\log_2 p(m).</math>כאשר <math>\mathbb{E}</math> המייצג את תוחלת המרחב. לדוגמה כאשר מרחב ההודעות מכיל שתי הודעות אחד בהסתברות P ואפס אחרת. נחשב את האנטרופיה לפי הגדרה:
+<math display="block">H(M)= -\bigl[p\log_2 p+(1-p)\log_2(1-p)\bigr]</math>במקרה בו p שווה ל: 1/3 נקבל:<math display="block">H(M)= -\biggl[\frac{1}{3}\log_2 \frac{1}{3}+\frac{2}{3}\log_2\frac{2}{3}\biggr]=0.91829...(bit)</math>
+ניתן להראות בטכניקות מתחום [[חשבון וריאציות]] כי כאשר ההסתברות לקבלת הודעה שווה בין כל ההודעות האנטרופיה היא מקסימלית ושווה ל-<math>\mathsf{MAX} (H)= \log_2|M|</math> כאשר <math>|M|</math> מייצג את מספר האיברים הקיים במרחב <math>M</math>, תכונה הנקראת [[עוצמה (מתמטיקה)|עוצמתו]] של <math>M</math>. ניתן לקבל אינטואיציה לתופעה  זו באמצעות ההגדרה האיכותית של האנטרופיה. כאשר כל ההודעות מתקבלות בהסתברות שווה, אזי אין כל דרך להעדיף בחירת הודעה אחת על אחרת, ולכן יכולת הניבוי היא מינימלית, כלומר המרחב הוא הכי בלתי צפוי שיכל להיות. כמו כן בזכות כך שאנטרופיה המינימלית מתקבלת כאשר ההתפלגות אחידה, ניתן לראות באנטרופיה מדד לעד כמה ההתפלגות הנמדדת שונה מהתפלגות זו.
 ==== אנטרופיה משותפת ====
 האנטרופיה המשותפת של שני משתנים מקריים<math>X,Y</math> מוגדרת כאנטרופיה של ההתפלגות המשותפת של <math>X,Y</math>:
-<math display="block">H(X,Y)\; \overset{\underset{\mathrm{def}}{}}{=}\;\mathbb E_{X,Y} [-\log_2 p(x,y)]=
+<math display="block">H(X,Y)\; \overset{\underset{\mathrm{def}}{}}{=}\;\mathbb E_{p(x,y)} [-\log_2 p(X,Y)]=
--\sum_{x,y}p(x,y)\log p (x,y)</math>כאשר המשתנים הם בלתי תלויים האנטרופיה המשותפת היא פשוט סכום האנטרופיות של שניהם.
+-\sum_{\{x\}}\sum_{\{y\}}p(x,y)\log p (x,y)</math>כאשר המשתנים הם בלתי תלויים האנטרופיה המשותפת היא פשוט סכום האנטרופיות של שניהם.
 ==== אנטרופיה מותנית ====
 אנטרופיה מותנית היא האנטרופיה שנגררת בעקבות ידיעה של אחד משני משתנים בעלי התפלגות משותפת. כאשר ידוע ערך ספציפי של Y שהוא קבוע ועליו מחשבים את האנטרופי של X אז ערכה מוגדר על ידי:
+<math>
-<math display="inline">H(X|y)\; \overset{\underset{\mathrm{def}}{}}{=}\;\mathbb E_{X|Y} [-\log_2 p(x|y)]=
+H(Y|X)\;\overset{\underset{\mathrm{def}}{}}{=}\;\sum_{\{x\}}p(x)H(Y|X=x)=
--\sum_{x \in X}p(x|y)\log p (x|y)</math> כאשר <math display="inline"> p(x|y)=\frac{p(x,y)}{p(y)}</math>.
+</math>
+<math>
+=
+-\sum_{\{x\}}p(x)\sum_{\{y\}}p(y|x)\log p(y|x)
+</math>
+<math>
+=
+-\sum_{\{x\}}\sum_{\{y\}}p(x,y)\log p (y|x)
+</math>
+<math>
+=-\boldsymbol E_{p(x,y)}[\log p(Y|X)]
+</math>
+ומכאן ניתן באמצעות כמה הצבות אלגבריות פשוטות לגזור את כלל השרשרת לאנטרופיה:
+<math>H(X,Y)=H(X|Y)+H(Y)</math>
+ובהכללה ל-i משתים בלתי תלויים:
-אולם באופן כללי כאשר ידוע המשתנה המקרה Y (לא רק ערך פרטי ספציפי שלו), ערך האנטרופיה המותנית ניתנת לחישוב על ידי שימוש בנוסחה לעיל. ערכה של האנטרופיה המשותפת, אשר נקראת בתנאי שכזה גם דו המשמעות של X על Y, נתונה על ידי:
+<math>H(X_1,X_2,...,X_n)=\sum^n_{i=1} H(X_i|X_{i-1},...,X_1)</math>
-<math>H(X|Y)=\mathbb{E}_Y( H(X|y))=-\sum_{y \in Y}p(y)\sum_{x \in X}p(x|y)\log p (x|y)=\sum_{x,y}p(x,y)
-\log_2\frac{p(y)}{p(x,y)}</math>
+ומכאן שכאשר המשתנים הם בלתי תלויים:
-ומכאן ניתן לגזור תכונה בסיסית של אנטרופיה מותנית:
-<math>H(X|Y)=H(X,Y)-H(Y)</math>
+<math>H(X_1,X_2,...,X_n)=\sum^n_{i=1} H(X_i)</math>
+=== אינפורמציה משותפת ===
-=== מידע משותף (העברת מידע) ===
-אחד הכלים האנליטים החשובים ביותר בתורת המידע היא בדיקה כמות של עד כמה אפשר להסיק מידע מסויים ממשתנה מקרי אחד על משתנה מקרי אחר. האינפורמציה המועברת ל- X מ- Y נתונה על ידי :
+אחד הכלים האנליטים החשובים ביותר בתורת המידע היא בדיקה כמות של עד כמה אפשר להסיק מידע מסויים ממשתנה מקרי אחד על משתנה מקרי אחר. האינפורמציה המשותפת מבטאת את הקטנת אי הודאות של משתנה מקרי X בזכות ידעתו של Y. מבחינה כמותית האינפורמציה המשותפת מתוארת על ידי המשוואה הבאה:
-<math>I(X;Y)=\sum_{x,y}p(y)p(x|y)\log_2\frac{p(x|y)}{p(x)} =\sum_{x,y}p(x,y)
+<math>I(X;Y)=\sum_{\{x\}}\sum_{\{y\}}p(y)p(x|y)\log_2\frac{p(x|y)}{p(x)} =\sum_{\{x\}}\sum_{\{y\}}p(x,y)
 \log_2\frac{p(x,y)}{p(x)p(y)}</math>
-תכונה בסיסית של העברת מידע זו היא ש:
+זהות חשובה בתחום היא ש:
 <math>I(X;Y)=H(X)-H(X|Y)</math>
-כמו כן העברת המידע היא סימטרית ולכן מתקיים הביטוי הבא:
+תכונה נוספת היא קיום סימטריה בין המדתנים ולכן מתקיים גם: מתקיים הביטוי הבא:
 <math>I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y)</math>

מכניקה סטטיסטית
תאוריה	עקרון גידול האנטרופיה • ergodic theory
תרמודינמיקה סטטיסטית	צברים • פונקציית חלוקה • משוואות מצב • פוטנציאלים תרמודינמיים: (U • H • F •‏ G) • קשרי מקסוול
מודל סטטיסטי	Ferromagnetism models (איזינג • פוטס • הייזנברג • חלחול ^EN) • חלקיקים בעלי שדה כוחות (כוחות דלדול ^EN • פוטנציאל לנארד-ג'ונס)
גישות מתמטיות	משוואת בולצמן • משפט־H • משוואת ולסוב • מדרג BBGKY • תהליך סטוכסטי • תורת שדה ממוצע ותורת השדות הקונפורמית
תופעות קריטיות	מעבר פאזה • אקספוננט קריטי (מרחק קורלציה • size scaling)
אנטרופיה	בולצמן • שאנון • צאליס • רניי • פון נוימן
יישומים	תורת השדות הסטטיסטית (חלקיקים יסודיים • נוזלי־על) • פיזיקה של חומר מעובה • מערכות מורכבות (כאוס • תורת האינפורמציה • אנטרופיה בתרמודינמיקה ובתורת האינפורמציה • מכונת בולצמן)

תחומים במדעי המחשב
יסודות מתמטים	לוגיקה מתמטית • תורת הקבוצות • תורת המספרים • תורת הגרפים • תורת הטיפוסים • תורת הקטגוריות • אנליזה נומרית • תורת האינפורמציה
תורת החישוביות	תורת האוטומטים • תורת הרקורסיה • תורת הסיבוכיות • מחשוב קוונטי
אלגוריתמים ומבנה נתונים	אנליזה של אלגוריתמים • גאומטריה חישובית
שפות תכנות ומהדרים	מפרש • פרדיגמת תכנות (תכנות פרוצדורלי • תכנות מונחה עצמים • תכנות פונקציונלי • תכנות לוגי)
חישוב מבוזר ועיבוד מקבילי	עיבוד מקבילי • מחשוב סריגי • בקרת מקביליות
הנדסת תוכנה	ניתוח מערכות מידע • עיצוב תוכנה • תכנות מחשבים • שיטות פורמליות • בדיקות תוכנה • מתודולוגיית פיתוח תוכנה
תקשורת	ניתוב • טופולוגיית רשת • קריפטוגרפיה
מסד נתונים	מסד נתונים יחסי • SQL • תנועה • אינדקסים • כריית מידע • CAP theorem
בינה מלאכותית	חשיבה אוטומטית • בלשנות חישובית • ראייה ממוחשבת • עיבוד שפה טבעית • בינה חישובית • מערכת מומחה • למידה חישובית • רובוטיקה
גרפיקה	הדמיה ממוחשבת • הנפשה ממוחשבת • עיבוד תמונה
שפות פורמליות	שפה רגולרית • שפה חסרת הקשר • שפה תלוית הקשר • ההיררכיה של חומסקי
שימושים במדע	ביואינפורמטיקה • מדעים קוגניטיביים • כימיה חישובית • פיזיקה חישובית • אנליזה נומרית

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: תורת האינפורמציה
תמונות ומדיה בוויקישיתוף: תורת האינפורמציה