בתרגום ללשון תורת הגרפים, כל תא במבוך הוא צומת, וכל קשת במבוך מייצגת שני תאים שניתן לעבור ביניהם (כלומר, הם שכנים, ואין ביניהם קיר). אלגוריתם בסיסי ליצירת מבוך יכול להתבסס על מציאת עץ פורש בגרף שמייצג את יחסי השכנות של התאים. בצורה זו, יהיה קיים במבוך מסלול אחד ויחיד בין כל שתי נקודות (נהוג לכנות מבוך שכזה בשם לבירינת). לאחר מכן ניתן יהיה להוסיף קשתות בין צמתים שמייצגים תאים שכנים על מנת לקבל מספר מסלולים אפשריים בין חלק מתאי המבוך.
אלגוריתם חיפוש לעומק.
שיטה אחת לבניית מבוך היא הרצת חיפוש לעומק על הגרף המייצג את יחסי השכנות שבמבוך. בתחילת ריצת האלגוריתם מבנה הנתונים שעליו הוא פועל מכיל את הגרף, כאשר עבור כל תא נמצאת גם רשימת הקירות שיש בו. האלגוריתם פועל כדלהלן: ראשית, בוחרים את התא שישמש בתור היציאה מהמבוך, וממנו תתחיל בניית המבוך. לאחר מכן מבצעים בצורה רקורסיבית את הפעולות הבאות:
השיטה הרקורסיבית הזו עלולה להיות בעייתית לתכנות במבוכים גדולים, שכן כל רקורסיה מעמיסה על המחסנית. לכן ניתן לכלול את המידע הדרוש לחזרה בתוך המבוך עצמו: אפשר להוסיף לכל תא "חץ" שמצביע לעבר השכן שממנו הגענו אליו, ולכן כל החצים מצביעים לכיוון היציאה. בצורה זו גם ניתן להציג בצורה אוטומטית פתרון של המבוך מבלי שיהיה צורך להפעיל אלגוריתם מיוחד הפותר אותו.
גרסה אקראית של אלגוריתם קרוסקל.
האלגוריתם של קרוסקל מבוסס על בנייה הדרגתית של העץ הפורש באמצעות בחירת קשת אחת בכל פעם שתתווסף לעץ, כאשר הקשתות נבחרות על פי משקלן. ניתן לבצע דבר דומה אם מחלקים משקלות אקראיים לקשתות הגרף המייצג את יחסי השכנות במבוך. דרך אחרת היא להשתמש במבנה נתונים שמסוגל לבצע פעולות Union Find בצורה הבאה:
הקלט לבעיה יהיה המבוך, עם כל הקירות האפשריים בתוכו. בשלב הראשון של האלגוריתם תיווצר רשימה של כל הקירות במבוך, ותוגדר קבוצה עבור כל אחד מהתאים שבו. לאחר מכן עוברים על כל הקירות בצורה אקראית. עבור כל קיר, מבצעים את הפעולה הבאה:
אלגוריתם זה ניתן לביצוע בצורה יעילה מאוד, שכן קיימים מבני נתונים שבהם זמן הביצוע המשוערך של פעולות Union ו-Find הוא נמוך יחסית.
גרסה אקראית של האלגוריתם של פרים.
האלגוריתם של פרים מבוסס על בנייה של עץ שהולך וגדל עד אשר הוא מכסה את כל הגרף. משיטת בניה זו נובע אלגוריתם המזכיר את זה של חיפוש לעומק. ראשית בוחרים את התא שמשמש כיציאה, ומוסיפים את כל הקירות ששכנים אליו לרשימת עזר. כעת מבצעים את הפעולות הבאות כל עוד ישנם קירות ברשימה:
ההבדל בין אלגוריתם זה לבין אלגוריתם החיפוש לעומק הוא שחיפוש לעומק מסוגל לבחור בתור הקיר הבא שיסיר רק כאלו ששכנים לתא הנוכחי שבו הוא נמצא, והאלגוריתם של פרים בוחר קיר מכל אחד מהקירות שקיימים במבוך שבנה עד כה.
בניגוד לאלגוריתם של קרוסקל, אלגוריתם זה אינו זקוק למבנה נתונים של קבוצות, מכיוון שבכל זמן שהוא קיימות רק שתי קבוצות שמעניינות אותנו: זו של התאים ששייכים למבוך וזו של התאים שאינם שייכים אליו. את ההפרדה בין שתי הקבוצות ניתן לבצע באמצעות סימון פשוט בכל תא.
MPAIAC
MPAIAC (בספרדית: Movimiento por la Autodeterminación e Independencia del Archipiélago Canario - התנועה להגדרה עצמית ולעצמאות של הארכיפלג הקנרי) הוא ארגון שרואה כמטרתו את השגת הזכות להגדרה עצמית והפרדה של האיים הקנריים מממלכת ספרד.
הארגון הוקם ב-22 בנובמבר 1964 באלג'יריה על ידי הגולה הספרדי עו"ד אנטוניו קוביז'ו. בשנת 1975 התנועה החלה לשדר תעמולה ברדיו אלג'יראי. באותה שנה ובשנת 1976 נהרגו שני פעילים של התנועה בידי כוחות ביטחון. ב-1 בנובמבר 1976 הארגון הכריז על מאבק מזוין באמצעות זרועו הצבאית FAG. פעולתם הראשונה בוצעה באותו חודש, כשהתפוצץ מטען חבלה באיים הקנריים, לא היו נפגעים.
ב-1977 ה-FAG פוצצו מטען חבלה ראשון מחוץ לאיים הקנריים, במדריד, לא היו נפגעים. באותה שנה הם הטמינו פצצה בחנות פרחים בנמל התעופה גאנדו, כתוצאה מהפיצוץ נפצעו מספר אנשים. בעקבות הפיגוע ומפני חשש לפצצה נוספת בנמל התעופה הטיסות הוסטו לשדה התעופה לוס רודאוס בטנריפה, מה שגרם (יחד עם מזג האוויר הגרוע ושרשרת של טעויות אנוש) לאסון המטוסים בטנריפה. ב־1978 נהרג הסמל רפאל ולדנברוס, מהיחידה לניטרול מטעני חבלה, כשניסה לנטרל פצצה בטנריפה. זה היה המקרה היחיד שבו גרמה פעילות הארגון באופן ישיר לנפגעים בנפש.
ב-5 באוגוסט 1978 אנטוניו קוביז'ו יצא בחיים מניסיון התנקשות באלג'יר, אך נשאר נכה. ההתנקשות בוצעה ביוזמת משרד החוץ הספרדי וב-2003 קוביז'ו פוצה בסך 150,000 אירו.
בשנת 1979 הארגון ויתר על המאבק המזוין ומייסדו אנטוניו קוביז'ו גורש מהארגון בשל חילוקי דעות עם ההנהלה.
בשנות ה-80 וה-90 הארגון חדל מלהתקיים. ב-1985 קוביז'ו חזר מגלותו באלג'יריה והקים מפלגה בדלנית בשם "הקונגרס הלאומי של האיים הקנריים" (Congreso Nacional de Canarias). שיא כוחה של המפלגה היה ב-1987, כאשר זכתה במושב אחד במועצה של העיירה ארסיפה (Arrecife) באי לנסרוטה. בשנת 2003 חלק מפעיליו הוותיקים של MPAIAC הקימו אותו מחדש, אך הפעילות שלו היא כמעט אפסית ומסתכמת בעיקר בתעמולה באינטרנט. אנשי הקונגרס הלאומי של האיים הקנריים מתנערים מפעילות זו וטוענים שזו למעשה פעילות של סוכנויות הריגול הספרדיות.
ה-FAG (בספרדית Fuerzas Armadas Guanches - הכוחות המזוינים הגואנצ'ים) היו הזרוע הצבאית של הארגון הבדלני הקנארי MPAIAC בין השנים 1976 ו-1978. שמו של הארגון נגזר משמה של האוכלוסייה הקדומה של הארכיפלג הקנרי, הגואנצ'ים. עיקר פעילותו הייתה הטמנת מטעני חבלה באתרים אסטרטגיים באיים הקנריים ובמדריד. מטרת הפעילות הייתה להפעיל לחץ על הממשל הספרדי ולא לגרום לנפגעים.
חלום ליל קיץ
חלום ליל קיץ (באנגלית: A Midsummer Night's Dream, חלום ליל אמצע הקיץ) הוא מחזה, קומדיה רומנטית, מאת ויליאם שייקספיר שנכתב בשלהי המאה ה-16. במחזה, המתרחש באתונה וביער הסמוך לה, מסופרים שלושה סיפורים מקבילים, המשתלבים זה בזה: סיפורם של ארבעה צעירים הקשורים ביניהם בקשרי אהבה מורכבים, סיפורה של חבורת שחקנים חובבים וסיפורם של הפיות ושאר שוכני היער. עיקר המחזה מתרחש בליל קיץ אחד, ביער הסמוך לאתונה.
המחזה הוא אחד המחזות הפופולריים ביותר של שייקספיר, אף שסמיואל פיפס, בן המאה ה-17, כתב ביומנו: "זהו המחזה המגוחך והתפל ביותר שאי פעם ראיתי בחיי".
מבנה עלילה.
הרמיה וליסנדר הם זוג מאוהב, אך אגאוס, אביה של הרמיה, עומד על כך שהיא תינשא לאדם שהוא בחר: דמטריוס (המאוהב בהרמיה). אגאוס מגיע להיכלם של תסאוס, דוכס אתונה, והיפוליטה (מלכת האמזונות) אשתו לעתיד, יחד עם בתו, דמטריוס וליסנדר, על מנת שתסאוס ישפוט בנושא. תסאוס מציג בפני הרמיה שלוש אפשרויות - לשמוע בקול אביה ולהינשא לדמטריוס, להמרות את פיו - במקרה כזה היא תומת, או לעבור למנזר לחיות חיי נזירה.
לנוכח אפשרויות אלה, ליסנדר מציע להרמיה לברוח יחדיו אל דודתו שגרה בעיר אחרת ולהינשא שם. הרמיה מסכימה והם קובעים להיפגש בלילה ביער כדי לממש את הבריחה. הרמיה מספרת על הבריחה רק לחברתה הטובה, הלנה, המאוהבת בדמטריוס. הלנה יודעת שלא תוכל לגרום לדמטריוס להתאהב בה, אך רוצה שהוא "יכיר לה תודה" גם אם זה יכאב לה ודמטריוס לא ישהה אתה, ולכן היא מלשינה על ליסנדר והרמיה לדמטריוס. דמטריוס יוצא ליער בעקבות ליסנדר והרמיה, והלנה עוקבת אחריו. דמטריוס מנסה להיפטר מהלנה לכל אורך הדרך.
בינתיים, אוברון וטיטניה, מלך ומלכת הפיות, מסתכסכים. ברשותה של טיטניה ילד אסופי, שהיה בנה של נסיכה הודית (כוהנת לטיטאניה) שנפטרה. טיטניה הבטיחה לכוהנת לגדל את הילד. אוברון מבקש לקבל את הילד וטיטניה מסרבת. אוברון מחפש דרך להשפיל את טיטניה, ולגרום לה לתת לו את הילד. הוא שולח את פּאק, יצור שובב הסר למרותו, להביא פרח שהשיקוי המופק ממנו גורם להתאהבות. אוברון מטפטף צוף מפרח זה על עיניה של טיטניה, ופוקד על פּאק לגרום לטיטניה להתאהב במשהו טיפשי ככל האפשר. כמו כן, מבקש אוברון מפּאק להסדיר בדרך זו את יחסי האהבה בין דמטריוס והלנה, שאינם סימטריים.
בזמן זה שישה בעלי מלאכה מגיעים ליער כדי להעלות את "הקומדיה העצובה־מכל־הקומדיות על מותם האכזרי־מכל־מוות של פירמוס ותיסבי" בחתונתם של תסאוס והיפוליטה. פּאק הופך את אחד מבעלי המלאכה, "מחט" (על-פי דן אלמגור, וראו להלן תרגומים אחרים), לאיש בעל ראש של חמור, ויתר בעלי המלאכה נבהלים ובורחים. כאשר טיטניה פוקחת את עיניה היא מתאהבת ב"מחט" בעל ראש החמור. "מחט" מעיר על כך: "נדמה לי, גבירתי, שמבחינה הגיונית, יש לך סיבה קטנה מאוד להתאהב באחד כמוני. עם זאת, נכון, אהבה והיגיון הולכים מעט מאוד ביחד בימינו."
פאק מתבלבל בין דמטריוס וליסנדר, ומטפטף בטעות צוף על עיני ליסנדר הישן. הלנה, הרואה את ליסנדר ישן, חוששת שדמטריוס הרגו, ולכן מעירה אותו, ובהשפעת הצוף ליסנדר מתאהב בהלנה. אוברון, שרואה שדמטריוס עודנו כרוך אחר הרמיה, מטפטף צוף על עיני דמטריוס וכאשר הוא מתעורר גם הוא מתאהב בהלנה. כך שוב אין סימטריה ביחסים - שני הגברים אוהבים אשה אחת, והאחרת זנוחה. הלנה אינה מאמינה לחיזוריהם של הגברים וסבורה שהם לועגים לה, שהרי לא אהבו אותה קודם לכן. הרמיה כועסת על שהלנה גזלה ממנה את אהובה, והן מתחילות לריב. גם בין דמטריוס לליסנדר פורצת מריבה, על רקע אהבתם המשותפת להלנה.