שיטות ספירה

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

ייצוג עשרוני

מספרים עשרוניים בנויים כך שלכל עמודה במספר יש משקל פי $10$ מהעמודה מימינה. לכן נאמר שמספרים עשרוניים הם בבסיס $10$ . נכתוב מספרים עם הייצוג לבסיס שלהם כך: $199_{10}$ הוא המספר $199$ בבסיס $10$ . לכל ספרה במספר בבסיס $10$ יש טווח של $10$ מספרים, בין $0$ ל-$9$ , לכן קיימות $10^{N}$ אפשרויות למספר עשרוני בעל $N$ ספרות.

ייצוג בינארי

ביט מייצג אחד מ-$2$ רכים אפשריים, $0$ או $1$ . צירוף כלשהו של מספר ביטים מרכיב מספר בינארי. לכל עמודה במספר בינארי יש משקל פי $2$ מהעמודה מימינה. לכל ספרה במספר בבסיס $2$ יש טווח של $2$ מספרים, $0$ או $1$ , לכן קיימות $2^{N}$ אפשרויות למספר בינארי בעל $N$ ספרות.

מעבר מבסיס $2$ ל-$10$

נכפיל כל ספרה במשקל שלה ונחבר. משקל הספרה הכי שמאלית הוא הבסיס בחזקת אפס, משקל הספרה משמאלה הוא הבסיס בחזקת $1$ , וכך הלאה עד שהגענו לספרה הכי ימנית.

$$1101110_{2}=1\cdot2^{6}+1\cdot2^{5}+0\cdot2^{4}+1\cdot2^{3}+1\cdot2^{2}+1\cdot2^{1}+0\cdot2^{0}=110_{10}$$

מעבר מבסיס $10$ ל-$2$

נחלק את המספר העשרוני ב-$2$ והשארית היא ספרה המתאימה לכל עמודה מימין לשמאל בייצוג הבינארי.

למשל $57_{10}$ , נחלק ב-$2$ ונקבל $28\frac{1}{2}$ לכן הספרה הכי שמאלית היא $1$ . נחלק את $28$ ב-$2$ ונקבל $14$ בלי שארית, לכן הספרה אחרי $1$ היא $0$ . נחלק את $14$ ונקבל $7$ , לכן הספרה הבאה היא $0$ . נחלק את $7$ ונקבל $3\frac{1}{2}$ לכן הספרה הבאה היא $1$ . נחלק את $3$ ונקבל $1\frac{1}{2}$ , ולכן הספרה הבאה היא $1$ . נחלק את $1$ ב-$2$ ונקבל שהספרה האחרונה היא $1$ . סך הכל קיבלנו שהייצוג הבינארי של $57_{10}$ הוא $111001_{2}$ .

ייצוג הקסדצימלי

מספרים בינאריים נוטים להיות ארוכים, כמו בדוגמא האחרונה מספר דו-סיפרתי בבסיס $10$ הופך למספר בעל $6$ ספרות בבסיס $2$ , $57_{10}=111001_{2}$ . קבוצה של $4$ ביטים מייצגת אחת מ-$2^{4}=16$ אפשרויות. לכן לפעמים יותר נוח לעבוד בבסיס $16$ .

מספרים הקסדצימליים משתמשים בספרות $0$ עד $9$ ובנוסף באותיות $\text{A}$ עד $\text{F}$ . בדומה לבסיסים הקודמים לכל עמודה יש משקל פי $16$ מהעמודה מימינה.

מעבר מבסיס $16$ ל-$2$

מעבר בין הבסיסים הוא יחסית פשוט משום שכל ספרה במספר הקסדצימלי מתאימה ל-$4$ ספרות בינאריות. $$\begin{eqnarray*} 4_{16} & = & 0100_{2}\\ \text{C}_{16} & = & 1100_{2}\\ 4\text{C}_{16} & = & 01001100_{2} \end{eqnarray*}$$

הקסדצימלי	עשרוני	בינארי
$0$	$0$	$0000$
$1$	$1$	$0001$
$2$	$2$	$0010$
$3$	$3$	$0011$
$4$	$4$	$0100$
$5$	$5$	$0101$
$6$	$6$	$0110$
$7$	$7$	$0111$
$8$	$8$	$1000$
$9$	$9$	$1001$
$\text{A}$	$10$	$1010$
$\text{B}$	$11$	$1011$
$\text{C}$	$12$	$1100$
$\text{D}$	$13$	$1101$
$\text{E}$	$14$	$1110$
$\text{F}$	$15$	$1111$

מעבר בסיס כללי לבסיס $10$

השיטה שהראינו למעבר מבסיס $2$ ל-$10$ , עובדת עבור כל בסיס. $r$ מייצג את הבסיס ו-$a_{i}$ מייצג ספרה $i$ .

$$\left(a_{n}a_{n-1}\dots a_{1}a_{0}\right)_{r}=a_{n}r^{n}+a_{n-1}r^{n-1}+\cdots+a_{1}r^{1}+a_{0}r^{0}$$

מספרים ממשיים

באופן דומה נוכל להעביר כל מספר עשרוני בבסיס כלשהו לבסיס $10$ , רק שעבור ספרות אחרי הנקודה החזקה יורדת מימין לשמאל.

$$\left(a_{n}\dots a_{0}.b_{-1}\ldots b_{-n}\right)_{r}=a_{n}r^{n}+\cdots+a_{0}r^{0}+b_{-1}r^{-1}+\cdots b_{-n}r^{-n}$$

$$\begin{eqnarray*} 537.4_{6} & = & 5\cdot6^{2}+3\cdot6^{1}+7\cdot6^{0}+4\cdot6^{-1}=\left(205\frac{2}{3}\right)_{10} \end{eqnarray*}$$

חיבור בינארי

חיבור בינארי הוא בדיוק כמו החיבור הרגיל שאנחנו מכירים רק שאנחנו עוברים במרחב בעל $2$ מספרים, $1$ ו-$0$ . $$\begin{eqnarray*} 0+0 & = & 0\\ 1+0 & = & 1\\ 0+1 & = & 1\\ 1+1 & = & 10_{2} \end{eqnarray*}$$

מספרים יותר מורכבים: $$\begin{array}{ccc} \begin{array}{c@{\,}c@{\,}c@{\,}c@{\,}c} & {\scriptstyle 1} & {\scriptstyle 1} & {\scriptstyle 1}\\ & 0 & 1 & 0 & 1\\ + & 0 & 1 & 1 & 1\\ \hline & 1 & 1 & 0 & 0\\ \\ \end{array} & \qquad & \begin{array}{cc@{\,}c@{\,}c@{\,}c@{\,}c} & {\scriptstyle 1} & {\scriptstyle 1} & {\scriptstyle 1} & {\scriptstyle 1}\\ & & 1 & 1 & 0 & 1\\ + & & 0 & 0 & 1 & 1\\ \hline & 1 & 0 & 0 & 0 & 0\\ \\ \end{array}\end{array}$$

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

מערכות דיגיטליות עובדות עם מספר קבוע של ביטים ולכן יכול להיווצר מצב בו חיבור שני מספרים בינאריים יתן לנו תוצאה לא נכונה. נניח שאנחנו משתמשים במערכת בעלת טווח של $4$ ביטים, נקבל $$\begin{array}{c@{\,}c@{\,}c@{\,}c@{\,}c} {\scriptstyle 1} & {\scriptstyle 1} & {\scriptstyle 1} & {\scriptstyle 1}\\ & 1 & 1 & 0 & 1\\ + & 0 & 0 & 1 & 1\\ \hline & 0 & 0 & 0 & 0\\ \\ \end{array}$$ ברור שהתוצאה לא נכונה משום ש-$13_{10}+3_{10}$ שווה ל-$16_{10}$ ולא לאפס.

מיון הכנסה - Insertion Sort

מיון הכנסה (Insertion sort) הוא אלגוריתם יעיל למיון מספר קטן של איברים.

מקור:https://en.wikipedia.org/wiki/File:Insertion-sort-example-300px.gif

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

קלט: סדרה בעלת $n$ מספרים $\left(a_{1},a_{2},\ldots,a_{n}\right)$.

פלט: סדרה בעלת $n$ מספרים $\left(a_{1}',a_{2}',\ldots,a_{n}'\right)$ כך שמתקיים $a_{1}'\le a_{2}'\le\cdots\le a_{n}'$.

מקור: https://en.wikipedia.org/wiki/File:Insertion_sort.gif

הוכחת נכונות

בתחילת כל איטרציה של לולאת ה-for, שהאינדקס שלו הוא $i$, תת-מערך $\text{num_array}\left[0:i-1\right]$ מכיל קלפים שמויינו, ושאר האיברים בתת-מערך $\text{num_array}\left[i+1:n\right]$ הם הקלפים שבאים אחרי קלף $i$ שעוד לא מויינו. ובפרט האיברים במערך $\text{num_array}\left[0:i-1\right]$ הם אותם איברים שהיו באינדקסים 0 עד $i-1$ לפני שהתחלנו למיין, נגדיר את התכונה הזאת של תת המערך $\text{num_array}\left[0:i-1\right]$ כשמורת לולאה.

שמורת לולאה:

בתחילת כל איטרציה של לולאה ה-for, תת-מערך $\text{num_array[0:i-1]}$ מורכב מאיברים שבמקור היו בתת המערך אך בסדר ממויין.

נשתמש בשמורת הלולאה כדי להוכיח את נכונות האלגוריתם. נצטרך להראות שלושה דברים:

• שמורת הלולאה נכונה לפני האיטרציה הראשונה של הלולאה:
• כאשר $i=1$, תת המערך $\text{num_array}[0:i-1]$ מורכב רק מאיבר אחד, $\text{num_array}[0]$. הוא ממויין ומכיל רק איברים מ-$\text{num_array}[0]$, ולכן שמורת הלולאה מתקיימת.
• אם שמורת הלולאה נכונה לפני איטרציה של הלולאה, אז היא נכונה גם לפני האיטרציה הבאה.
• עבור $i$ כלשהו, הלולאה מזיזה את כל האיברים באינדקס הקטן מ-$i$ צעד אחד ימינה ($+1$) עד שנמצא מקום מתאים ל-$\text{num_array}[i]$. לכן תת המערך $\text{num_array}[0:i]$ מכיל רק את האיברים המקוריים שהיו ב-$\text{num_array}[0:i]$, רק בצורה ממויינת. ולכן איטרציה של הלולאה משמרת את שמורת הלולאה.
• כאשר הלולאה מסתיימת, שמורת הלולאה נותנת לנו תכונה שימושית שעוזרת להוכיח את נכונות האלגוריתם.
• התנאי שעוצר את הלולאה הוא $i > \text{len(num_array)}$, משום שהלולאה מגדילה את $i$ ב-$1$ כל איטרציה בהכרח נגיעה ל-$i=\text{len(num_array)}+1$. לפי שמורת הלולאה תת המערך $\text{num_array}[0:i-1]$ מורכב מאיברים שבמקור היו בתת המערך אך בסדר ממויין, ולכן  $\text{num_array}[0:\text{len(num_array)}]$ מערך ממויין.

זמן ריצה

במקרה הטוב ביותר	בממוצע	במקרה הגרוע
$O(n)$	$O\left(n^{2}\right)$	$O\left(n^{2}\right)$