מרכז קרוגר למימון הוקם בשנת 1984, והוא תומך ומעודד מחקרים עיוניים בתחום המימון והבנקאות ומחקרים יישומיים הרלוונטיים לעולם העסקים והכלכלה הישראלית. המרכז תומך בביקורי חוקרים ובקיום ימי עיון בתחום המימון והבנקאות, ובפעילות חדר העסקאות של בית הספר.
פרסומי ניסא
מכלית (פירושונים)
עורבאים
עורבאים (שם מדעי: Corvida) היא אינפרא-סדרה של ציפורי שיר מתת-סדרת דמויי-דרור. זוהי קבוצה המכילה בעיקר את ציפורי השיר האוסטרליות כמו הנבליים, העדניים או סבכיי פיות וכן את העורביים, הזהבניים, החנקניים וקרוביהם.
ציפורים אלה הם גדולות יחסית למיני קבוצת הדרוראים והם חיים במגוון תנאי מחיה מיערות טרופיים ועד למדבריות ולמרומי ההרים. לחלקם ישנם נוצות כהות ואחרים בעלי צבעים בהירים. מקורם ארוך ונוקשה והם פולטים צעקות חזקות שאינם דומים לקריאות הנעימות של ציפורי שיר עדינים יותר. עם זאת חלקם יכולים לחקות קולות של חיות אחרות.
לחלק מהעופות ישנם הבדלים בולטים בין הזכרים לנקבות, בייחוד למינים האוסטרליים והניו זילנדים. כך למשל הנבליים או העדניים המפוארים שבנוסף לנוצותיהם מרקדים בצורות מוזרות לפני הנקבות.
ציפורים אלה הן אוכלות כל הניזונים הן מצמחייה והן מנבלות, חרקים ומחולייתנים קטנים.
אנליזה של אלגוריתמים
ניתוח של אלגוריתמים הוא תחום במדעי המחשב, העוסק בגילוי מאפיינים שונים באלגוריתמים, וסיווג רמת החיסכון שלהם.
סיווג רמת החיסכון של אלגוריתם מתבצע באמצעות קביעת כמות המשאבים, הנדרשים עבור ביצועו. בדרך-כלל, יעילותו של אלגוריתם תלויה במספר הצעדים (זמן המורכבות) ובשטח האחסון (מורכבות אחסון) הנדרשים.
המונח "ניתוח אלגוריתמים" נטבע על ידי דונלד קונת'. ניתוח אלגוריתמים הוא חלק חשוב של תאוריה רחבה יותר הנקראת תורת הסיבוכיות, אשר מספקת הערכות תאורטיות לכמות המשאבים הדרושים לכל אלגוריתם הפותר בעיה חישובית נתונה. הערכות אלו מספקות תובנות חשובות באשר לחיפוש אחר אלגוריתמים יעילים יותר ויותר.
בניתוח תאורטי של אלגוריתמים, נהוג להעריך את המורכבות שלהם במובן אסימפטוטי. כלומר, להעריך את מורכבות האלגוריתם עבור קלט שרירותי גדול. סימון O גדולה [formula_1], סימון אומגה גדול [formula_2] וסימון טטא גדול [formula_3] משמשים למטרה זו. למשל, חיפוש בינארי הוא חיפוש האמור לרוץ מספר צעדים, יחסי ללוגריתם של אורך הרשימה הממוינת שבה מתבצע החיפוש, או ב- formula_4, ב"זמן לוגריתמי".
ממד יעילות מדיוק (לא אסימפטוטי) ניתן לחישוב במקרים מסוימים אך בדרך כלל הוא דורש הנחות מסוימות לגבי יישום מסוים של האלגוריתם, הנקרא מודל של מחשוב. מודל של מחשוב עשוי להיות מוגדר במונחים של מחשב אבסטרקטי, למשל, מכונת טיורינג, או על ידי הנחה כי פעולות מסוימות מבוצעות ביחידת זמן.
לדוגמה, אם ברשימה הממוינת עליה אנו מריצים חיפוש בינארי יש "n" אלמנטים, ואנחנו יכולים להבטיח כי כל בדיקה של אלמנט ברשימה יכולה להתבצע תוך יחידת זמן, אז צריך לכל היותר log2 "n" + 1 יחידות זמן להחזיר תשובה.
דגמי עלויות.
הערכות יעילות זמן תלויות במה אנו מגדירים להיות צעד. כדי שניתוח האלגוריתם יתאים בצורה שימושית לזמן הביצוע בפועל, הזמן הנדרש כדי לבצע צעד חייב להיות חסום מלעיל על ידי קבוע. יש להיות זהיר בנקודה זו, למשל, כמה אנליזות זמנים סופרות חיבור של שני מספרים בתור צעד אחד. הנחה לא יכולה להיות מובטחת בתנאים מסוימים או בהקשרים מסוימים. לדוגמה, אם המספרים המעורבים בחישוב גדולים מאוד, במקרה זה לא ניתן להניח כי הזמן הנדרש על ידי פעולת חיבור יחידה הוא קבוע כלשהו.
יש שני מודלי חישוב עליות המשומשים בצורה נרחבת:
האחרון הוא יותר מסורבל לשימוש, לכן הוא משומש רק בעת הצורך, למשל בניתוח של אלגוריתמים של דיוק-שרירותי אריתמטי, כמו אלה אשר משתמשים בהם בקריפטוגרפיה.
נקודת מפתח אשר נוטים להתעלם ממנה לעיתים קרובות היא שחסמים תחתונים שפורסמו לבעיות הם לעיתים קרובות חושבו על מודל מחשוב אשר מוגבל יותר מאשר סט הפעולות שניתן להשתמש בו בפועל, ולכן יש אלגוריתמים מהירים יותר מאלה שניתן לדמיין בצורה נאיבית.
ניתוח זמן ריצה.
ניתוח זמן ריצה הוא סיווג תאורטי שמעריך וצופה את הגידול בזמן הריצה של אלגוריתם ככל שגודל הקלט שלו (לרוב מסומן כ-n) גדל. יעילות זמן ריצה היא נושא בעל חשיבות גבוהה במדעי המחשב: תוכנה יכולה לקחת שניות שעות או אפילו שנים כדי לסיים ביצוע, דבר שתלוי על איזה אלגוריתם היא מיישמת (ראו גם ניתוח ביצועים, כלומר הניתוח של זמן ריצה בצורה פרקטית).
החסרונות של אמות מידה אמפיריות.
כיוון שאלגוריתמים הם תלויי פלטפורמה (כלומר, אלגוריתם נתון יכול להיות מיושם בשפת תכנות שרירותית במחשב שרירותי ועל מערכת ההפעלה שרירותית), יש חסרונות משמעותיים לשימוש בגישה אמפירית למדדית הביצועים היחסיים של סט נתון של אלגוריתמים.
קחו כדוגמה תוכנה המחפשת ערך מסוים רשימה ממוינת בגודל "n". נניח שתכנה זו הושמה על מחשב א', מחשב חדיש עם חומרה מרמה גבוהה, תוך שימוש באלגוריתם חיפוש ליניארי, ועל מחשב ב', אשר איטי בהרבה מן המחשב הקודם, באמצעות אלגוריתם חיפוש בינארי. בוחן ביצועים על שני המחשבים המריצים את התוכנה בהתאמה עשוי להיראות משהו כמו טבלה זו:
בהתבסס על ערכים אלה, זה יהיה קל לקפוץ למסקנה כי על "מחשב א"' פועל אלגוריתם יעיל בהרבה מיעילות של האלגוריתם של "מחשב B". עם זאת, אם נגדיל את גודל הקלט בצורה מספקת, מסקנה זו הוא מוכחת להיות שגיאה:
מחשב א', מריץ את תוכנת החיפוש הליניארי, ומראה קצב גידול ליניארי. זמן הריצה של התוכנה הוא בעל יחס ישיר לגודל הקלט שלה. הכפלת גודל הקלט מכפיל את זמן הריצה, הכפלה פי ארבעה של גודל הקלט מכפילה פי ארבעה את זמן הריצה וכו'. מצד שני, מחשב ב', מריץ תוכנת חיפוש בינארי, ומראה קצב גידול לוגריתמי. הכפלת גודל הקלט פי ארבעה מגדיל את זמן הריצה על ידי קבוע בלבד (בדוגמה זו, 50,000 ns). אף על פי שמחשב א' מהיר יותר, מאשר מחשב ב'. מחשב ב' יתגבר על מחשב א' באופן בלתי נמנע ביעילות זמן ריצה מפני שהאלגוריתם שהוא מריץ בעל קצב גידול נמוך בהרבה.
רמות של קצב גידול.
באופן לא רשמי, ניתן לומר כי אלגוריתם מציג צמיחה בשיעור מסדר גודל של פונקציות מתמטיות אם עבור קלט מסוים בגודל "n", פונקציה formula_5 כפול קבוע חיובי מספקת את החסם העליון או הגבול של זמן הריצה של האלגוריתם. במילים אחרות, עבור גודל קלט "n" אשר גדול יותר מ-"n"0 "וקבוע c", זמן הריצה של אלגוריתם לעולם לא יהיה גדול מאשר formula_6. ביטוי זה מיוצג לעיתים קרובות על ידי סימון O גדולה. לדוגמה, כיוון שזמן הריצה של מיון הכנסה גדל בצורה מרובעת כמו שלה הקלט גדל, ההכנסה סוג יכול להיות אמר להיות של סדר "O"("n"2).
סימון O גדולה הוא דרך נוחה כדי לבטא את התרחיש הגרוע ביותר עבור אלגוריתם נתון, אף על פי שזה יכול לשמש גם כדי להביע את המקרה הממוצע — לדוגמה, התרחיש הגרוע ביותר עבור quicksort הוא "O"("n"2), אבל זמן הריצה עבור המקרה הממוצע הוא "O"("n" log "n").
רמות אמפיריות של קצב גידול.
תחת ההנחה שזמן הביצוע עוקב אחר כלל הכוח,formula_7, ניתן למצוא את המקדם על ידי לקיחת מדידות אמפיריות של זמן ריצה formula_8 על נקודות בעלות גודל בעייתי formula_9 וחישוב formula_10 כך formula_11. במילים אחרות, זה מודד את השיפוע של קו אמפירי על log-log plot של זמן הביצוע לעומת גודל הבעיה, בנקודת גודל כלשהי. אם רמת הצמיחה אכן מלווה את כלל הכוח (אזי הקו על log-log-plot אכן קו ישר), הערך האמפירי של "a" יישאר קבוע בטווחים שונים, ואם לא, הוא ישתנה (ואז הקו הוא קו מעוגל) - אבל זה עדיין יכול לשמש להשוואה של כל שני אלגוריתמים נתונים בהתחשבות בהתנהגות של "רמות קצב גידול מקומיות אמפיריות". ובהחלה על הטבלה מלעיל:
קל לראות כי האלגוריתם הראשון מראה קצב גידול ליניארי אשר בבירור עוקב אחרי כלל הכוח. הערכים האמפיריים עבור השני הולכים ופוחתים במהירות, מה שרומז כי האלגוריתם השני עוקב אחרי חוק אחר של קצב גידול ובכל מקרה יש לו רמות קצב גידול מקומיות הרבה יותר נמוכות (אשר עדיין משתפרות), באופן אמפירי, מאשר לאלגוריתם הראשון.
הערכת סיבוכיות זמן ריצה.
את מורכבות זמן הריצה למקרה הגרוע ביותר של אלגוריתם נתון ניתן לעיתים להעריך על ידי בחינת המבנה של האלגוריתם ולקיחת מספר הנחות מפשטות. נתבונן ב-pseudocode הבא:
if n &gt; 10
write 'This might take a while...'
for i = 1 to n
for j = 1 to i
write i * j
write 'Done!'
מחשב נתון ייקח כמות הזמן בדידה לביצוע כל הפקודות המעורבות עם ביצוע האלגוריתם הזה. כמות הזמן המסוימת כדי לבצע פקודה נתונה ישתנו בהתאם לפקודה אשר מתבצעת, ועל פי איך המחשב מבצע אותה, אבל על מחשב רגיל, כמות זמן זו היא דטרמיניסטית (המקרה שונה במקרה של מחשב קוונטי). נניח כי הפעולות שבוצעו בשלב 1 נחשבות צורכות זמן "T"1, אלה שבשלב 2 צורכות זמן "T"2, וכך הלאה.
באלגוריתם לעיל, שלבים 1, 2 ו-7 ירוצו פעם אחת בלבד. עבור הערכה של המקרה הגרוע ביותר, יש להניח כי שלב 3 יורץ גם הוא. לפיכך, הסכום הכולל של זמן כדי לריץ את צעדים 1–3 וצעד 7 הוא:
את הלולאות בשלבים 4, 5 ו-6 יותר מסובך להעריך. החיצונית בשלב 4 תרוץ ( "n" + 1 )