0 - הקדמה וקצת חזרה — קומבינטוריקה למדעי המחשב

בקורס שני חלקים:

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

ישנו חיבור חזק בין שני הנושאים.

קבוצות

הגדרה 1 (קבוצה)

קבוצה היא אוסף של איברים שונים, ללא חשיבות לסידורם.

דוגמה

X=\left\{ 1,2,3,4 \right\}

Y=\left\{ A,B,C,D,E,F \right\}

הגדרה (סימונים)

\emptyset=\left\{ \right\}

$a \in A$ אמ"מ האיבר $a$ נמצא בקבוצה $A$ .
$Y \subseteq X$ אם כל $y \in Y$ מקיים $y \in X$ .

הגדרה 2 (גודל של קבוצה)

גודל של קבוצה $X$ יהיה מספר האיברים בה ויסומן $|X|$ .

הגדרה (וקטור/סדרה/רשימה)

נסמן קבוצה עם חשיבות לסדר עם סוגריים עגולים:

(1,2,3,4)\neq(2,1,3,4)

כמה תתי קבוצות יש ל- $\left\{ 1,2,3 \right\}$ ?

\begin{matrix} \emptyset & \left\{ 1 \right\} & \left\{ 2 \right\} & \left\{ 3 \right\} & \left\{ 1,2 \right\} & \left\{ 1,3 \right\} & \left\{ 2,3 \right\} & \left\{ 1,2,3 \right\} \end{matrix}

פעולות על קבוצות

איחוד קבוצות - $X \cup Y$ - אוסף האיברים השייכים ל- $X$ או ל- $Y$ (או לשנייהם)
חיתוך קבוצות - $X \cap Y$ - אוסף האיברים השייכים ל- $X$ וגם ל- $Y$ .
קבוצות $X,Y$ יקראו זרות $X \cap Y=\emptyset \iff$ .
הפרש של קבוצות - $X \setminus Y$ .
מכפלה קרטזית של קבוצות - די נו, תסתכלו על מתקא.

פונקציות

הגדרה 3 (פונקציה)

פונקציה מקבוצה $X$ לקבוצה $Y$ היא התאמה המשייכת לכל איבר בקבוצה $X$ איבר יחיד בקבוצה $Y$ .

קומבי אולי.png

f:X\to Y

הגדרה 4 (פונקציה חח"ע)

פונקציה $f:X\to Y$ תקרא פונקציה חד חד ערכית אם לכל איבר בטווח $Y$ יש לכל היותר מקור אחד מ- $X$ .

הגדרה 5 (פונקציה על)

פונקציה $f:X\to Y$ תקרא פונקציה על אם לכל איבר בטווח $Y$ יש מקור אחד לפחות ב- $X$ .

הגדרה 6 (פונקציה הפיכה)

פונקציה $f:X\to Y$ היא הפיכה אם היא חח"ע ועל.

משפט

אם קיימת $f:X\to Y$ הפיכה אזי $|X|=|Y|$ .

קבוצות

הגדרה 1 (קבוצה)

קבוצה היא אוסף של איברים שונים, ללא חשיבות לסידורם.

דוגמה

X=\left\{ 1,2,3,4 \right\}

Y=\left\{ A,B,C,D,E,F \right\}

הגדרה (סימונים)

\emptyset=\left\{ \right\}

$a \in A$ אמ"מ האיבר $a$ נמצא בקבוצה $A$ .
$Y \subseteq X$ אם כל $y \in Y$ מקיים $y \in X$ .

הגדרה 2 (גודל של קבוצה)

גודל של קבוצה $X$ יהיה מספר האיברים בה ויסומן $|X|$ .

הגדרה (וקטור/סדרה/רשימה)

נסמן קבוצה עם חשיבות לסדר עם סוגריים עגולים:

(1,2,3,4)\neq(2,1,3,4)

כמה תתי קבוצות יש ל-

\left\{ 1,2,3 \right\}

\begin{matrix} \emptyset & \left\{ 1 \right\} & \left\{ 2 \right\} & \left\{ 3 \right\} & \left\{ 1,2 \right\} & \left\{ 1,3 \right\} & \left\{ 2,3 \right\} & \left\{ 1,2,3 \right\} \end{matrix}

פעולות על קבוצות

איחוד קבוצות -

X \cup Y

- אוסף האיברים השייכים ל-

X

או ל-

Y

(או לשנייהם)

חיתוך קבוצות -

X \cap Y

- אוסף האיברים השייכים ל-

X

וגם ל-

Y

קבוצות

X,Y

יקראו זרות

X \cap Y=\emptyset \iff

הפרש של קבוצות -

X \setminus Y

מכפלה קרטזית של קבוצות - די נו, תסתכלו על מתקא.

פונקציות

הגדרה 3 (פונקציה)

פונקציה מקבוצה $X$ לקבוצה $Y$ היא התאמה המשייכת לכל איבר בקבוצה $X$ איבר יחיד בקבוצה $Y$ .

f:X\to Y

הגדרה 4 (פונקציה חח"ע)

פונקציה $f:X\to Y$ תקרא פונקציה חד חד ערכית אם לכל איבר בטווח $Y$ יש לכל היותר מקור אחד מ- $X$ .

הגדרה 5 (פונקציה על)

פונקציה $f:X\to Y$ תקרא פונקציה על אם לכל איבר בטווח $Y$ יש מקור אחד לפחות ב- $X$ .

הגדרה 6 (פונקציה הפיכה)

פונקציה $f:X\to Y$ היא הפיכה אם היא חח"ע ועל.

משפט

אם קיימת $f:X\to Y$ הפיכה אזי $|X|=|Y|$ .