על שם הגבעה אשר היוותה את המרכז השלטוני של האימפריה הרומית נקראת גבעת הקפיטול שעליה נמצא הקפיטול בוושינגטון בירת ארצות הברית.
קורדונאטה.
הקורדונאטה הוא גרם המדרגות המונומנטלי המוביל לכיכר הקמפידוליו בראש הגבעה. הוא תוכנן על ידי מיכלאנג'לו וידוע במדרגותיו הרחבות המאפשרות לסוסים לעלות במדרגות, וזאת על מנת לאפשר לאצילי רומא לעלות במדרגות בעודם רכובים על סוסיהם.
בוטרוס בוטרוס ראלי
בּוּטְרוֹס בּוּטְרוֹס-רַאלִי (בערבית: بطرس بطرس غالي, בתעתיק מדויק: בטרס בטרס ע'אלי; בקופטית: Ⲡⲉⲧⲣⲟⲥ Ⲡⲉⲧⲣⲟⲥ-Ⲅⲁⲗⲓ; 14 בנובמבר 1922 – 16 בפברואר 2016) היה דיפלומט ופוליטיקאי מצרי שכיהן כשר החוץ של מצרים בין השנים 1977–1991, וכמזכ"ל האו"ם בין השנים 1992–1996.
קורות חיים.
נעוריו ותחילת דרכו.
בוטרוס-ראלי נולד בקהיר למשפחה קופטית. סבו היה שר החוץ ולאחר מכן ראש ממשלת מצרים, בוטרוס ראלי (1910-1846). הוא סיים את לימודיו באוניברסיטת קהיר ב־1946 וקיבל דוקטורט במשפט בינלאומי מאוניברסיטת פריז ותעודה ביחסים בינלאומיים מהמוסד למדעי המדינה של פריז ב-1949. באותה שנה מונה לפרופסור למשפט בינלאומי ויחסים בינלאומיים באוניברסיטת קהיר, משרה אותה החזיק עד 1977. הוא היה לנשיא המרכז למדעי המדינה ולימודים אסטרטגיים ב־1975, ולנשיא החברה האפריקאית למדעי המדינה ב־1980.
בשנים 1954–1955 למד באוניברסיטת קולומביה במסגרת תוכנית פולברייט, בין 1963 ל־1964 עמד בראש המרכז למחקר של האקדמיה למשפט בינלאומי בהאג, ובשנים 1967–1968 היה מרצה אורח בפקולטה למשפטים של אוניברסיטת פריז.
הוא נישא ללאה-מריה, בת למשפחת נדלר היהודייה שהגיעה מרומניה לאלכסנדריה והמירה דתה לנצרות קתולית בצעירותה.
קריירה דיפלומטית.
במצרים.
בוטרוס-ראלי מונה לשר החוץ של מצרים ב-1977, במקומו של איסמעיל פהמי, שהתנגד לביקור נשיא מצרים סאדאת בישראל, וכיהן בתפקיד עד 1991. לאחר מכן היה לתקופה קצרה לסגן ראש הממשלה לענייני חוץ, לפני שעבר לאו"ם. כשר החוץ השתתף בוועידה שהובילה לחתימת הסכמי קמפ דייוויד, והיה לו חלק בהשגת הסכם השלום בין ישראל למצרים.
בראשות האו"ם.
ב־1992 נבחר למזכ"ל האו"ם. הוא ספג ביקורת על אזלת ידו של האו"ם לנוכח רצח העם ברואנדה ומלחמת האזרחים באנגולה. האו"ם בראשותו התקשה גם להתמודד עם מלחמת אזרחים ביוגוסלביה המתפוררת, במישור הדיפלומטי וההומניטרי.
ב־1996 העלו עשר חברות מועצת הביטחון, בראשות שלוש החברות האפריקאיות מצרים, גינאה ביסאו ובוטסואנה, את מועמדותו לכהונה שנייה (חמש שנים נוספות) כמזכ"ל האו"ם. ארצות הברית מנעה יזמה זו כשהטילה וטו על מועמדותו. חברות המועצה בריטניה, פולין, קוריאה הדרומית ואיטליה הצביעו בעד בוטרוס-ראלי, אך רק לאחר שהווטו האמריקני הוכרז, ולא הוסיפו את תמיכתן להצעת המועמדות קודם לכן. כך היה בוטרוס-ראלי למזכיר הראשון בתולדות הארגון שלא נבחר לכהונה שנייה.
אחרי סיום תפקידו באו"ם.
בוטרוס-ראלי שימש מ־1997 עד 2002 כמזכיר הכללי של הארגון הבינלאומי לפרנקופוניה, ארגון המאגד מדינות דוברות צרפתית. הוא כיהן כראש המועצה המנהלת של האקדמיה למשפט בינלאומי בהאג.
בספטמבר 2004, בריאיון לטלוויזיה המצרית, כינה את ארצות הברית "משטר טוטליטרי" בכל הנוגע ליחסי החוץ שלה.
פאזה
פרננדס
פרננדס הוא שם משפחה ספרדי נפוץ.
סיבוכיות מקום
במדעי המחשב, כאשר עוסקים בניתוח המשאבים שדורשים אלגוריתמים משתמשים במושג של סיבוכיות מקום (המכונה גם סיבוכיות זיכרון) על מנת להעריך את כמות זיכרון המחשב הדרוש להם. מדד זה ומדד סיבוכיות הזמן של ריצת אלגוריתמים הם שני המדדים הנפוצים ביותר לסיבוכיות אלגוריתמים, וקיימים קשרים הדוקים בין שניהם.
מבוא.
כל אלגוריתם, כשהוא ממומש כתוכנת מחשב, זקוק לכמות כלשהי של זיכרון מחשב לצורך ריצתו. חלק מהזיכרון נדרש לאלגוריתם לצורך שמירת נתוני עזר שנדרשים במהלך ביצוע התוכנה. זיכרון נוסף דרוש על מנת לאחסן את הקלט של האלגוריתם ואת הפלט שלו. כמו כן, חלק מהזיכרון דרוש כדי לאחסן את הקוד אשר מממש את האלגוריתם.
כאשר עוסקים בחקירה תאורטית של ביצועי האלגוריתם, נהוג להתעלם מאספקטים טכניים הקשורים ישירות למימוש של האלגוריתם במחשב מסוים, ועל כן ההתמקדות היא רק בזיכרון הדרוש לצורך קלט, עיבוד ופלט הנתונים. כמו כן, נהוג להשתמש במודל מתמטי מופשט של מחשב לביצוע הניתוח, כאשר המודל המקובל ביותר הוא זה של מכונת טיורינג.
מכיוון שבהינתן בעיה כלשהי, גודל הקלט וגודל הפלט אינם תלויים באלגוריתם הפותר אותה, לא נהוג להחשיב אותם כחלק מהזיכרון אותו דורש האלגוריתם. אם כן, עיקר ההתמקדות בחקר סיבוכיות מקום היא בזיכרון העזר הנדרש לצורך ביצוע האלגוריתם.
מכיוון שקשה להעריך במדויק את כמות הזיכרון שדורש אלגוריתם, נהוג להשתמש בהערכה החוסמת את כמות הזיכרון המקסימלית שאותה ידרוש האלגוריתם. מכיוון שעבור קלטים ארוכים יותר נדרש לרוב זיכרון רב יותר, בעיקר מתעניינים בהתנהגות האסימפטוטית של כמות הזיכרון הנדרשת כפונקציה של גודל הקלט.
סיבוכיות זיכרון של בעיית הכרעה ידועה בתור סיבוכיות הזיכרון המינימלית של מכונת טיורינג המממשת אותה. הגדרה נאיבית של סיבוכיות הזיכרון של מכונת טיורינג היא כמות תאי הזיכרון של המכונה שבהם נעשה שימוש - בצורה פורמלית, מספרו של התא הימני ביותר שאליו הראש הקורא הגיע (כאשר המודל הוא מכונת טיורינג חד סרטית, שהסרט שלה אינסופי בכיוון ימין בלבד).
הבעייתיות שבהגדרה הנאיבית נעוצה בכך שהן הקלט והן הפלט של המכונה כתובים על הסרט, ולכן נחשבים לחלק מהמדד. למשל, אלגוריתם אשר מקבל מספר ובודק האם ספרתו האחרונה היא 1 לא ידרוש כלל זיכרון עזר (שכן כל שעליו לעשות הוא לבדוק את הביט האחרון בקלט שקיבל), אך סיבוכיות הזיכרון שלו היא ליניארית באורך הקלט (שכן הקלט נחשב לחלק מהזיכרון שבו משתמשת המכונה).
בשל בעיה זו, נהוג להשתמש בווריאציה על המודל הסטנדרטי של מכונת טיורינג: מכונת טיורינג בעלת סרט קלט לקריאה בלבד, סרט פלט לכתיבה בלבד, וסרט "עבודה". קל להראות שהמודל הזה של מכונת טיורינג שקול למודל הסטנדרטי (הוא ניתן למימוש באמצעות המודל של מכונת טיורינג רב סרטית שגם הוא שקול למודל הרגיל), אך ניתן למדוד בו סיבוכיות זיכרון בצורה יעילה יותר אם היא מוגדרת ככמות תאי הזיכרון שבהם השתמשה המכונה מתוך "סרט העבודה" בלבד.
מחלקות סיבוכיות.
עבור פונקציה formula_1 מקובל להשתמש בסימון formula_2 כדי לסמן את אוסף כל בעיות ההכרעה עבורן קיימת מכונת טיורינג דטרמיניסטית שבהינתן קלט באורך formula_3 פותרת את הבעיה תוך שימוש בזיכרון של לכל היותר formula_1. לעיתים משתמשים בסימון אסימפטוטי על מנת לפשט את הכתיבה, ומסתפקים בכך שמכונת הטיורינג תפתור את הבעיה בזיכרון formula_5. כלומר - עבור קלטים גדולים מספיק, כמות הזיכרון הנדרשת קטנה מקבוע כלשהו כפול formula_1.
בצורה דומה מסמנים בתור formula_7 את אוסף בעיות ההכרעה עבורן קיימת מכונת טיורינג לא דטרמיניסטית הפותרת את הבעיה תוך שימוש בזיכרון formula_1.
בעזרת הסימונים הללו ניתן להגדיר כמה ממחלקות הסיבוכיות המרכזיות בהן עוסקים בחקר סיבוכיות זיכרון: PSPACE, L,NL,EXPSPACE.
קשר בין סיבוכיות מקום וסיבוכיות זמן.
ניתן להראות כי מתקיים formula_13 כלומר, לכל מכונה העובדת בסיבוכיות מקום formula_14 קיימת מכונה העובדת לכל היותר בסיבוכיות זמן שהיא אקספוננציאלית בסיבוכיות המקום formula_14 ופותרת את אותה הבעיה.
הטכניקה בה משתמשים כדי להראות זאת מבוססת על ספירת כל המצבים האפשריים של החישוב אותו מבצעת המכונה המקורית. כל מצב שכזה נקבע באופן יחיד על ידי תוכן סרט העבודה, מיקום הראש הקורא של המכונה והמצב הפנימי בו נמצאת המכונה. על מנת למנוע בלבול נהוג לכנות כל מצב שכזה בשם קונפיגורציה.
ניתן להראות כי מספר הקונפיגורציות האפשריות של מכונת טיורינג שעובדת בזיכרון של formula_16 הוא formula_17. זאת מכיוון שמספר המצבים הפנימיים הוא קבוע, מספר המקומות שבהם הראש הקורא יכול להיות הוא formula_14, ומספר האפשרויות השונות לתוכן סרט העבודה הוא formula_19 (בהנחה שא"ב העבודה הוא בינארי - אם הוא מכיל יותר אותיות ההבדל יהיה רק שינוי בבסיס החזקה).
הבחנה חשובה בהקשר זה היא כי אם חישוב של מכונת טיורינג מגיע פעמיים לאותה קונפיגורציה, החישוב מצוי בלולאה אינסופית (כלומר, יחזור על עצמו שוב ושוב לתמיד). בכל צעד חישוב מכונת הטיורינג עוברת מקונפיגורציה אחת לאחרת, ולכן אם המכונה תבצע יותר צעדי חישוב מאשר מספר הקונפיגורציות האפשריות, היא בהכרח תגיע לאותה קונפיגורציה פעמיים, ולכן היא נמצאת בלולאה אינסופית.
כעת, בהינתן מכונת טיורינג A הפותרת בעיה בזיכרון formula_16 ניתן לבנות מכונת טיורינג B שפותרת את אותה הבעיה בזמן formula_17 בצורה הבאה: B מבצעת סימולציה של ריצת A, וסופרת את כל הצעדים ש-A מבצעת. אם A חורגת ממספר הצעדים המותר, B עוצרת מיד ומחזירה תשובה שלילית.
מסקנה נוספת מקשר זה היא שמתקיים תמיד formula_22, כלומר כל בעיה שניתנת לפתרון באמצעות מכונת טיורינג בעלת זיכרון חסום, ניתנת גם להכרעה (כלומר, קיימת מכונת טיורינג שפותרת אותה ועוצרת לכל קלט).
קשר אלמנטרי נוסף בין סיבוכיות זמן וזיכרון הוא formula_23. קשר זה נובע מכך שמכונה שרצה formula_14 צעדים אינה מסוגלת לנצל יותר מ-formula_14 תאי זיכרון, שכן בכל צעד ניתן לנצל תא זיכרון חדש אחד לכל היותר. (ניתן גם להראות תוצאה טובה יותר formula_26)
משפטים הנוגעים לסיבוכיות זיכרון.
משפט סביץ'.