תוצאה מעניינת נוספת היא הסיבוכיות המשוערכת של מבנה הנתונים. עבור formula_6 פעולות על formula_6 עצמים, תתקבל סיבוכיות משוערכת של formula_26 עבור ביצוע פעולה יחידה.
מימוש בעזרת יער של קבוצות זרות.
יער של קבוצות זרות הוא מימוש של מבנה הנתונים בו כל קבוצה מיוצגת בעזרת עץ.
במימוש הנאיבי, הנציג של כל קבוצה מוגדר להיות שורש העץ. חיפוש עוקב אחרי אבותיהם של איברים בעץ עד למציאת השורש. איחוד ממזג שני עצים בעזרת קביעת שורשו של עץ אחד כאביו של שורשו של העץ השני. במימוש זה, הגישה אינה טובה יותר מגישת הרשימות המקושרות, כיוון שהעצים שנוצרים אינם מאוזנים מבחינת הסתעפות הבנים. בהמשך נציג שני שיפורים אפשריים לשיטת היער.
להלן מימוש אפשרי בשיטה הנאיבית. נשים לב כי לצורך מניעת טיפול במקרי קצה, הגדרנו את אביו של שורש להיות השורש עצמו.
function "MakeSet"(x)
x.parent := x
function "Find"(x)
if x.parent == x
return x
return "Find"(x.parent)
function "Union"(x, y)
xRoot := "Find"(x)
yRoot := "Find"(y)
xRoot.parent := yRoot
איחוד על פי דרגה.
העקרון המנחה של גישה זו הוא שמירה על עומק עץ מינימלי, בעזרת שרשור העץ הקטן יותר (מבחינת עומק) אל שורשו של העץ הגדול יותר בזמן פעולת איחוד. כתוצאה מכך, העץ המאוחד יהיה בעל עומק גדול יותר אם ורק אם עומקי העצים שאוחדו היו זהים. בהקשר של האלגוריתם, המונח דרגה בא לידי שימוש במקום המונח עומק, מכיוון שכפי שנראה בהמשך, לאחר שיפורים באלגוריתם, ערך זה כבר לא יהיה זהה לעומק העץ על פי הגדרתו.
עצים בעלי איבר יחיד יוגדרו להיות בעלי דרגה 0, ובכל פעם ששני עצים מדרגה formula_27 מאוחדים, דרגת העץ המאוחד תוגדר formula_28. נשים לב כי עבור עצים מדרגה שונה, דרגת העץ המאוחד תהיה זהה לדרגתו של העץ הגדול מביניהם.
שימוש בטכניקה זו לבדה מניב זמן ריצה של formula_26 לכל פעולת איחוד או חיפוש על פני מבנה נתונים בעל formula_6 עצמים. פסאודו קוד עבור מימוש הפעולות יצירה ואיחוד תחת טכניקה זו מוצג להלן.
function "MakeSet"(x)
x.parent := x
x.rank := 0
function "Union"(x, y)
xRoot := "Find"(x)
yRoot := "Find"(y)
if xRoot == yRoot
return
// x and y are not already in same set. Merge them.
if xRoot.rank &lt; yRoot.rank
xRoot.parent := yRoot
else if xRoot.rank &gt; yRoot.rank
yRoot.parent := xRoot
yRoot.parent := xRoot
xRoot.rank := xRoot.rank + 1
דחיסת מסלולים.
השיפור השני שנציג הוא "דחיסת מסלולים". נרצה לשטח את מבנה העץ בכל פעם שפעולת חיפוש מבוצעת עליו. הרעיון הבסיסי הוא שכל איבר בו אנו מבקרים בדרך אל השורש, יכול להתחבר ישירות אל השורש (כזכור, כל האיברים בעץ חולקים את אותו השורש שהוא גם הנציג). בפועל, בעת חיפוש, נטפס באופן רקורסיבי במעלה העץ ונערוך את מצביע האב של כל איבר במסלול כך שיצביע אל השורש. העץ המתקבל הוא שטוח יותר, תוצאה אשר ממריצה את זמני הריצה של פעולות עתידיות על מבנה הנתונים. פעולת חיפוש משופרת תמומש כדלהלן.
function "Find"(x)
if x.parent != x
x.parent := "Find"(x.parent)
return x.parent
ניתוח אסימפטוטי משוערך.
לוגריתם חוזר.
הניתוח המוכר הראשוני של זמן לכל פעולה הוכח על ידי הופקרופט ואולמן בשנת 1973 ונקבע בתור formula_31, הלוגריתם החוזר. נוכיח כי עבור formula_5 פעולות של איחוד או חיפוש, המופעלות על מבנה נתונים בעל formula_6 עצמים, מתקבל זמן ריצה של formula_34.
"למה 1:" דרגת הצמתים לאורך מסלול חיפוש גדלה ממש.
"למה 2:" לעץ בעל שורש עם דרגה formula_27 יש לפחות formula_39 איברים (כולל השורש).
למה 3: המספר המרבי של צמתים בעלי דרגה formula_27 הוא לכל היותר formula_48.
מטעמי נוחות, נגדיר "דלי": דלי הוא קבוצה של צמתים בעלי דרגות.
בהינתן קבוצת עצמים (צמתים), אנו יוצרים דליים וממיינים אליהם צמתים על פי דרגותיהם ועל פי החוקיות הבאה: צמתים בעלי דרגה 0 ישוייכו לדלי שיתוייג ב-0, צמתים בעלי דרגה 1 ישוייכו לדלי שיתוייג ב-1, צמתים בעלי דרגה 2 או 3 ישוייכו לדלי שיתוייג ב-2, ובאופן כללי, צמתים בעלי דרגה בין formula_56 לבין formula_57 ישוייכו לדלי שיתוייג ב-formula_56.
נוכל לבצע שתי אבחנות לגבי הדליים:
כל צומת מתחיל כקבוצה בפני עצמה, המונה איבר יחיד, ולכן על מנת שהעץ formula_77 יהיה מגודל formula_79, חייבים להפעיל לפחות formula_80 פעולות איחוד על העץ, ובפרט formula_81.
נראה עתה כי לכל עץ formula_77, עלות formula_76 הפעולות שבוצעו בו חסומה על ידי formula_84.
ולסיכום, העלות של formula_76 פעולות על העץ formula_77 מורכבת מהעלות של formula_86 בזכות קשתות מסוג 1, formula_107 בזכות קשתות מסוג 2 וכן formula_107 בזכות קשתות מסוג 3. העלות הכוללת של כלל הפעולות על העץ נתונה על ידי formula_107.
נסכום מסקנה זו על פני כל העצים במבנה הנתונים, כאשר נזכור כי formula_110, ונקבל כי העלות הסופית היא formula_34, כנדרש.
חסם הדוק יותר.
למעשה, שימוש בטכניקות שפורטו לעיל יניב סיבוכיות משוערכת של formula_112 בלבד לכל פעולה, כאשר formula_113 היא הפונקציה ההופכית לפונקציה formula_114, כאשר formula_115 היא פונקציית אקרמן, הידועה בתכונתה כפונקציה שגדלה מהר מאוד. בתור ההופכית לפונקציית אקרמן, formula_113 היא בפועל פחות מ-5 לכל ערך מעשי של formula_6. לדוגמה, המספר formula_118, כאשר formula_119 הוא אופרטור העצרת, הוא בעל 35,164 ספרות ומתקבל formula_120).
כך, הסיבוכיות המשוערכת לפעולה היא למעשה קבוע זעיר. רוברט טרג'אן היה הראשון להוכיח את החסם על סיבוכיות הזמן במונחים של פונקציית אקרמן בשנת 1975. אמנם הלוגריתם החוזר הוא פונקציה הגדלה מאוד לאט, אך לא לא באותה מידת איטיות כפי של פונקציית אקרמן ההופכית.
פרדמן ("Fredman") וסאקס ("Saks") הראו בשנת 1989 כי formula_121 עצמים בהכרח זוכים לגישה על ידי פעולה כלשהי על מבנה הנתונים בממוצע. תוצאה זו מראה כי החסם שנמצא הוא אופטימלי מבחינה אסימפטוטית.
יישומים.
איחוד קבוצות זרות יכול להוות מודל של חלוקה של קבוצה, כדי, לדוגמה, לעקוב אחרי רכיבי קשירות בגרף לא מכוון. מודל זה יכול לעזור לנו בקביעה האם זוג צמתים בגרף שייכים לאותו רכיב קשירות, או האם הוספת קשת בין זוג צמתים תגרום ליצירת מעגל. אלגוריתם איחוד-חיפוש נמצא בשימוש נרחב במערכות בעלות ביצועים ברמה גבוהה המממשות איחוד-גרפים ("Unification"), תהליך החישוב של הגרף הכללי ביותר המכליל את הגרפים שניתנו כקלט. שימוש נוסף לדוגמה למימוש אלגוריתמים בתורת הגרפים, הוא מימוש האלגוריתם של קרוסקל למציאת עץ פורש מינימלי.
מימוש ביטויי שוויון בשפת Fortran עושה שימוש באלגוריתם איחוד-חיפוש.
יישומים נוספים כוללים שימושים בתחומי עיבוד תמונה, אלגוריתמי היסק וכן במידול מערכות פיזיקליות, כגון חלחול.
שער חליפין קבוע
שער חליפין קבוע הוא שער חליפין שנקבע על ידי הממשלה או גוף חוקי מוסמך אחר בעל הסמכות המוניטרית; זאת, בניגוד לשער חליפין נייד שמתנייד על פי כוחות השוק. את שער החליפין הקבוע אפשר להוריד, פעולה הנקראת "פיחות"; או להעלות, פעולה המכונה "ייסוף".
שער חליפין קבוע יכול להיקבע במדינה מסוימת או במספר מדינות במקביל, על פי הסכם כלכלי ביניהן. כאשר מונהג שער חליפין קבוע, נוהג הבנק המרכזי להתערב בשוק המטבעות כשהוא קונה או מוכר את המטבע שעליו קיים השער, כדי למנוע פער בין השער שאמור להיות על פי כוחות השוק לבין השער שנקבע. הסמכות המוניטרית תקבע את שער החליפין במונחים של משקל קבוע של זהב שנמצא ברשותה או סכום קבוע של יתרות מטבע או סל מטבעות.
בשיטת שער החליפין הקבוע הסמכות המוניטרית מנתבת את השער לכיוון הרצוי לה. אולם, הסמכות המוניטרית מאבדת בכך את שליטתה על כמות יתרות מטבע החוץ, וכמו כן הקנייה והמכירה של מטבע חוץ משנות את כמות הכסף במשק, דבר המאלץ את הבנק המרכזי לנקוט פעולות אחרות שיש להן השפעה על כמות הכסף. בנוסף, התערבות הבנק המרכזי כוחה יפה במיתון תנודות קצרות טווח; כאשר מתרחשים במשק שינויים מהותיים, ההתערבות אינה יעילה.
לורה ואנדרוורט
פלוגות העבודה
מודל wireframe
מודל wireframe הוא סוג של ייצוג גרפי ממוחשב לגוף תלת ממדי המשמש לצורך יצירת הדמיות בגרפיקה ממוחשבת תלת-ממדית. בטכניקה זו מוצגים רק המצולעים המרכיבים את האובייקט, אשר למעשה מורכבים מקווים המחברים נקודות וקטור שונות, בעוד שהאובייקט עצמו הוא שקוף כמעט לחלוטין.
מכיוון שההדמיה של מודל wireframe בתוכנות מחשב היא מהירה ופשוטה יחסית לחישוב, לעיתים רבות נעשה שימוש במודלי wireframe פשוטים יחסית במקרים בהם יש צורך לבצע הדמיה בזמן אמת כאשר קצב רענון הפריימים גבוה יחסית - לדוגמה, במהלך שנות ה-80 ושנות ה-90 של המאה ה-20 נעשה שימוש נרחב במודלי wireframe במשחקי וידאו על מנת לשלב במשחקים אובייקטים תלת ממדיים אשר נעים בזמן אמת.
קונסטנטין (סדרת טלוויזיה)
קונסטנטין היא סדרת על-טבעי מבית היוצר של רשת NBC המבוססת על האנטי-גיבור ג'ון קונסטנטין מהקומיקס ליגת הצדק האפל מבית DC קומיקס. הסדרה הופקה על ידי דניאל סרון ודייוויד ס. גויר שמשמשים גם כתסריטאים.
הפקה.
בינואר 2014, רשת NBC הודיעה באופן רשמי כי הזמינה פרק פיילוט לסדרה שתהיה מבוססת על סדרת הקומיקס על דמותו של ג'ון קונסטנטין.
ההפקה אישרה כי הדמות תהיה בריטית ובלונדינית, בהתאם לכתוב בקומיקס ולא כפי שנעשה בסרט קונסטנטין בכיכובו של קיאנו ריבס. זמן קצר לאחר מכן אושר כי ניל מרשל מביים את פרק הפיילוט. הסדרה מתוכננת להיות נאמנה יותר למקור, לעומת הסרט באותו השם.