%latex2e declaration
\documentclass[12pt]{article}
\usepackage[cp862]{inputenc}
\usepackage[hebrew]{babel}
\usepackage{tcourse}

\newcommand{\fiber}{\ast}
\newcommand{\capacity}{{\sf c}}
\newcommand{\period}{{\sf p}}

\begin{document}
\sethebrew
\courseSlogan{קידוד במערכות איחסון מידע - אביב תשס''א}
\exerciseNumberAndDate{1}{18/4/2001}

\ques{} יהיו $G_1, G_2$ שני גרפים ויהי $G_1 \fiber G_2$ גרף מכפלת התוויות של $G_1$ ו-$G_2$.\ הוכח כי
\[.S(G_1 \fiber  G_2) = S(G_1) \cap S(G_2)\]
\ques{} יהי $G=(V,E,L)$
כיסוי \L{Shannon} של שפה אי-פריקה $S=S(G)$ ויהי $H$ הגרף המתקבל מהשמטת
הצמתים מהצורה $(v,v)$, $v \in V$, מגרף מכפלת התוויות $G*G$.
\begin{enumerate}
\item הוכח כי אם $S$ הינה בעלת זיכרון סופי, כי אז
הזיכרון של $S$ שווה לזיכרון של $G$.
\item הוכח כי $S$ הינה בעלת זיכרון סופי אם ורק אם $H$ איננו מכיל מעגלים.
\item הוכח כי אם $S$ הינה בעלת זיכרון סופי, כי אז זכרון זה חסום מלמעלה על-ידי
$|V|(|V|-1)/2$.
\item נסח אלגוריתם יעיל למציאת הזיכרון של $S=S(G)$.
\end{enumerate}

\ques{} יהי $G=(V,E,L)$ גרף ותהי $S=S(G)$ השפה המיוצרת על-ידי $G$.
הוכח,
מהגדרת הקיבול, כי לכל $l$ טבעי, \[.\capacity(S^l) = l\cdot \capacity(S)\]
{\bf הדרכה}: השתמש בשלד הוכחה להלן )עליך לנמק נכונות של כל צעד בהוכחה(:

\noindent
יהי $\Sigma$ הא''ב של $S$ ותהי $S_0 = S(G_0)$ השפה המיוצרת ע''י רכיב אי-פריק
$G_0$ של $G$ אשר מקיימת $\capacity(S) = \capacity(S_0)$ )מדוע $S_0$ כזאת קיימת?(.
\newpage
\noindent
תהי $\ell_1 < \ell_2 < \cdots <  \ell_i < \cdots$ סדרת אורכים אשר מקיימים
\begin{equation}
\lim_{i \rightarrow \infty}
\frac{1}{\ell_i} \log_2 |S_0 \cap \Sigma^{\ell_i}| = \capacity(S_0)
\end{equation}
)מדוע סדרה כזאת קיימת?(. נגדיר  $m_i = \lceil \ell_i/\ell \rceil$. מתקיים
\begin{eqnarray}
\label{eq:sfirst}
\capacity(S^\ell) & \ge & \capacity(S_0^\ell) \\
                  & \ge & \limsup_{i \rightarrow \infty}
		          \frac{1}{m_i}
                          \log_2 |S_0 \cap \Sigma^{m_i \ell}| \\
                  & \ge & \limsup_{i \rightarrow \infty}
		          \frac{1}{m_i}
                          \log_2 |S_0 \cap \Sigma^{\ell_i}| \\
                  & \ge & \ell \cdot \lim_{i \rightarrow \infty}
                          \frac{\ell_i}{m_i \ell}
			  \lim_{i \rightarrow \infty}
		          \frac{1}{\ell_i}
                               \log_2 |S_0 \cap \Sigma^{\ell_i}|\\
                  & =   &  \ell \cdot \capacity(S_0) \\
\label{eq:slast}
%                  & =   &  \ell \cdot \capacity(S) \; .
                  & =  &  \ell \cdot \capacity(S) \;
\end{eqnarray}
)נמק צעדים~\L{(\ref{eq:sfirst})--(\ref{eq:slast})}. היכן בהוכחה משתמשים בעובדה
ש-$S_0$ אי-פריקה?(.
\ques{} יהי $G$
גרף אי-פריק לא טריוויאלי בעל מחזור $\period$.
הוכח כי הגרף $G^\period$ מורכב מ-$\period$
רכיבים אי-פריקים שכולם פרימיטיביים ומבודדים זה מזה.

\ques{} יהי $G$ גרף
אי-פריק לא טריוויאלי בעל מחזור $\period$ ויהי $v$ צומת ב-$G$. הראה כי $\period$ הינו
המחלק המשותף הגדול ביותר של אורכי המעגלים )הלאו-דווקא פשוטים( ב-$G$ העוברים
דרך $v$.

\ques{} יהי $G$ גרף אי-פריק לא טריוויאלי בעל מחזור $\period$, ויהיו
$G_1, G_2, \ldots, G_\period$ הרכיבים האי-פריקים של $G^\period$.
הוכח כי לכל רכיב אי-פריק
$G_i$ מתקיים: \[.\capacity(S(G_i)) = \period\cdot \capacity(S(G)) \]
\goodLuck
\end{document}
