diff options
Diffstat (limited to 'Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex')
-rw-r--r-- | Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex | 82 |
1 files changed, 20 insertions, 62 deletions
diff --git a/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex b/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex index 2b46dbc9407..55038a4b51f 100644 --- a/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex +++ b/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex @@ -35,18 +35,7 @@ اگر $\cal F$ مجموعهای از $n$ تابع چندجملهای با درجهی $s$ باشد. با توجه به اینکه هر دو تابع چندجملهای از درجهی $s$ حداکثر در $s$ نقطه با یکدیگر برخورد میکنند (این بدان معنی است که حداکثر $s$ تناوب از هر دو تابع مجزا از $\cal F$ در $\Gamma(\cal F)$ وجود خواهد داشت) و نیز وجود دو تابع یکسان مجاور به هم در $\Gamma(\cal F)$ هم امکان ندارد، بهراحتی میتوان نتیجه گرفت که $\Gamma(\cal F)$ متناظر با یک $(n, s)$ دنبالهی داونپورت-شینزل است و پیچیدگی آن نیز، برابر با طول دنبالهی داونپورت-شینزل متناظر با آن خواهد شد. شکل \ref{fig-DSsequence} را ببینید. پس میتوان گفت که پیچیدگی $\Gamma(\cal F)$ از مرتبهی $O(\lambda_{s}(n))$ است. تمام نتایج بهطور مشابه برای پیچیدگی پوشش بالایی نیز برقرار است. اگر دامنهی تعریف $\Gamma(\cal F)$ در نظر گرفته شود و هر تابع چندجملهای از $\cal F$ روی قسمتی از این دامنه (یک بازه مشخص از دامنه) تعریف شود، یعنی نمودار هر تابع تکهای از نمودار آن تابع با دامنه نامحدود باشد، آنگاه پیچیدگی $ \Gamma(\cal F)$ برابر $O(\lambda_{s+2}(n))$ میشود \cite{sp-dssga-95}. برای یک ثابت $s\geq 3$، $\lambda_{s}(n)$ یک تابع ابرخطی است اما خیلی آهسته رشد میکند. در ادامه قضیهای بیان میشود که فرمولهای مربوط به محاسبه $\lambda_{s}(n)$ را بیان میکند. تابع $\alpha(n)$ به معکوس تابع آکرمان\LTRfootnote{Ackermann function} اشاره میکند \cite{sp-dssga-95}. -\endinput -\begin{theorem}\label{theo-DS-sequ} -پیچیدگی پوشش پایینی (یا بالایی) یک مجموعه از $n$ تابع چندجملهای با درجه $s$ برابر $O(\lambda_{s}(n))$ است، که $\lambda_{s}(n)$ در روابط زیر صدق میکند. -$$\begin{array}{l l l l l} -\lambda_{1}(n) = n \\ \\ -\lambda_{2}(n) = 2n - 1 \\ \\ -\lambda_{3}(n) = \Theta(n\alpha(n)) \\ \\ - \lambda_{s}(n) \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}} & $ باشد، زوج $n$اگر $\\ \\ -\lambda_{s}(n) \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}\log \alpha(n)} - & $ باشد، فرد $n$اگر $ \end{array}$$ -\end{theorem} از آن جایی که $\alpha(n)$ تابعی است که بینهایت آهسته رشد میکند (تقریبا برای مقادیر عملی و منطقاً بزرگ $n$ مقدار ثابت است)، بنابراین برای یک مقدار ثابت $s$، $\lambda_{s}(n)$ تقریبا خطی از $n$ است. %%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% @@ -110,59 +99,28 @@ $$d_{\cal G}(p, q) \leq t \cdot ||pq||.$$ هر مسیری که این شرط ر \label{obsr-angles} با انتخاب $ \phi = \arcsin \frac{\varepsilon}{2(1+\varepsilon)}$ و $\varphi = 2\arcsin \frac{\varepsilon^{2}}{4(1+\varepsilon)(2+\varepsilon)}$ دو شرط \ref{eq-rd-first} و \ref{eq-rd-sec} برقرار است. \end{observation} -\begin{proof} -قسمت اول اثبات: با توجه به مشاهدهی \ref{obsr-phi}، رابطهی -$0 < \phi < \dfrac{\pi}{6}$ برقرار است، بنابراین رابطهی -$\cos \phi \geq 1-\sin \phi$ نیز برقرار خواهد بود و شرط -\ref{eq-rd-first} به این صورت اثبات میشود: -\begin{LTR} -\begin{center} -\begin{tabular}{rll} -$\phi$ & $=$ & $\arcsin \frac{\varepsilon}{2(1 + \varepsilon)}$\\ \\ -$\sin \phi $ & $=$ & $\dfrac{\varepsilon}{2(1 + \varepsilon)}$\\ \\ -$2\sin \phi- 1$ & $=$ & $\dfrac{\varepsilon}{1 + \varepsilon} - 1$\\ \\ -$1 - 2\sin \phi$ & $=$ & $\dfrac{1}{1 + \varepsilon}$ -\end{tabular} -\end{center} -\end{LTR} -\begin{LTR} -\begin{center} -\begin{tabular}{rll} -$1- \sin \phi-\sin \phi$ & $=$ & $\dfrac{\varepsilon}{1 + \varepsilon}$\\ \\ -$\cos \phi - \sin \phi$ & $\geq$ & $\dfrac{1}{1 + \varepsilon}.$ -\end{tabular} -\end{center} -\end{LTR} -قسمت دوم اثبات: از مشاهدهی \ref{obsr-phi}، رابطهی -\mbox{$\dfrac{1}{2} < \cos(\phi/2) < 1$} و از قسمت اول اثبات، -رابطهی $\sin \phi = \dfrac{\varepsilon}{2(1 + \varepsilon)}$ -برقرار است. با توجه به این روابط و نیز رابطهی مثلثاتی \linebreak $\sin \phi = 2\sin(\phi/2) \cos(\phi/2)$، شرط \ref{eq-rd-sec} به این صورت اثبات میشود: -\begin{center} -\begin{LTR} -\begin{tabular}{rll} -$\varphi$ & $=$ & $2\arcsin \frac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\ \\ -$\sin(\varphi/2)$ & $=$ & $\dfrac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\ \\ -$\sin(\varphi/2)\cos(\phi/2)$ & $\leq$ & $\dfrac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\ \\ -$\dfrac{1}{\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{4(\varepsilon + 2)(1 + \varepsilon)}{\varepsilon^{2}}$ \\ \\ -$\dfrac{\dfrac{\varepsilon}{2(1 + \varepsilon)}}{\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{2(\varepsilon + 2)}{\varepsilon}$ \\ \\ -$\dfrac{\sin\phi}{2\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{\varepsilon + 2}{\varepsilon}$ \\ \\ -$\dfrac{\sin(\phi/2)}{\sin(\varphi/2)}$ & $\geq$ & $1 + 2/\varepsilon.$ -\end{tabular} -\end{LTR} -\end{center} -\end{proof} +مشتق\index{مشتق} تابع $f$، تابعی است که با علامت $f'$ نشان داده میشود و مقدار آن در هر عدد $x$ واقع در دامنهٔ $f$ +به صورت +\begin{align}\label{bderi1} +f'(x)=\lim_{\Delta x\rightarrow 0}\dfrac{f(x+\Delta x) - f(x)}{\Delta x} +\end{align} +\ysymbol{$f'(x)$}{مشتق تابع $f$ در نقطهٔ $x$} +تعریف میشود؛ به شرطی که حد فوق وجود داشته باشد. -\begin{lemma} -پیچیدگی پوشش پایینی (یا بالایی) یک مجموعه از $n$ تابع چندجملهای با درجه $s$ برابر $O(\lambda_{s}(n))$ است، که $\lambda_{s}(n)$ در روابط زیر صدق میکند. +اگر $f$ روی بازهٔ $[a,b]$ هموار باشد، طول منحنی $y=f(x)$ از $a$ تا $b$ برابر است با +\begin{align}\label{10eq6} +L=\int_a^b \sqrt{1+\Big(\dfrac{dy}{dx}\Big)^2}dx=\int_a^b \sqrt{1+(f'(x))^2}dx. +\ysymbol{$L$}{طول منحنی} +\end{align} -$$\begin{array}{l l l l l} -\lambda_{1}(n) = n \\ \\ -\lambda_{2}(n) = 2n - 1 \\ \\ -\lambda_{3}(n) = \Theta(n\alpha(n)) \\ \\ - \lambda_{s}(n) \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}} & $ باشد، زوج $n$اگر $\\ \\ -\lambda_{s}(n) \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}\log \alpha(n)} - & $ باشد، فرد $n$اگر $ \end{array}$$ -\end{lemma} +اگر تابع $f$ در $x_1$ تعریف شده باشد، آنگاه مشتق راست $f$ در $x_1$ با $f'_{+}(x_1)$ +\ysymbol{$f'_{+}(x)$}{مشتق راست $f$ در نقطهٔ $x$} +نشان داده میشود و به صورت +\begin{align} +f'_{+}(x_1)=\lim_{\Delta x\rightarrow 0^{+}}\dfrac{f(x_1+\Delta x) - f(x_1)}{\Delta x} +\end{align} +و یا به عبارت دیگر، +تعریف میشود؛ به شرطی که این حدود موجود باشند. \begin{example} نمونه مثال |