על אף השכיחות הנמוכה (פעם בכמה עשרות מיליוני שנים), פגעו מטאוריטי-ענק בכדור הארץ מספר פעמים. חוקרים סבורים כי מכתש צ'יקשולוב בחצי האי יוקטן, נוצר מפגיעת מטאוריט בקוטר של כ-10 ק"מ, שגרם לפיצוץ בעוצמה של כ-2,000,000 פצצות מימן. פגיעה זו הביאה, על פי חלק מהחוקרים, להכחדת הדינוזאורים לפני 65 מיליון שנה. מטאוריט עלול לגרום לצונאמי ואפילו למגה-צונאמי אם יפגע בלב ים.
המפורסם שבמכתשים הוא מכתש המטאור ("מכתש בארינגר") שבאריזונה, ארצות הברית, שקוטרו כקילומטר ונוצר כתוצאה מפגיעה של מטאוריט ברזלי.
קיימת סברה כי אירוע טונגוסקה שהתרחש ברוסיה ב-1908, בו נגרם נזק משמעותי לקרקע (מיליוני עצים נעקרו) אך לא נמצא מכתש פגיעה, נגרם כתוצאה מגוף סלעי גדול שקוטרו 37 מטרים ומשקלו לפחות 100,000 טון, שהתפוצץ באוויר בגובה 5-10 קילומטרים מעל הקרקע במהלך מעברו באטמוספירה וגרם לגלי הלם שהביאו להרס הרב.
ב-15 בפברואר 2013, התפוצץ מטאור בקוטר של כ-17 מטרים מסוג כונדריט בגובה של כ-23 קילומטר סמוך לעיר צ'ליאבינסק, ברוסיה. הפיצוץ גרם ל-1,500 פצועים, בהם שניים קשה, בעיקר מחלונות זכוכית שבורים שהתנפצו על ידי גל ההלם, ולנזק סביבתי רב. רסיס גדול מהמטאור נפל לאגם, ולאחר מבצע שנמשך מספר שבועות הוא נמשה מן המים ונמצא כי מסתו הכוללת היא 654 קילוגרמים.
סלע שנוצר או השתנה מהלחץ והחום של מטאוריט נקרא Impactite.
מחקר.
הפיזיקאי הגרמני ארנסט פלורנס צ'לדני היה הראשון שהעלה את רעיון שלפיו מטאוריטים הם למעשה סלעים מהחלל החיצון בשנת 1794. הקהילה המדעית באותו הזמן הגיבה בהתנגדות ובלעג. רק לאחר כעשור הושגה הסכמה כללית לגבי מקור המטאוריטים הודות לעבודתם של המדען הצרפתי ז’אן-בטיסט ביו והכימאי הבריטי אדוארד הווארד.
מטאוריטים נקראים על שם המקום בו הם נמצאו (בדרך כלל עיר קרובה או מאפיין גאוגרפי). השם שניתן למטאוריטים על ידי האגודה המטאוריטית משמש מדענים, קטלוגים ואספנים.
אלגוריתם דייקסטרה
אלגוריתם דייקסטרה, פרי יצירתו של אדסחר דייקסטרה, פותר את בעיית מציאת המסלול הקל ביותר מנקודה בגרף ליעד בגרף ממושקל. מכיוון שניתן למצוא באמצעות אלגוריתם זה, בזמן זהה, את המסלולים המהירים לכל הנקודות בגרף, בעיה זאת נקראת לעיתים מציאת המסלולים הקלים מנקודה.
האלגוריתם עובד על גרף נתון, מכוון או לא מכוון, בעל משקולות אי-שליליות על הקשתות. המשקולות בגרף מסמלות מרחק. משמעותו של המסלול הקצר ביותר בין שתי נקודות היא המסלול בעל סכום המשקולות הנמוך ביותר בין שתי הנקודות.
תוצאת האלגוריתם של דייקסטרה זהה לתוצאת אלגוריתם בלמן-פורד אך אלגוריתם בלמן-פורד פועל גם על גרפים הכוללים קשתות שמשקלן שלילי. לעומת זאת, זמן הריצה של אלגוריתם דייקסטרה מהיר יותר.
פעולת האלגוריתם.
בתמצית ניתן לסכם את פעולת האלגוריתם כך:
עבור כל קודקוד, מסומן האם ביקרו בו או לא ומה מרחקו מקודקוד המקור, אותו נסמן ב-S. בהתחלה כל הקודקודים מסומנים שלא ביקרו בהם, ומרחקם מוגדר כאינסוף.
לולאת האלגוריתם:
פסאודו קוד:
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph: // Initialization
dist[v] ← INFINITY // Unknown distance from source to v
prev[v] ← UNDEFINED // Previous node in optimal path from source
add v to Q // All nodes initially in Q (unvisited nodes)
dist[source] ← 0 // Distance from source to source
while Q is not empty:
u ← vertex in Q with min dist[u] // Node with the least distance will be selected first
remove u from Q
for each neighbor v of u: // where v is still in Q.
alt ← dist[u] + length(u, v)
if alt &lt; dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
האלגוריתם מסתיים כאשר קודקוד X החדש הוא היעד או (למציאת כל המסלולים המהירים ביותר) כאשר ביקרנו בכל הקודקודים.
סיבוכיות האלגוריתם תלויה במבנה הנתונים השומר את הקודקודים שטרם ביקרנו בהם, אם מדובר ברשימה או במערך, הסיבוכיות היא ב-formula_1, אם משתמשים בערימה בינארית סיבוכיות הריצה נהיית formula_2 ואם משתמשים בערימת פיבונאצ'י הסיבוכיות משתפרת ל- formula_3.
רעיון האלגוריתם.
אלגוריתם דייקסטרה מבוסס על שני רעיונות אלגוריתמיים. הראשון הוא שימוש בתת-בעיות כדי לפתור את בעיית המסלול הקצר ביותר.
יהי P המסלול הקצר ביותר מקודקוד S לקודקוד T. ייתכן ש-P עובר בקודקודים רבים. עבור כל קודקוד V, החלק ממסלול P שמגיע מ-S אליו מהווה את הדרך הקצרה ביותר האפשרית להגיע מ-S ל-V. אם לא כן, ניתן היה לקצר את המסלול מ-S ל-V ובכך להקטין את המרחק הכולל מ-S ל-T, ואם כך P אינו המסלול הקצר ביותר, בסתירה להגדרתו.
עקרון זה מאפשר לבסס את מציאת המסלול הקצר ביותר על מעין תכנון דינאמי. הפתרון לבעיה מצוי בפתרון לתת הבעיות שלה. המסלול הקצר ביותר מ-S ל-T יימצא על סמך המסלולים הקצרים ביותר מ-S לקודקודים שקדמו ל-T.
עיקרון שני הוא חמדני. בכל שלב מסוים במצב שבו נקבע מרחקם הקצר ביותר מ-S של חלק מהקודקודים, אך לא נקבע מרחקם של קודקודים אחרים. הרעיון החמדני קובע כי בכל שלב יש להתבונן באלו מהקודקודים שלא נקבע מרחקם ושיש אליהם קשת מקודקודים שמרחקם כבר נקבע, וליטול מקבוצה זו את הקודקוד שהדרך אליו מ-S, שעוברת כולה בקודקודים שכבר נקבע מרחקם, היא הקצרה ביותר.
ההגיון בבסיס בחירה זו הוא שאין קצר יותר מהקצר ביותר. לא ניתן להגיע אל קודקוד בדרך קצרה יותר מאשר על ידי בחירת הדרכים הקצרות ביותר הזמינות בכל שלב. עיקרון זה אינו נכון כאשר יש משקולות שליליות לקשתות. ייתכן שדווקא קשת ארוכה תוביל אותנו לקשת שתסמל מרחק שלילי גדול, וסכום המרחק הכולל לקודקוד יהיה נמוך יותר מאשר אם נלך בעקבות הקשת הקצרה שנבחרה מיידית.
קישורים חיצוניים.
מצגת הסבר - אלגוריתם דייקסטרה
דויד הילברט
דויד הילברט (גרמנית: David Hilbert; 23 בינואר 1862 - 14 בפברואר 1943) היה מתמטיקאי גרמני, שהשפיע רבות על המתמטיקה של סוף המאה ה-19 ותחילת המאה ה-20, הן הודות לתרומתו הישירה והן בשל השפעתו על אחרים.
תולדות חייו.
דויד הילברט נולד ב-23 בינואר 1862 בעיירה ולאו (Wehlau) שליד קניגסברג, שהייתה באותה עת בירתה של פרוסיה המזרחית. בשנת 1880 החל ללמוד באוניברסיטת קניגסברג, שם התיידד עם הרמן מינקובסקי. בשנת 1885 קיבל תואר דוקטור, בהנחייתו של פרדיננד לינדמן. בשנים 1886–1895 כיהן כפרופסור באוניברסיטת קניגסברג. בשנת 1892 נישא לקטה ירוש, וכעבור שנה נולד בנם יחידם.
בשנת 1888 פרסם פליקס קליין, בכתב העת Mathematische Annalen שבעריכתו, מאמר מאת הילברט, שבו פתר הילברט את הבעיה המרכזית של תורת האינווריאנטים, בהראותו שלכל מערכת אינווריאנטים יש בסיס סופי. לפרסום המאמר התנגד פאול גורדן, מראשי העוסקים בתחום, שטען כי הוכחתו של הילברט "אינה מתמטיקה. זו תאולוגיה". בשנת 1895 הביא קליין את הילברט לאוניברסיטת גטינגן, שנחשבה באותה עת למרכז המחקר המתמטי המוביל בעולם. הילברט שימר את תהילתה של גטינגן עד לפרישתו בשנת 1932, והפך למתמטיקאי החשוב בדורו. על שיתוף הפעולה בין קליין להילברט כתב ההיסטוריון של המדע ליאו קורי:
הילברט היה חופשי מדעות קדומות לאומניות או גזעניות. חרף ההתנגדות בגרמניה לצירוף יהודים לסגל האקדמי, הילברט תמך בהצלחה במינוים של שני יהודים לפרופסורים: הרמן מינקובסקי ב-1902 ואדמונד לנדאו ב-1909. כאשר קליין פרש, מינה הילברט את המתמטיקאי היהודי ריצ'רד קוראנט למחליפו. הילברט תמך גם באמי נתר, מתמטיקאית יהודייה שההתנגדות למינויה, בעשור השני של המאה ה-20, נבעה בעיקר מהיותה אישה.
בשנות ה-20 של המאה ה-20 התקיימה מחלוקת בפילוסופיה של המתמטיקה בין הילברט לבין ל.א.י בראואר. בראואר תמך באינטואיציוניזם ואילו הילברט דגל בפורמליזם. המחלוקת הפכה לאידאולוגית כאשר בראואר הציג עצמו כ"אלוף הגרמניות הארית". כאשר בראואר מנע פרסום מאמרים של אוסטיודן בכתב העת Mathematische Annalen, הדיח אותו הילברט מעריכת כתב העת.
תרומותיו של הילברט.
בין תרומותיו הישירות היו עבודתו על שמורות (אינווריאנטות), בה הוכיח את "משפט הבסיס של הילברט", עבודתו בתורת המספרים האלגברית, האקסיומטיזציה של הגאומטריה האוקלידית באמצעות "מערכת האקסיומות של הילברט", הנחת הבסיס לאנליזה הפונקציונלית עם ניסוח הגרסה הראשונית של "מרחבי הילברט", והסיוע שלו לאלברט איינשטיין בניסוח תורת היחסות הכללית.
הילברט ידוע גם בשל תרומותיו העקיפות וההנהגה החזקה שסיפק לעולם המתמטיקה:
בקונגרס הבינלאומי השני של המתמטיקאים שנערך בפריז בשנת 1900, הציג הילברט רשימה של 23 בעיות מתמטיות חשובות שלא נפתרו עד זמנו.
אחדות מהן נפתרו מאז, אחדות הוכחו כבלתי פתירות, ואחדות עדיין נותרו פתוחות בימינו.
הילברט היה ממובילי הזרם הפורמליסטי בפילוסופיה של המתמטיקה. הפרויקט השאפתני ביותר שלו היה תוכנית הנקראת "תוכנית הילברט", שלפיה יש לבסס את כל המתמטיקה על אקסיומות באופן פורמלי כך שניתן יהיה לבדוק את תקפות כל משפט על בסיס אקסיומות אלו (כלומר לבנות תורה עקבית, אפקטיבית ושלמה). הפרויקט הסתיים שלא כפי שתכנן הילברט, לאחר שקורט גדל הוכיח כי תוכנית כזו אינה ניתנת לביצוע.
הילברט עסק גם בפופולריזציה של המתמטיקה, ודוגמה מובהקת לפעילותו בתחום זה היא סיפור "המלון של הילברט", הממחיש את התכונות המיוחדות של מושג האינסוף.
הנצחה.
בשנת 1970 מכתש על הירח נקרא על שמו של הילברט.