פורטל:מדעי המחשב/יסודות

מתוך המכלול, האנציקלופדיה היהודית

< פורטל:מדעי המחשב

קפיצה לניווט קפיצה לחיפוש

גרף הינו אחד ממבני הנתונים השימושיים ביותר. בדוגמה לעיל, עץ פורש מינימלי, אשר מתאר את אוסף הקשתות בעל המשקל הנמוך ביותר, אשר מכסה את כלל צמתי הגרף.

מדעי המחשב, בהיותם מדע, מתבססים על יסודות מתמטיים רבים מתחום האלגברה, הקומבינטוריקה והלוגיקה. מדעי המחשב מציעים מגוון של מבני נתונים מופשטים המהווים מודל מתמטי נוח עבור בעיות יום-יומיות. שימוש במודלים אלו מאפשר גיבוש, ניתוח ומיטוב אלגוריתמים עבור בעיות אלו.

שיטות ייצוג וספירה

סיבית • בית • מילה • בסיס • השיטה העשרונית • בסיס בינארי • משלים ל-2 • בסיס אוקטלי • בסיס הקסדצימלי

לוגיקה מתמטית

אם-אז • אם ורק אם • DNF • CNF • משפטי אי השלמות של גדל • ריגורוזיות • שפה מסדר ראשון • תחשיב הפסוקים • תחשיב למדא

הוכחה לוגית

אינדוקציה מתמטית • דוגמה נגדית • הוכחה בדרך השלילה • הוכחה בנפנופי ידיים • הוכחה שגויה • הפרכה • השערה • כוח גס • כלל היסק • כלל השלישי מן הנמנע

פעולות בוליאניות

NOT • OR • NOR • AND • NAND • XOR

ראו גם: אלגברה בוליאנית

לוגיקה בוליאנית

טבלת אמת • כללי דה מורגן • מפת קרנו • שער לוגי

קומבינטוריקה

בעיית הנהגים הגחמנים • הבינום של ניוטון • מספר מוצקין • מספר קטלן • משולש פסקל • משפט החתונה • משפט רמזי • נוסחת נסיגה • עקרון ההכלה וההפרדה • עקרון שובך היונים • פונקציית אוילר • פונקציה יוצרת • פונקציית החלוקה • פונקציית מביוס • תמורה

התפוצצות קומבינטורית

עצרת • פונקציית אקרמן • פונקציות בעלות גידול על-מעריכי

מבני נתונים

מבנה נתונים מופשט • רשימה (list) • קבוצה (set) • מערך (array) • רשימה מקושרת (linked list) • טבלת גיבוב (Hash Table) • מחסנית (stack) • תור (queue) • דו-תור (deque) • גרף (graph) • ערימה (heap) • פילטר בלום

עץ חיפוש (tree)

עץ AVL • עץ אדום שחור • עץ B • עץ B+ • עץ 2-3 • עץ 2-3-4 •עץ SPLAY • עץ kd • עץ R

תורת הגרפים

גרף דו-צדדי (דו-חלקי) • גרף מישורי • גרף מכוון • גרף ממושקל • גרף מרחיב • גרף משלים • גרף קיילי • גרף קשיר • גרף שלם • גרף תשתית • גרפים מקריים • היפרגרף • מולטיגרף • עץ • עץ בינומי • עץ פורש • עץ פורש מינימלי • יער

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=פורטל:מדעי_המחשב/יסודות&oldid=96060"