ניתן להוכיח כי קוד האפמן מחזיר תמיד קידוד אופטימלי, מבין כל צפני התחיליות. באופן כללי יותר, קוד האפמן נותן אורך ממוצע מינימלי של צופן בהשוואה לכל צפני החד-פענח (Uniquely Decodable). יש להיזהר בשימוש במילה "אופטימלי", שכן קיימים קידודים יעילים יותר במצבים מסוימים. האופטימליות של קוד האפמן פירושה שהוא הקוד היעיל ביותר שבו מייצגים כל אות על ידי רצף קבוע של ביטים, כך שלכל אות בטקסט מותאם רצף שכזה.
הוכחת אופטימליות הקוד אינה מסובכת, ומתבססת על כך שבהינתן קוד אופטימלי כלשהו, ניתן לבנות ממנו קוד אופטימלי חדש על ידי כך שמעבירים את שתי האותיות בעלות מספר המופעים הנמוך ביותר למקום הנמוך ביותר בעץ הקוד. מכיוון שפעולה זו יכולה רק לשפר את עלות הקוד הכוללת, הקוד נותר אופטימלי. כך ניתן באינדוקציה לבנות קוד האפמן מתוך כל קוד אופטימלי ללא הגדלת העלות.
קובץ גרפי
מלחמות השושנים
מלחמות השושנים (באנגלית: Wars of the Roses שמשמעותו היא מלחמות הוורדים) הן מאבק בין שושלות בממלכת אנגליה בשנים 1455–1487, שהתנהל בין בית לנקסטר, שסמלו היה שושנה אדומה, לבין בית יורק, שסמלו היה שושנה לבנה.
כתוצאה מהמלחמה הושמדו רוב בתי האצולה הגדולים באנגליה, לשלטון עלה בית טיודור הריכוזי והחזק, והסתיימו מאות שנות סכסוכים בין המלך לבין האצילים באנגליה. את המלחמה היטיב לתאר ויליאם שייקספיר, במיוחד במחזות "הנרי השישי" ו"ריצ'רד השלישי", הנחשבים לשניים מהחשובים שבמחזותיו.
רקע היסטורי.
הדחת ריצ'רד השני והכתרת לנקסטר.
בשנת 1377 מת אדוארד השלישי, אחד מגדולי מלכי אנגליה, לאחר תקופת מלוכה ארוכה ויציבה. לכס השלטון עלה נכדו, ריצ'רד השני, שהיה דמות יוצאת דופן בהיסטוריה האנגלית. עריץ קטנוני, אך גם שליט המחובר אל העם, אשר עשוי היה לשמש כקולם של בני העם הפשוט אל מול המעמד האריסטוקרטי. שילוב זה הביא להסכמה כללית בקרב האצולה על הצורך בהחלפתו. בשנת 1399 מרד במלך בן דודו, הנרי בולינגברוק, דוכס לנקסטר, ובתמיכת בתי האצולה הגדולים הפך בולינגברוק למלך הנרי הרביעי. המלך ריצ'רד הועלם בטירה רחוקה, וכעבור חודשים מספר הוכרז על מותו הטבעי (ככל הנראה נמנע ממנו מזון עד שגווע ברעב, כדי שעל גווייתו לא ייראו סימני עינויים).
הנרי הרביעי היה אף הוא נכדו של המלך אדוארד השלישי, אך לאדוארד היו ילדים חוקיים רבים. ריצ'רד השני היה בן בנו הבכור של אדוארד השלישי, ולא היו לו בנים. בנו השני של אדוארד השלישי מת בינקותו, ולכן יורש העצר החוקי אחרי ריצ'רד היה ילד בן שמונה בשם אדמונד מורטימר , רוזן מרץ' ואלסטר, שהיה נינו של ליונל מאנטוורפן, דוכס קלרנס, בנו השלישי של אדוארד השלישי. הנרי הרביעי היה בנו של ג'ון מגונט, בנו הרביעי של אדוארד השלישי. דודו של מורטימר ניסה למרוד בהנרי הרביעי בשם אחיינו הילד, אך המרד כשל, ומורטימר עצמו ישב כמה שנים בכלא, אך שוחרר ובבגרותו היה לתומך בבית לנקסטר.
ריצ'רד השני היה אחרון המלכים האנגלים שלא היו עוררין על זכותם לכתר. הנרי הרביעי השתלט על השלטון בכוח, ובמשך כל ימי מלכותו ובמהלך מלכותם של יורשיו, ידוע היה על קיומם של יורשים בעלי זכות עדיפה לכס המלוכה, וזכותו של בית לנקסטר נשענה לא על המסורת והחוק, כי אם על כוח הזרוע.
הנרי החמישי ומלחמת מאה השנים.
הנרי הרביעי, ויותר מכך בנו, הנרי החמישי, היו מלכים רבי עוצמה שמלכו בחוכמה. הנרי החמישי היה מהמוכשרים שבמלכי אנגליה, שהביא לניצחון בקרב אז'נקור (1415), מהניצחונות הגדולים במלחמת מאה השנים. קרב זה ביסס את אחיזתה של אנגליה בנחלות צרפתיות ואת שליטתה בצרפת, ובכך לראשונה הפכה אנגליה לאימפריה ולגורם משמעותי בזירה המדינית האירופית. הנרי החמישי נישא לקתרין, מלכת צרפת, והשניים הולידו ילד, הנרי השישי.
בהיותו בשיא כוחו, שליט בלתי מעורער על אנגליה וצרפת, לקה הנרי החמישי במחלה זיהומית קשה, ומת בשנת 1422. לכס השלטון עלה בנו, שעדיין לא מלאה לו שנה.
עם מותו של הנרי החמישי חל שינוי במצבה של אנגליה. השלטון הוחזק בידי שורה של עוצרים, שעיסוקם העיקרי היה תככים זה כנגד זה. באותה עת עלתה על בימת ההיסטוריה ז'אן ד'ארק, שהצליחה לאחד את העם הצרפתי ולהמרידו נגד הכובש האנגלי. כתוצאה, איבדה אנגליה תוך שנים ספורות את מרבית נחלותיה בצרפת, שהושגו במאמץ, בעמל ובדמם של הקשתים האנגלים בקרבות קראסי, פואטייה ואז'ינקור. בשנת 1453 נותרה לאנגליה רק נחלה אחת קטנה מכל כיבושיו של הנרי החמישי, העיר קאלה.
הנרי השישי מול ריצ'רד דוכס יורק.
הנרי השישי, שבתקופתו איבדה אנגליה את נחלותיה ביבשת, היה האדם הפחות מתאים למלוכה מבין כל האצולה האנגלית בתקופה סוערת זו. התקופה שיוועה לאדם שיוכל לפשר בין האצילים היריבים מבית, ולנהל מלחמה מוצלחת כנגד הצרפתים מבחוץ. הנרי, שסבל ממחלת נפש שגרמה לו לתקופות ארוכות של אובדן יכולתו המנטלית ושל חוסר התמצאות, לא ניחן מלכתחילה בכישרון לשלוט או לנהל מלחמה. במשך כל תקופת שלטונו הארוכה (באופן לא רציף בין 1422 ל-1461 ומ-1470 עד 1471) היה הנרי בובה בידי הסובבים אותו. בילדותו - בידי האצילים ששימשו לו כעוצרים, ולאחר מכן - בידי כל מי שיכול היה להשפיע עליו, ובמיוחד אשתו, מרגרט מאנז'ו.
בנסיבות אלו התרכזו המתנגדים לכתר סביב ריצ'רד פלנטג'נט, דוכס יורק. ריצ'רד היה בן אחותו של אדוארד מורטימר, וכן היה בן בנו של אדמונד מלאנגלי, דוכס יורק, בנו החמישי של אדוארד השלישי. באישיותו היה ריצ'רד ההפך הגמור מהנרי השישי: איש פעולה ומעש, חזק וכריזמטי. ריצ'רד שימש במספר משרות רמות-דרג, לרבות הממונה על נחלות המלך באירלנד, ובכולן נחל הצלחה. כך עמדה אנגליה אל מול הדילמה שבין זכותו של מלך חולה נפש וחסר אונים, אשר זכותו אינה מבוססת על החוק והמסורת, אלא על תפיסת השלטון בכוח על ידי סבו, ומולו בעל הזכות החוקית למלוך, שמבחינת תכונותיו אין מתאים ממנו למלוכה.
כך התגבשה החזית הראשונית במלחמת השושנים - אנשי המלך הנרי נקראו "בית לנקסטר", שאימצו להם כסמל את השושנה האדומה, וכנגדם אנשי הדוכס ריצ'רד שנקראו "בית יורק", אשר אימצו להם כסמל את השושנה הלבנה. אין קשר בין האזורים הגאוגרפיים "לנקסטר" ו"יורק" ובין השושלות היריבות. בית יורק הסתמכו בעיקר על תומכים בדרום אנגליה ומערבה, בעוד שבית לנקסטר היה חזק בצפון אנגליה ובמזרחה.
בשלב הראשוני נראה היה כי השושנה הלבנה של בית יורק הקדימה לפרוח. בשנת 1453 סבל הנרי מהתקף חמור מאוד של מחלת הרוח שלו, ואיבד קשר עם המציאות. ריצ'רד מונה כעוצר, ונראה היה כי דרכו אל המלוכה סלולה. אך הייתה זו אשליה, שכן לא חלפו ימים רבים והמלכה מרגרט ילדה בן זכר למלך, וניתן לו השם אדוארד. בחג המולד בשנת 1454 חזרה למלך לפתע שפיותו, לאחר חמישה עשר חודשים. מבחינה חוקית לא היה עוד תוקף לאפוטרופסותו של ריצ'רד, והשלטון חזר רשמית לידי המלך הנרי מבית לנקסטר, ומעשית לידי אשתו מרגרט, שעתידה הייתה לעשות הכל כדי שבנה אדוארד יהיה למלך אחריו. התנאים היו בשלים לעימות מזוין.
תחילת המלחמה.
קרב סנט אולבנס.
עם החלמתו של הנרי השישי, לא עשה ריצ'רד כל מאמץ להמשיך בשלטונו כעוצר. עם זאת, כשהתברר כי מרגרט מאנז'ו, המלכה, מתכוונת לשמור בידיה את השלטון ולסלק את המתנגדים, החל ריצ'רד חושש לחייו. מרגרט נטלה מריצ'רד את אחרון תפקידיו - מושל העיר קאלה, ולא הזמינה אותו עוד לישיבות מועצת המלך. אך משהוזמן פתאום לישיבה בעיר לסטר, חשד ריצ'רד כי המטרה היא לאסרו, לשפוט אותו שם ולהורגו. בפעולת מנע, ב-22 במאי 1455, תקף בראש כוח של כשלושת אלפים איש את צבא תומכיו של המלך בדרכם ללסטר, בעיר סנט אולבנס, והביס אותו. היה זה העימות המזוין הראשון במלחמות השושנים.
מטרתו הרשמית של ריצ'רד לא הייתה הדחת המלך הנרי, אלא להסיר מעליו את "יועציו הרעים". הקרב היה קצר ועז; בסך הכול נהרגו בקרב סנט אולבנס פחות מ-200 איש. עם זאת, כפי שאופייני למלחמות השושנים, היו רוב ההרוגים אצילים, ורבים מהם היו מתומכיו העיקריים של המלך. מלחמות השושנים היו, ככלל, עניין פנימי בין האצילים. פשוטי העם אמנם השתתפו בלחימה, אך לא עשו זאת באותה התלהבות והקרבה אישית כפי שלחמו האצילים, שמעמדם וזכויותיהם היו תלויים בהישגים. כתוצאה מכך נלחמו אצילים אלו זה בזה עד מוות.
לאחר קרב סנט אולבנס היה השלטון בידי ריצ'רד, ורבים מתומכי המלך הנרי היו בין ההרוגים. ריצ'רד נהג במתינות בניצחונו: הוא לא פגע במלך, באשתו או בבנו. מבחינה פורמלית נותר הנרי השישי על כס המלוכה, אך ריצ'רד שב וקיבל את תפקידו כאפוטרופוס על המלך. עם זאת הכריז על עצמו כיורש, תוך שהוא מדיח מתואר זה את הנסיך אדוארד, בנה של המלכה מרגרט. ייתכן שהייתה זו פשרה ראויה, אך הדבר לא היה מקובל על הלנקסטרים, שלא חדלו מלתכנן קשר במטרה להשיב לידם את רסן השלטון. עד 1460 שררה שביתת נשק שנראתה כזמנית, וכהעמדת פנים של ידידות ושלום. מתחת לפני השטח המשיכו שני הצדדים בצבירת תומכים ונשק, והמלכה מרגרט הכריזה על גיוס חובה, לראשונה בתולדות אנגליה.
קרב נורת'האמפטון.
לבסוף פרצה האש מן הגחלים הלוחשות מתחת לפני השטח: ריצ'רד דוכס יורק היה בשליחות באירלנד, כשכוח מתומכי יורק, בראשותו של ריצ'רד נוויל, הרוזן מווריק (שעתיד היה להפוך לדמות מפתח במלחמה וכונה "ממליך המלכים") התקיף את אנשי המלך בנורת'מפטון, וזאת לאחר מספר התנגשויות בין בית-יורק ובית-לנקסטר במהלך החודשים שקדמו לכך.
הרוזן מווריק היה אחד האנשים העשירים ורבי העוצמה שבאנגליה, אך לא השתייך למשפחת המלוכה. תמיכתו בדוכס מיורק הביאה לאנשי יורק מימון, ואת אחד המנהיגים הצבאיים והפוליטיים הגדולים בתקופתו.