-
ניתוח אשכולות
כל מה שרצית לדעת על ניתוח אשכולות:בכריית מידע, סטטיסטיקה ולמידה חישובית, ניתוח אשכולות (באנגלית: Cluster Analysis) מתייחס למשימה של קיבוץ אובייקטים לקבוצות (אשכולות) כך שהאובייקטים הנמצאים באותה קבוצה דומים זה לזה יותר מאשר לאובייקטים השייכים לקבוצות אחרות.לניתוח אשכולות יש שימושים רבים במגוון תחומים. לדוגמה במחקר שיווקי, ניתוח אשכולות משמש לביצוע פילוח של הלקוחות לפי התנהגות…
-
משפט קירכהוף
כל מה שרצית לדעת על משפט קירכהוף:בתחום המתמטי של תורת הגרפים משפט קירכהוף או משפט מטריצת העץ של קירכהוף, הנקרא על שם הפיזיקאי הגרמני גוסטב קירכהוף, מספק את מספר העצים הפורשים בגרף. המשפט הוא הכללה לנוסחת קיילי הקובעת כי מספר העצים הפורשים בגרף שלם בעל n צמתים הוא n n − 2 {\displaystyle \…
-
משפט טורן
כל מה שרצית לדעת על משפט טורן:בתורת הגרפים, משפט טורן הוא משפט הקובע, בהינתן מספר קבוע של צמתים, את הגרף עם מספר הקשתות המקסימלי שאינו מכיל תת-גרף שלם (קליקה) מגודל נתון. את המשפט הוכיח המתמטיקאי ההונגרי פאול טורן (Paul Turán) בשנת 1941.ביתר פירוט, המשפט קובע כי הגרף עם n צמתים שאינו מכיל קליקה K…
-
משפט לובאס-קנזר
כל מה שרצית לדעת על משפט לובאס-קנזר:בתורת הגרפים, משפט לובאס-קנזר הוא משפט מתמטי שקובע את מספר הצביעה של גרף קנזר (אנ'). ייחודו של המשפט בכך שההוכחות הסטנדרטיות שלו מבוססות בעיקר על כלים מתחום הטופולוגיה. נלקח מויקיפדיה הגדרות נוספות הקשורות למשפט לובאס-קנזר:•משפטים בתורת הגרפים•הוכחות
-
אלגוריתם חיפוש לעומק
כל מה שרצית לדעת על אלגוריתם חיפוש לעומק:במדעי המחשב, אלגוריתם חיפוש לעומק (באנגלית: Depth-first search, ראשי תיבות: DFS) הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו.אינטואיטיבית, האלגוריתם מתחיל את החיפוש מצומת שרירותי בגרף ומתקדם לאורך הגרף עד אשר הוא נתקע, לאחר מכן הוא חוזר על עקבותיו עד שהוא יכול לבחור להתקדם לצומת אליו טרם…
-
קוטר
כל מה שרצית לדעת על קוטר:בגאומטריה, קוטר של מעגל הוא מיתר של המעגל שעובר דרך מרכזו. משתמשים במושג זה גם עבור האורך של הקוטר; אורכו של הקוטר כפול מאורכו של רדיוס המעגל. בתורת הגרפים הקוטר של גרף קשיר הוא המרחק הגדול ביותר בין שני צמתים בגרף, כלומר אורך המסלול הקצר ביותר בין שני הצמתים המרוחקים…
-
יוהאן מקובסקי
כל מה שרצית לדעת על יוהאן מקובסקי:יוהאן (ינוש) א. מקובסקי (Johann (János) A. Makowsky; נולד ב-12 במרץ 1948 בבודפשט) הוא לוגיקן ומדען מחשב שווייצרי ממוצא יהודי הונגרי, פרופסור מן המניין בטכניון.מקובסקי כתב את עבודת הדוקטורט שלו בלוגיקה מתמטית בציריך ב-1974. הוא שימש במשרות זמניות במרכז בנך בוורשה, באוניברסיטת סטנפורד בארצות הברית, באוניברסיטת סימון פרייז'ר בקנדה,…
-
בעיית צביעת המסלולים
כל מה שרצית לדעת על בעיית צביעת המסלולים:בעיית צביעת המסלולים היא בעיה ידועה בתורת הגרפים, העוסקת בצביעה של קשתות בגרף. לבעיה יישומים תאורטיים בתורת האוטומטים ובדינמיקה סימבולית, ויישומים פרקטיים בדחיסת מידע, תכנון ממוחשב ובדיקת פרוטוקולים.הבעיה הוצגה ב-1970 (ונוסחה במפורש ב-1977 ), בקשר להשערה (שהוכחה לבסוף בדרך אחרת), שהאנטרופיה הטופולוגית של מערכת דינמית בעל אופי…
-
אופטימיזציית קן הנמלים
כל מה שרצית לדעת על אופטימיזציית קן הנמלים:אופטימיזציית קן הנמלים (באנגלית: Ant Colony Optimization [או בקיצור ACO]) היא שיטת אופטימיזציה ששימושה המקורי הוא למציאת פתרון מקורב לבעיות קשות בתורת הגרפים שעיקרן מציאת מסלולים קצרים במשקל או מרחק, לדוגמה, בעיית הסוכן הנוסע. את השיטה ניסח ד"ר מרקו דוריגו בשנת 1992 כחלק מעבודת הדוקטורט שלו. הבעיה הראשונית…
-
אלגוריתמים לפתרון מבוכים
כל מה שרצית לדעת על אלגוריתמים לפתרון מבוכים:אלגוריתמים לפתרון מבוכים הם מספר אלגוריתמים שונים לפתרון באופן אוטומטי ושיטתי של מבוכים. העכבר האקראי, הליכה בעקבות הקיר והאלגוריתמים של פלדג' ושל טרימו, הם אלגוריתמים שנועדו לניווט בתוך מבוך ללא ידע מוקדם כלשהו על המבוך, בעוד שהאלגוריתמים של מילוי דרכים ללא מוצא והדרך הקצרה ביותר נועדו לשימוש אדם…