diff options
Diffstat (limited to '')
| -rw-r--r-- | cv/cv.md | 56 | ||||
| -rw-r--r-- | šola/ana1/teor.lyx | 4300 | ||||
| -rw-r--r-- | šola/citati.bib | 227 | ||||
| -rw-r--r-- | šola/članki/dht/.gitignore | 3 | ||||
| -rw-r--r-- | šola/članki/dht/dokument.lyx | 2306 | ||||
| -rw-r--r-- | šola/članki/dht/makefile | 13 |
6 files changed, 6882 insertions, 23 deletions
@@ -4,11 +4,12 @@ Osebni podatki * Ime: **Anton Luka Šijanec** * Status: **študent** * Bivališče: **Trzin** -* Rojstvo **2004 v Ljubljani (star 19 let)** +* Rojstvo **2004 v Ljubljani (star 20 let)** * Telefon: **+38664176345** +* XMPP: **anton@sijanec.eu** * Splet: **[http://splet.šijanec.eu.](http://splet.sijanec.eu.)** -* Pošta: `anton@šijanec.eu.` -* Vozniškega izpita **nimam** +* Elektronska pošta: `anton@šijanec.eu.` +* Vozniški izpit: **kategorija B** Šolanje ======= @@ -17,12 +18,12 @@ Osebni podatki * **Gimnazija Bežigrad**, Ljubljana: 9. 2019 - 7. 2023 * **Osnovna šola Trzin**: 9. 2010 - 6. 2019 -Izkušnje -======== +Delovne izkušnje +================ * Študentsko delo: - Pri SAZU popravil odjemni del sistema za zaznavanje napak na DAT kasetah -* Tehnik za luč v Klubu Gromka: začetek 9. 2022 +* Tehnik za osvetlitev odra v Klubu Gromka: 2022 - 2023 Jezikovno znanje ================ @@ -36,43 +37,52 @@ Področja znanja Formalne izobrazbe na naštetih področjih nimam. -* Umetniška tehnika - - **Odrska osvetlitev** s protokolom DMX512 in programom QLC+ - - Osnovne **izkušnje obdelave zvoka v živo** na mešalkah Behringer X32 in PreSonus StudioLive 32SX - - Osnove fotografije in videosnemanja * Računalništvo - - **Programiranje**: programski jeziki **C**, **PHP**, **JS**, **Py**, C++ + - **Programiranje**: programski jeziki C, PHP, Javascript, Python, C++, Java - Delo s podatkovnimi zbirkami tipa SQL: mysql, sqlite3, poznavanje ORM (sqlalchemy) - - Osnovno znanje **realtime zvoka** na posixaških sistemih: libsoundio - - Dobro poznavanje internetnih protokolov in Linux userlanda: - + **Pretakanje zvoka** (icecast2) - + **OSC** (uporabljam za nastavitev luči pred koncerti) - + **ArtNet** (uporabil za izdelavo DMX512 vmesnika za upravljanje luči) - + **OBS**+**RTSP** na nginx + - Razvoj spletnih tehnologij, mobilnih/spletnih aplikacij: HTML5, PWA + + uporabljal sem knjižnico libwebsockets + - Razvoj "cross-platform native" aplikacij: znam osnove GTK+ + - Osnovno znanje **realtime zvoka** na posixaških sistemih: libsoundio, libav (ffmpeg) - **Administracija Linux strežnikov** -- osebni strežnik: + Elektronska pošta (postfix/dovecot) in seznami (mailman3) + HTTP (nginx) - + Imenski strežnik (bind9, powerdns) + + Imenski strežnik/DNS (bind9, powerdns) + Osnove uporabe git ([http://ni.šijanec.eu.](http://ni.sijanec.eu.)) + CI/CD (jenkins) + + Lokalna in navidezna omrežja (iptables, wireguard) - Postavitev in **administracija omrežij** z linux usmerjevalniki - Dobro poznavanje področja **informacijske varnosti**; našel in obvestil več družb s 50.000+ uporabniki o kritičnih varnostnih napakah - - **Vgrajeno računalništvo** ("IoT"): programiranje ESP8266 s programjem platformio - - Poznavanje spletnih protokolov, recimo uporabljal sem knjižnico libwebsockets za delo z websockets protokolom v C - - Osnove uporabe LaTeX in LyX + - **Vgrajeno računalništvo** ("IoT"): programiranje ESP8266 in ESP32 s programjem platformio + - Osnove postavljanja dokumentov z LaTeX in LyX + - Dobro poznavanje internetnih protokolov in Linux userlanda: + + **Pretakanje zvoka** (icecast2) + + **ArtNet**, **OSC** (uporabil za izdelavo DMX512 vmesnika za upravljanje luči) + + **OBS**+**RTSP** na nginx + + Osnovno poznavanje delovanja delovanja IEEE 802.11 protokolov (Wi-Fi) +* Umetniška tehnika + - **Odrska osvetlitev** s protokolom DMX512 in programom QLC+ + - Osnovne **izkušnje obdelave zvoka v živo** na mešalkah Behringer X32 in PreSonus StudioLive 32SX + - Osnove fotografije in videosnemanja Tekmovanja ========== * 2023-10: Udeležil sem se tekmovanja [ECSC](http://ecsc.no) na Norveškem v slovenski reprezentanci. -* Enkrat prvo in enkrat drugo mesto na [računalniškem tekmovanju ACM](http://rtk.ijs.si) ter srebrno priznanje na tekmovanju ZOTKS +* Enkrat prvo in enkrat drugo mesto na [računalniškem tekmovanju ACM](http://rtk.ijs.si) ter srebrno priznanje na računalniškem tekmovanju ZOTKS Raziskovalno delo ================= -* [Pridobivanje podatkov iz omrežja DHT, 2023](https://plus.cobiss.net/cobiss/si/sl/bib/163807491) -- COBISS.SI ID 163807491 +* [Pridobivanje podatkov iz omrežja DHT, 2023](https://plus.cobiss.net/cobiss/si/sl/bib/163807491) -- COBISS.SI ID 163807491 pdf: <http://splet.sijanec.eu./dir/kon%C4%8Dna.pdf> Hobiji ====== Poleg zgoraj naštetega sem od 5. 2022 radioamater in član Radiokluba Triglav. + +Meta +==== + +* Življenjepis nazadnje spremenjen 2024-07-05 +* Aktualna različica: <http://upload.sijanec.eu./d/cv.pdf> diff --git a/šola/ana1/teor.lyx b/šola/ana1/teor.lyx new file mode 100644 index 0000000..6ff52cd --- /dev/null +++ b/šola/ana1/teor.lyx @@ -0,0 +1,4300 @@ +#LyX 2.4 created this file. For more info see https://www.lyx.org/ +\lyxformat 620 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass article +\begin_preamble +\usepackage{hyperref} +\usepackage{siunitx} +\usepackage{pgfplots} +\usepackage{listings} +\usepackage{multicol} +\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}} +\usepackage{amsmath} +\usepackage{tikz} +\newcommand{\udensdash}[1]{% + \tikz[baseline=(todotted.base)]{ + \node[inner sep=1pt,outer sep=0pt] (todotted) {#1}; + \draw[densely dashed] (todotted.south west) -- (todotted.south east); + }% +}% +\DeclareMathOperator{\Lin}{\mathcal Lin} +\DeclareMathOperator{\rang}{rang} +\DeclareMathOperator{\sled}{sled} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\red}{red} +\DeclareMathOperator{\karakteristika}{char} +\DeclareMathOperator{\Ker}{Ker} +\DeclareMathOperator{\Slika}{Ker} +\DeclareMathOperator{\sgn}{sgn} +\DeclareMathOperator{\End}{End} +\DeclareMathOperator{\n}{n} +\DeclareMathOperator{\Col}{Col} +\usepackage{algorithm,algpseudocode} +\providecommand{\corollaryname}{Posledica} +\usepackage[slovenian=quotes]{csquotes} +\end_preamble +\use_default_options true +\begin_modules +enumitem +theorems-ams +theorems-ams-extended +\end_modules +\maintain_unincluded_children no +\language slovene +\language_package default +\inputencoding auto-legacy +\fontencoding auto +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_roman_osf false +\font_sans_osf false +\font_typewriter_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\float_placement class +\float_alignment class +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry true +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification false +\use_refstyle 1 +\use_formatted_ref 0 +\use_minted 0 +\use_lineno 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\leftmargin 2cm +\topmargin 2cm +\rightmargin 2cm +\bottommargin 2cm +\headheight 2cm +\headsep 2cm +\footskip 1cm +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style german +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tablestyle default +\tracking_changes false +\output_changes false +\change_bars false +\postpone_fragile_content false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\docbook_table_output 0 +\docbook_mathml_prefix 1 +\end_header + +\begin_body + +\begin_layout Title +Teorija Analize 1 — + IŠRM 2023/24 +\end_layout + +\begin_layout Author + +\noun on +Anton Luka Šijanec +\end_layout + +\begin_layout Date +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +today +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Abstract +Povzeto po zapiskih s predavanj profesorja Oliverja Dragičevića. +\end_layout + +\begin_layout Standard +\begin_inset CommandInset toc +LatexCommand tableofcontents + +\end_inset + + +\end_layout + +\begin_layout Section +Števila +\end_layout + +\begin_layout Definition* +Množica je matematični objekt, + ki predstavlja skupino elementov. + Če element +\begin_inset Formula $a$ +\end_inset + + pripada množici +\begin_inset Formula $A$ +\end_inset + +, + pišemo +\begin_inset Formula $a\in A$ +\end_inset + +, + sicer pa +\begin_inset Formula $a\not\in A$ +\end_inset + +. + Množica +\begin_inset Formula $B$ +\end_inset + + je podmnožica množice +\begin_inset Formula $A$ +\end_inset + +, + pišemo +\begin_inset Formula $B\subset A$ +\end_inset + +, + če +\begin_inset Formula $\forall b\in B:b\in A$ +\end_inset + +. + Presek +\begin_inset Formula $B$ +\end_inset + + in +\begin_inset Formula $C$ +\end_inset + + označimo +\begin_inset Formula $B\cap C\coloneqq\left\{ x;x\in B\wedge x\in C\right\} $ +\end_inset + +. + Unijo +\begin_inset Formula $B$ +\end_inset + + in +\begin_inset Formula $C$ +\end_inset + + označimo +\begin_inset Formula $B\cup C\coloneqq\left\{ x;x\in B\vee x\in C\right\} $ +\end_inset + +. + Razliko/komplement +\begin_inset Quotes gld +\end_inset + + +\begin_inset Formula $B$ +\end_inset + + manj/brez +\begin_inset Formula $C$ +\end_inset + + +\begin_inset Quotes grd +\end_inset + + označimo +\begin_inset Formula $B\setminus C\coloneqq\left\{ x;x\in B\wedge x\not\in C\right\} $ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Realna števila +\end_layout + +\begin_layout Standard +Množico realnih števil označimo +\begin_inset Formula $\mathbb{R}$ +\end_inset + +. + V njej obstajata binarni operaciji seštevanje +\begin_inset Formula $a+b$ +\end_inset + + in množenje +\begin_inset Formula $a\cdot b$ +\end_inset + +. +\end_layout + +\begin_layout Subsubsection +Lastnosti seštevanja +\end_layout + +\begin_layout Axiom +Komutativnost: + +\begin_inset Formula $\forall a,b\in\mathbb{R}:a+b=b+a$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Asociativnost: + +\begin_inset Formula $\forall a,b,c\in\mathbb{R}:a+\left(b+c\right)=\left(a+b\right)+c$ +\end_inset + +, + torej je +\begin_inset Formula $a+\cdots+z$ +\end_inset + + dobro definiran izraz. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Obstoj enote: + +\begin_inset Formula $\exists0\in\mathbb{R}\forall a\in\mathbb{R}:a+0=a$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Obstoj inverzov: + +\begin_inset Formula $\forall a\in\mathbb{R}\exists b\in\mathbb{R}\ni a+b=0$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Claim* +Inverz je enoličen. +\end_layout + +\begin_layout Proof +Naj bo +\begin_inset Formula $a,b,c\in\mathbb{R}$ +\end_inset + + in +\begin_inset Formula $a+b=0$ +\end_inset + + in +\begin_inset Formula $a+c=0$ +\end_inset + +. + Tedaj +\begin_inset Formula $b=b+0=b+a+c=0+c=c$ +\end_inset + +. +\end_layout + +\begin_layout Corollary* +Inverz je funkcija in aditivni inverz +\begin_inset Formula $a$ +\end_inset + + označimo z +\begin_inset Formula $-a$ +\end_inset + +. + Pri zapisu +\begin_inset Formula $a+\left(-b\right)$ +\end_inset + + običajno +\begin_inset Formula $+$ +\end_inset + + izpustimo in pišemo +\begin_inset Formula $a-b$ +\end_inset + +, + čemur pravimo odštevanje +\begin_inset Formula $b$ +\end_inset + + od +\begin_inset Formula $a$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $\forall a\in\mathbb{R}:a=-\left(-a\right)$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Naj bo +\begin_inset Formula $b=-a$ +\end_inset + + in +\begin_inset Formula $c=-b=-\left(-a\right)$ +\end_inset + +. + Tedaj velja +\begin_inset Formula $c-a=c+b=-\left(-a\right)-a=0$ +\end_inset + + in +\begin_inset Formula $a=0+a=c-a+a=c+\left(-a\right)+a=c+0=c=-\left(-a\right)$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $-\left(b+c\right)=-b-c$ +\end_inset + + +\end_layout + +\begin_layout Proof +Velja +\begin_inset Formula $b+c+\left(-b-c\right)=b+c+\left(\left(-b\right)+\left(-c\right)\right)=b+\left(-b\right)+c+\left(-c\right)=0$ +\end_inset + +, + torej je +\begin_inset Formula $b+c$ +\end_inset + + inverz od +\begin_inset Formula $\left(-b-c\right)$ +\end_inset + +, + torej je +\begin_inset Formula $-\left(b+c\right)=-b-c$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Subsubsection +Lastnosti množenja +\end_layout + +\begin_layout Axiom +Komutativnost: + +\begin_inset Formula $\forall a,b\in\mathbb{R}:ab=ba$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Asociativnost: + +\begin_inset Formula $\forall a,b,c\in\mathbb{R}:a\left(bc\right)=\left(ab\right)c$ +\end_inset + +, + torej je +\begin_inset Formula $a\cdots z$ +\end_inset + + dobro definiran izraz. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Obstoj enote: + +\begin_inset Formula $\exists1\in\mathbb{R}\forall a\in\mathbb{R}:a1=a$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Obstoj inverzov: + +\begin_inset Formula $\forall a\in\mathbb{R}\setminus\left\{ 0\right\} \exists b\in\mathbb{R}\setminus\left\{ 0\right\} \ni:ab=1$ +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Claim* +Inverz je enoličen. +\end_layout + +\begin_layout Proof +Naj bo +\begin_inset Formula $a,b,c\in\mathbb{R}\setminus\left\{ 0\right\} $ +\end_inset + + in +\begin_inset Formula $ab=1$ +\end_inset + + in +\begin_inset Formula $ac=1$ +\end_inset + +. + Tedaj +\begin_inset Formula $b=b1=bac=1c=c$ +\end_inset + +. +\end_layout + +\begin_layout Corollary* +Inverz je funkcija in multiplikativni inverz +\begin_inset Formula $a$ +\end_inset + + označimo z +\begin_inset Formula $a^{-1}$ +\end_inset + +. + Pri zapisu +\begin_inset Formula $a\cdot b^{-1}$ +\end_inset + + lahko +\begin_inset Formula $\cdot$ +\end_inset + + izpustimo in pišemo +\begin_inset Formula $a/b$ +\end_inset + +, + čemur pravimo deljenje +\begin_inset Formula $a$ +\end_inset + + z +\begin_inset Formula $b$ +\end_inset + + za neničeln +\begin_inset Formula $b$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Subsubsection +Skupne lastnosti v +\begin_inset Formula $\mathbb{R}$ +\end_inset + + +\end_layout + +\begin_layout Axiom +\begin_inset Formula $1\not=0$ +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Axiom +Distributivnost: + +\begin_inset Formula $\forall a,b,c\in\mathbb{R}:\left(a+b\right)c=ac+bc$ +\end_inset + + +\end_layout + +\begin_layout Paragraph +Urejenost +\begin_inset Formula $\mathbb{R}$ +\end_inset + + +\end_layout + +\begin_layout Standard +Realna števila delimo na pozitivna +\begin_inset Formula $\mathbb{R}_{+}\coloneqq\left\{ x\in\mathbb{R};x>0\right\} $ +\end_inset + +, + negativna +\begin_inset Formula $\mathbb{R}_{-}\coloneqq\left\{ x\in\mathbb{R};x<0\right\} $ +\end_inset + + in ničlo +\begin_inset Formula $0$ +\end_inset + +. + Če je +\begin_inset Formula $x\in\mathbb{\mathbb{R}}_{+}\cup\left\{ 0\right\} $ +\end_inset + +, + pišemo +\begin_inset Formula $x\geq0$ +\end_inset + +, + če je +\begin_inset Formula $x\in\mathbb{R}_{-}\cup\left\{ 0\right\} $ +\end_inset + +, + pišemo +\begin_inset Formula $x\leq0$ +\end_inset + +. +\end_layout + +\begin_layout Axiom +Če je +\begin_inset Formula $a\not=0$ +\end_inset + +, + je natanko eno izmed +\begin_inset Formula $\left\{ a,-a\right\} $ +\end_inset + + pozitivno, + imenujemo ga absolutna vrednost +\begin_inset Formula $a$ +\end_inset + + (pišemo +\begin_inset Formula $\left|a\right|$ +\end_inset + +), + in natanko eno negativno, + pišemo +\begin_inset Formula $-\left|a\right|$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +\begin_inset Formula $\left|0\right|=0$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +Za +\begin_inset Formula $a,b\in\mathbb{R}$ +\end_inset + + se +\begin_inset Formula $\left|a-b\right|$ +\end_inset + + imenuje razdalja. +\end_layout + +\begin_layout Axiom +\begin_inset Formula $\forall a,b\in\mathbb{R}:a,b>0\Rightarrow\left(a+b>0\right)\wedge\left(ab>0\right)$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +Za +\begin_inset Formula $a,b\in\mathbb{R}$ +\end_inset + +: + +\begin_inset Formula $a$ +\end_inset + + je večje od +\begin_inset Formula $b$ +\end_inset + +, + oznaka +\begin_inset Formula $a>b\Leftrightarrow a-b>0$ +\end_inset + +. + +\begin_inset Formula $a$ +\end_inset + + je manjše od +\begin_inset Formula $b$ +\end_inset + +, + oznaka +\begin_inset Formula $a<b\Leftrightarrow a-b<0$ +\end_inset + +. + Podobno +\begin_inset Formula $\leq$ +\end_inset + + in +\begin_inset Formula $\geq$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +Trikotniška neenakost. + +\begin_inset Formula $\forall a,b\in\mathbb{R}$ +\end_inset + +: + +\begin_inset Formula $\left|\left|a\right|-\left|b\right|\right|\leq\left|a+b\right|\leq\left|a\right|+\left|b\right|$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Dokažimo desni neenačaj. + Vemo +\begin_inset Formula $ab\leq\left|ab\right|$ +\end_inset + + in +\begin_inset Formula $\left|a\right|=\sqrt{a^{2}}$ +\end_inset + +. + Naj bo +\begin_inset Formula $a^{2}+2ab+b^{2}\leq\left|a\right|^{2}+2\left|a\right|\left|b\right|+\left|b\right|^{2}$ +\end_inset + +, + torej +\begin_inset Formula $\left(a+b\right)^{2}\leq\left(\left|a\right|+\left|b\right|\right)^{2}$ +\end_inset + +, + korenimo: + +\begin_inset Formula $\left|a+b\right|\leq\left|a\right|+\left|b\right|$ +\end_inset + +. +\end_layout + +\begin_layout Subsubsection +Intervali +\end_layout + +\begin_layout Definition* +Naj bo +\begin_inset Formula $a<b$ +\end_inset + +. + Označimo odprti interval +\begin_inset Formula $\left(a,b\right)\coloneqq\left\{ x\in\mathbb{R};a<x<b\right\} $ +\end_inset + +, + zaprti +\begin_inset Formula $\left[a,b\right]\coloneqq\left\{ x\in\mathbb{R};a\leq x\leq b\right\} $ +\end_inset + +, + polodprti +\begin_inset Formula $(a,b]\coloneqq\left\{ x\in\mathbb{R};a<x\leq b\right\} $ +\end_inset + + in podobno +\begin_inset Formula $[a,b)$ +\end_inset + +. + +\begin_inset Formula $\left(a,\infty\right)\coloneqq\left\{ x\in\mathbb{R};x>a\right\} $ +\end_inset + + in podobno +\begin_inset Formula $[a,\infty)$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Temeljne številske podmnožice +\end_layout + +\begin_layout Subsubsection +Naravna števila +\begin_inset Formula $\mathbb{N}$ +\end_inset + + +\end_layout + +\begin_layout Definition* +\begin_inset Formula $\mathbb{N}\coloneqq\left\{ 1,1+1,1+1+1,1+1+1+1,\dots\right\} $ +\end_inset + + +\end_layout + +\begin_layout Paragraph +Matematična indukcija +\end_layout + +\begin_layout Standard +Če je +\begin_inset Formula $A\subseteq\mathbb{N}$ +\end_inset + + in velja +\begin_inset Formula $1\in A$ +\end_inset + + (baza) in +\begin_inset Formula $a\in A\Rightarrow a+1\in A$ +\end_inset + + (korak), + tedaj +\begin_inset Formula $A=\mathbb{N}$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $1+2+3+\cdots+n=\frac{n\left(n+1\right)}{2}$ +\end_inset + +. +\end_layout + +\begin_layout Proof +\begin_inset Formula $A\coloneqq\left\{ n\in\mathbb{N};\text{velja trditev za }n\right\} $ +\end_inset + +. + Dokažimo +\begin_inset Formula $A=\mathbb{N}$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Itemize +Baza: + +\begin_inset Formula $1=\frac{1\cdot2}{2}=1$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +Korak: + Predpostavimo +\begin_inset Formula $1+2+3+\cdots+n=\frac{n\left(n+1\right)}{2}$ +\end_inset + +. + Prištejmo +\begin_inset Formula $n+1$ +\end_inset + +: + +\begin_inset Formula +\[ +1+2+3+\cdots+n+\left(n+1\right)=\frac{n\left(n+1\right)}{2}+\left(n+1\right)=\frac{n\left(n+1\right)}{2}+\frac{2\left(n+1\right)}{2}=\frac{\left(n+2\right)\left(n+1\right)}{2} +\] + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Subsubsection +Cela števila +\begin_inset Formula $\mathbb{Z}$ +\end_inset + + +\end_layout + +\begin_layout Standard +Množica +\begin_inset Formula $\mathbb{N}$ +\end_inset + + je zaprta za seštevanje in množenje, + torej +\begin_inset Formula $\forall a,b\in\mathbb{N}:a+b\in\mathbb{N}\wedge ab\in\mathbb{N}$ +\end_inset + +, + ni pa zaprta za odštevanje, + ker recimo +\begin_inset Formula $5-3\not\in\mathbb{N}$ +\end_inset + +. + Zapremo jo za odštevanje in dobimo množico +\begin_inset Formula $\mathbb{Z}$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +\begin_inset Formula $\mathbb{Z}\coloneqq\left\{ a-b;b,a\in\mathbb{N}\right\} $ +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Racionalna števila +\begin_inset Formula $\mathbb{Q}$ +\end_inset + + +\end_layout + +\begin_layout Standard +Najmanjša podmnožica +\begin_inset Formula $\mathbb{R}$ +\end_inset + +, + ki vsebuje +\begin_inset Formula $\mathbb{Z}$ +\end_inset + + in je zaprta za deljenje, + je +\begin_inset Formula $\mathbb{Q}$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +\begin_inset Formula $\mathbb{Q}\coloneqq\left\{ a/b;a\in\mathbb{Z},b\in\mathbb{Z}\setminus\left\{ 0\right\} \right\} $ +\end_inset + +. +\end_layout + +\begin_layout Standard +Velja +\begin_inset Formula $\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +Za +\begin_inset Formula $a\in\mathbb{Q}$ +\end_inset + +, + +\begin_inset Formula $b\not\in\mathbb{Q}$ +\end_inset + + velja +\begin_inset Formula $a+b\not\in\mathbb{Q}$ +\end_inset + + in +\begin_inset Formula $a\not=0\Rightarrow ab\not\in\mathbb{Q}$ +\end_inset + +. +\end_layout + +\begin_layout Proof +PDDRAA +\begin_inset Formula $a+b\in\mathbb{Q}$ +\end_inset + +. + Tedaj +\begin_inset Formula $a+b-a\in\mathbb{Q}$ +\end_inset + +, + tedaj +\begin_inset Formula $b\in\mathbb{Q}$ +\end_inset + +, + kar je +\begin_inset Formula $\rightarrow\!\leftarrow$ +\end_inset + +. + PDDRAA +\begin_inset Formula $ab\in\mathbb{Q}$ +\end_inset + +. + Tedaj +\begin_inset Formula $\frac{ab}{a}\in\mathbb{Q}$ +\end_inset + +, + tedaj +\begin_inset Formula $b\in\mathbb{Q}$ +\end_inset + +, + kar je +\begin_inset Formula $\rightarrow\!\leftarrow$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +\begin_inset CommandInset label +LatexCommand label +name "subsec:Omejenost-množic" + +\end_inset + +Omejenost množic +\end_layout + +\begin_layout Definition* +Naj bo +\begin_inset Formula $A\subset\mathbb{R}$ +\end_inset + +. + +\begin_inset Formula $A$ +\end_inset + + je navzgor omejena +\begin_inset Formula $\Leftrightarrow\exists m\in\mathbb{R}\forall a\in A:a\leq m$ +\end_inset + +. + Takemu +\begin_inset Formula $m$ +\end_inset + + pravimo zgornja meja. + Najmanjši zgornji meji +\begin_inset Formula $A$ +\end_inset + + pravimo supremum ali natančna zgornja meja množice +\begin_inset Formula $A$ +\end_inset + +, + označimo +\begin_inset Formula $\sup A$ +\end_inset + +. + Če je zgornja meja +\begin_inset Formula $A$ +\end_inset + + ( +\begin_inset Formula $m$ +\end_inset + +) element +\begin_inset Formula $A$ +\end_inset + +, + je maksimum množice +\begin_inset Formula $A$ +\end_inset + +, + označimo +\begin_inset Formula $m=\max A$ +\end_inset + +. + Če množica ni navzgor omejena, + pišemo +\begin_inset Formula $\sup A=\infty$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Če +\begin_inset Formula $s=\sup A\in\mathbb{R}$ +\end_inset + +, + mora veljati +\begin_inset Formula $\forall a\in A:a\leq s$ +\end_inset + + in +\begin_inset Formula $\forall\varepsilon>0\exists b\in A\ni:b>s-\varepsilon$ +\end_inset + +, + torej za vsak neničeln +\begin_inset Formula $\varepsilon$ +\end_inset + + +\begin_inset Formula $s-\varepsilon$ +\end_inset + + ni več natančna zgornja meja za +\begin_inset Formula $A$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +Naj bo +\begin_inset Formula $A\subset\mathbb{R}$ +\end_inset + +. + +\begin_inset Formula $A$ +\end_inset + + je navzdol omejena +\begin_inset Formula $\Leftrightarrow\exists m\in\mathbb{R}\forall a\in A:a\geq m$ +\end_inset + +. + Takemu +\begin_inset Formula $m$ +\end_inset + + pravimo spodnja meja. + Največji spodnji meji +\begin_inset Formula $A$ +\end_inset + + pravimo infimum ali natančna spodnja meja množice +\begin_inset Formula $A$ +\end_inset + +, + označimo +\begin_inset Formula $\inf A$ +\end_inset + +. + Če je spodnja meja +\begin_inset Formula $A$ +\end_inset + + ( +\begin_inset Formula $m$ +\end_inset + +) element +\begin_inset Formula $A$ +\end_inset + +, + je minimum množice +\begin_inset Formula $A$ +\end_inset + +, + označimo +\begin_inset Formula $m=\min A$ +\end_inset + +. + Če množica ni navzdol omejena, + pišemo +\begin_inset Formula $\inf A=-\infty$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +Množica +\begin_inset Formula $A\subset\mathbb{R}$ +\end_inset + + je omejena, + če je hkrati navzgor in navzdol omejena. +\end_layout + +\begin_layout Axiom +\begin_inset CommandInset label +LatexCommand label +name "axm:Dedekind.-Vsaka-navzgor" + +\end_inset + +Dedekind. + Vsaka navzgor omejena množica v +\begin_inset Formula $\mathbb{R}$ +\end_inset + + ima natančno zgornjo mejo v +\begin_inset Formula $\mathbb{R}$ +\end_inset + +. +\end_layout + +\begin_layout Remark* +Za +\begin_inset Formula $\mathbb{Q}$ +\end_inset + + aksiom +\begin_inset CommandInset ref +LatexCommand ref +reference "axm:Dedekind.-Vsaka-navzgor" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + ne velja. + Če +\begin_inset Formula $B\subset\mathbb{Q}$ +\end_inset + +, + se lahko zgodi, + da +\begin_inset Formula $\sup B\not\in\mathbb{Q}$ +\end_inset + +. + Primer: + +\begin_inset Formula $B\coloneqq\left\{ q\in\mathbb{Q};q^{2}\leq2\right\} $ +\end_inset + +. + +\begin_inset Formula $\sup B=\sqrt{2}\not\in\mathbb{Q}$ +\end_inset + +. +\end_layout + +\begin_layout Example* + +\end_layout + +\begin_layout Subsection +Decimalni zapis +\end_layout + +\begin_layout Definition* +\begin_inset Formula $\forall x\in\mathbb{R}^{+}\exists!m\in\mathbb{N}\cup\left\{ 0\right\} ,d_{1},d_{2},\dots\in\left\{ 0..9\right\} $ +\end_inset + +, + ki število natančno določajo. + Pišemo +\begin_inset Formula $x=m,d_{1}d_{2}\dots$ +\end_inset + +. + Natančno določitev mislimo v smislu: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $m\leq x<m+1$ +\end_inset + + — + s tem se izognemo dvojnemu zapisu +\begin_inset Formula $1=0,\overline{9}$ +\end_inset + + in +\begin_inset Formula $1=1,\overline{0}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $[m,m+1)$ +\end_inset + + razdelimo na 10 enako dolgih polodprtih intervalov +\begin_inset Formula $I_{0},\dots,I_{9}$ +\end_inset + +. + +\begin_inset Formula $x$ +\end_inset + + leži na natanko enem izmed njih, + indeks njega je +\begin_inset Formula $d_{1}$ +\end_inset + +. + Nadaljujemo tako, + da +\begin_inset Formula $I_{d_{1}}$ +\end_inset + + razdelimo zopet na 10 delov itd. +\end_layout + +\end_deeper +\begin_layout Definition* +Števila +\begin_inset Formula $x\in\mathbb{R^{-}}$ +\end_inset + + pišemo tako, + da zapišemo decimalni zapis števila +\begin_inset Formula $-x$ +\end_inset + + in predenj zapišemo +\begin_inset Formula $-$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +Če se decimalke v zaporedju +\begin_inset Formula $\left(d_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + ponavljajo, + uporabimo periodični zapis, + denimo +\begin_inset Formula $5,01\overline{763}\in\mathbb{Q}$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Kompleksna števila +\end_layout + +\begin_layout Definition* +Vpeljimo število +\begin_inset Formula $i$ +\end_inset + + z lastnostjo +\begin_inset Formula $i^{2}=-1$ +\end_inset + +, + da je +\begin_inset Formula $i$ +\end_inset + + rešitev enačbe +\begin_inset Formula $x^{2}+1=0$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $i\not\in\mathbb{R}$ +\end_inset + + +\end_layout + +\begin_layout Proof +Sicer bi veljajo +\begin_inset Formula $i^{2}\geq0$ +\end_inset + +, + kar po definiciji ne velja. +\end_layout + +\begin_layout Definition* +Kompleksna števila so +\begin_inset Formula $\mathbb{C}\coloneqq\left\{ a+bi;a,b\in\mathbb{R}\right\} $ +\end_inset + +. + +\begin_inset Formula $bi$ +\end_inset + + je še nedefinirano, + zato za kompleksna števila definirano seštevanje in množenje za +\begin_inset Formula $z=a+bi$ +\end_inset + + in +\begin_inset Formula $w=c+di$ +\end_inset + +: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $z+w\coloneqq\left(a+c\right)+\left(b+d\right)i$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $zw\coloneqq\left(a+bi\right)\left(c+di\right)=ac+adi+bic+bidi=ac+adi+bic-bd=\left(ac-bd\right)+\left(ad+bc\right)i$ +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Definition* +Definiramo še konjugirano vrednost +\begin_inset Formula $z\in\mathbb{C}$ +\end_inset + +: + +\begin_inset Formula $\overline{z}\coloneqq a-bi$ +\end_inset + + in označimo +\begin_inset Formula $\left|z\right|^{2}=z\overline{z}$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $z\overline{z}=a^{2}+b^{2}\geq0$ +\end_inset + + za +\begin_inset Formula $z=a+bi$ +\end_inset + +. +\end_layout + +\begin_layout Proof +\begin_inset Formula $\left(a+bi\right)\left(a-bi\right)=a^{2}+abi-bia-bibi=a^{2}+b^{2}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Velja, + da je +\begin_inset Formula $\mathbb{R}\subset\mathbb{C}$ +\end_inset + + v smislu identifikacije +\begin_inset Formula $\mathbb{R}$ +\end_inset + + z množico +\begin_inset Formula $\mathbb{C}$ +\end_inset + +: + +\begin_inset Formula $\mathbb{R}=\left\{ a+0i;a\in\mathbb{R}\right\} $ +\end_inset + +, + torej smo +\begin_inset Formula $\mathbb{R}$ +\end_inset + + razširili v +\begin_inset Formula $\mathbb{C}$ +\end_inset + +, + kjer ima vsak polinom vedno rešitev. +\end_layout + +\begin_layout Subsubsection +Deljenje v +\begin_inset Formula $\mathbb{C}$ +\end_inset + + +\end_layout + +\begin_layout Standard +Za +\begin_inset Formula $w,z\in\mathbb{C},w\not=0$ +\end_inset + + iščemo +\begin_inset Formula $x\in\mathbb{C}\ni:wx=z$ +\end_inset + +. + Ločimo dva primera: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $w\in\mathbb{R}\setminus\left\{ 0\right\} $ +\end_inset + +: + definiramo +\begin_inset Formula $x=\frac{z}{w}\coloneqq\frac{a}{w}+\frac{b}{w}i$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $w\in\mathbb{C}\setminus\left\{ 0\right\} $ +\end_inset + + (splošno): + +\begin_inset Formula $wx=z\overset{/\cdot\overline{w}}{\Longrightarrow}w\overline{w}x=z\overline{w}\Rightarrow\left|w\right|^{2}x=z\overline{w}\Rightarrow x=\frac{z\overline{w}}{\left|w\right|^{2}}$ +\end_inset + +, + z +\begin_inset Formula $\left|w\right|^{2}$ +\end_inset + + pa znamo deliti, + ker je realen. +\end_layout + +\begin_layout Subsubsection +Lastnosti v +\begin_inset Formula $\mathbb{C}$ +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Formula $+$ +\end_inset + + in +\begin_inset Formula $\cdot$ +\end_inset + + sta komutativni, + asociativni, + distributivni, + +\begin_inset Formula $0$ +\end_inset + + je aditivna enota, + +\begin_inset Formula $1$ +\end_inset + + je multiplikativna. +\end_layout + +\begin_layout Definition* +Za +\begin_inset Formula $z=a+bi$ +\end_inset + + vpeljemo +\begin_inset Formula $\Re z=a$ +\end_inset + + in +\begin_inset Formula $\Im z=b$ +\end_inset + +. +\end_layout + +\begin_layout Remark* +Opazimo +\begin_inset Formula $\Re z=\frac{z+\overline{z}}{2}$ +\end_inset + +, + +\begin_inset Formula $\Im z=\frac{z-\overline{z}}{2}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Remark* +\begin_inset Formula $\mathbb{C}$ +\end_inset + + si lahko predstavljamo kot urejene pare; + +\begin_inset Formula $a+bi$ +\end_inset + + ustreza paru +\begin_inset Formula $\left(a,b\right)$ +\end_inset + +. + Tako +\begin_inset Formula $\mathbb{C}$ +\end_inset + + enačimo/identificiramo z +\begin_inset Formula $\mathbb{R}^{2}\coloneqq\left\{ \left(a,b\right);a,b\in\mathbb{R}\right\} $ +\end_inset + +, + s čimer dobimo geometrično predstavitev +\begin_inset Formula $\mathbb{C}$ +\end_inset + + kot vektorje v +\begin_inset Formula $\mathbb{R}^{2}$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +Za +\begin_inset Formula $z=a+bi$ +\end_inset + +, + predstavljen z vektorjem s komponentami +\begin_inset Formula $\left(a,b\right)$ +\end_inset + +, + velja +\begin_inset Formula $a=\left|z\right|\cos\varphi$ +\end_inset + + in +\begin_inset Formula $v=\left|z\right|\sin\varphi$ +\end_inset + +. + Kotu +\begin_inset Formula $\varphi$ +\end_inset + + pravimo argument kompleksnega števila +\begin_inset Formula $z$ +\end_inset + +, + oznaka +\begin_inset Formula $\arg z$ +\end_inset + +. +\end_layout + +\begin_layout Corollary* +\begin_inset Formula $z=$ +\end_inset + + +\begin_inset Formula $\left|z\right|\left(\cos\varphi+i\sin\varphi\right)$ +\end_inset + +. + Velja +\begin_inset Foot +status open + +\begin_layout Plain Layout +TODO DOPISATI ZAKAJ (v bistvu še jaz ne vem). + ne razumem. +\end_layout + +\end_inset + + +\begin_inset Formula $\left(\cos\varphi+i\sin\varphi\right)\left(\cos\psi+i\sin\psi\right)=\cos\left(\varphi+\psi\right)+i\sin\left(\varphi+\psi\right)$ +\end_inset + +, + zato lahko pišemo +\begin_inset Formula $e^{i\varphi}=\cos\varphi+i\sin\varphi$ +\end_inset + +. + Množenje kompleksnh števil +\begin_inset Formula $z=\left|z\right|e^{i\varphi}$ +\end_inset + + in +\begin_inset Formula $w=\left|w\right|e^{i\psi}$ +\end_inset + + vrne število +\begin_inset Formula $zw$ +\end_inset + +, + za katero velja: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $\left|zw\right|=\left|z\right|\left|w\right|$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\arg zw=\arg z+\arg w$ +\end_inset + + (do periode +\begin_inset Formula $2\pi$ +\end_inset + + natančno) +\end_layout + +\end_deeper +\begin_layout Section +Zaporedja +\end_layout + +\begin_layout Definition* +Funkcija +\begin_inset Formula $a:\mathbb{N}\to\mathbb{R}$ +\end_inset + + se imenuje realno zaporedje, + oznaka +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + +. + +\begin_inset Formula $a_{n}$ +\end_inset + + je funkcijska vrednost pri +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_layout Example* +\begin_inset Formula $a_{n}=n$ +\end_inset + +: + +\begin_inset Formula $1,2,3,\dots$ +\end_inset + +; + +\begin_inset Formula $a_{n}=\left(-1\right)^{n}n^{2}$ +\end_inset + +: + +\begin_inset Formula $-1,4,-9,16,-25,\dots$ +\end_inset + +; + +\begin_inset Formula $a_{n}=\cos\left(\frac{\pi}{2}n\right)=0,-1,0,1,0,-1,\dots$ +\end_inset + + +\end_layout + +\begin_layout Standard +Zaporedje lahko podamo rekurzivno. + Podamo prvi člen ali nekaj prvih členov in pravilo, + kako iz prejšnjih členov dobiti naslednje. +\end_layout + +\begin_layout Example* +\begin_inset Formula $a_{1}=0,a_{n+1}=a_{n}+n$ +\end_inset + + da zaporedje +\begin_inset Formula $a_{n}=\frac{n\left(n+1\right)}{2}$ +\end_inset + +. + +\begin_inset Formula $a_{0}=0,a_{n+1}=\sqrt{b+a_{n}}$ +\end_inset + + da zaporedje +\begin_inset Formula $0,\sqrt{b},\sqrt{b+\sqrt{b}},\sqrt{b+\sqrt{b+\sqrt{b}}},\dots$ +\end_inset + +. + Fibbonacijevo zaporedje: + +\begin_inset Formula $a_{1}=a_{2}=1,a_{n+1}=a_{n}+a_{n-1}$ +\end_inset + + da zaporedje +\begin_inset Formula $1,1,2,3,5,8,\dots$ +\end_inset + + +\end_layout + +\begin_layout Subsection +Posebni tipi zaporedij +\end_layout + +\begin_layout Definition* +Zaporedje +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + je aritmetično, + če +\begin_inset Formula $\exists k\in\mathbb{R}\forall n\in\mathbb{N}:a_{n+1}-a_{n}=k$ +\end_inset + +. + Tedaj +\begin_inset Formula $a_{n+1}=a_{n}+k=a_{1}+nd$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +Zaporedje +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + je geometrično, + če +\begin_inset Formula $\exists\lambda\in\mathbb{R}\forall n\in\mathbb{N}:a_{n+1}=a_{n}\lambda$ +\end_inset + +. + Tedaj +\begin_inset Formula $a_{n}=\lambda^{n-1}a_{1}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +Zaporedje +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + je navzdol oz. + navzgor omejeno, + če je množica vseh členov tega taporedja navzgor oz. + navzdol omejena (glej +\begin_inset CommandInset ref +LatexCommand ref +reference "subsec:Omejenost-množic" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +). + Podobno z množico členov definiramo supremum, + infimum, + maksimum in infimum zaporedja. +\end_layout + +\begin_layout Definition* +Zaporedje je naraščajoče, + če +\begin_inset Formula $\forall n\in\mathbb{N}:a_{n+1}\geq a_{n}$ +\end_inset + +, + padajoče, + če +\begin_inset Formula $\forall n\in\mathbb{N}:a_{n+1}\leq a_{n}$ +\end_inset + +, + strogo naraščajoče, + če +\begin_inset Formula $\forall n\in\mathbb{N}:a_{n+1}>a_{n}$ +\end_inset + +, + strogo padajoče podobno, + monotono, + če je naraščajoče ali padajoče in strogo monotono, + če je strogo naraščajoče ali strogo padajoče. +\end_layout + +\begin_layout Subsection +Limita zaporedja +\end_layout + +\begin_layout Definition* +Množica +\begin_inset Formula $U\subseteq\mathbb{R}$ +\end_inset + + je odprta, + če +\begin_inset Formula $\forall u\in U\exists r>0\ni:\left(u-r,u+r\right)\subseteq U$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +Množica +\begin_inset Formula $U\subseteq\mathbb{R}$ +\end_inset + + je zaprta, + če je +\begin_inset Formula $U^{\mathcal{C}}\coloneqq\mathbb{R}\setminus U$ +\end_inset + + odprta. +\end_layout + +\begin_layout Claim* +Odprt interval je odprta množica. +\end_layout + +\begin_layout Proof +Za poljubna +\begin_inset Formula $a,b\in\mathbb{R}$ +\end_inset + +, + +\begin_inset Formula $b>a$ +\end_inset + +, + naj bo +\begin_inset Formula $u\in\left(a,b\right)$ +\end_inset + + poljuben. + Ustrezen +\begin_inset Formula $r$ +\end_inset + + je +\begin_inset Formula $\min\left\{ \left|r-a\right|,\left|r-b\right|\right\} $ +\end_inset + +, + da je +\begin_inset Formula $\left(u-r,u+r\right)\subseteq U$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +Zaprt interval je zaprt. +\end_layout + +\begin_layout Proof +Naj bosta +\begin_inset Formula $a,b\in\mathbb{R}$ +\end_inset + + poljubna in +\begin_inset Formula $b>a$ +\end_inset + +. + Dokazujemo, + da je +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + zaprt, + torej da je +\begin_inset Formula $\left[a,b\right]^{\mathcal{C}}=\left(-\infty,a\right)\cup\left(b,\infty\right)$ +\end_inset + + odprta množica. + Za poljuben +\begin_inset Formula $u\in\left[a,b\right]^{\mathcal{C}}$ +\end_inset + + velja, + da je bodisi +\begin_inset Formula $\in\left(-\infty,a\right)$ +\end_inset + + bodisi +\begin_inset Formula $\left(b,\infty\right)$ +\end_inset + +, + kajti +\begin_inset Formula $\left(-\infty,a\right)\cap\left(b,\infty\right)=\emptyset$ +\end_inset + +. + Po prejšnji trditvi v obeh primerih velja +\begin_inset Formula $\exists r>0\ni:\left(u-r,u+r\right)\subseteq U$ +\end_inset + +, + torej je +\begin_inset Formula $\left[a,b\right]^{\mathcal{C}}$ +\end_inset + + res odprta, + torej je +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + res zaprta. +\end_layout + +\begin_layout Definition* +Množica +\begin_inset Formula $B$ +\end_inset + + je okolica točke +\begin_inset Formula $t\in\mathbb{R}$ +\end_inset + +, + če vsebuje kakšno odprto množico +\begin_inset Formula $U$ +\end_inset + +, + ki vsebuje +\begin_inset Formula $t$ +\end_inset + +, + torej +\begin_inset Formula $t\in U^{\text{odp.}}\subseteq B\subseteq\mathbb{R}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Definition* +\begin_inset Formula $L\in\mathbb{R}$ +\end_inset + + je limita zaporedja +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{R}}$ +\end_inset + + +\begin_inset Formula $\Leftrightarrow\forall\varepsilon>0\exists n_{0}\in\mathbb{N}\forall n\in\mathbb{N}:n\geq n_{0}\Rightarrow\left|a_{n}-L\right|<\varepsilon$ +\end_inset + +. + ZDB +\begin_inset Formula $\forall V$ +\end_inset + + okolica +\begin_inset Formula $L\in\mathbb{R}\exists n_{0}\in\mathbb{N}\forall n\in\mathbb{N}:n\geq n_{0}\Rightarrow a_{n}\in V$ +\end_inset + +, + pravimo, + da +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + konvergira k +\begin_inset Formula $L$ +\end_inset + + in pišemo +\begin_inset Formula $L\coloneqq\lim_{n\to\infty}a_{n}$ +\end_inset + + ali drugače +\begin_inset Formula $a_{n}\underset{n\to\infty}{\longrightarrow}L$ +\end_inset + +. + Če zaporedje ima limito, + pravimo, + da je konvergentno, + sicer je divergentno. +\end_layout + +\begin_layout Claim* +Konvergentno zaporedje v +\begin_inset Formula $\mathbb{R}$ +\end_inset + + ima natanko eno limito. +\end_layout + +\begin_layout Proof +Naj bosta +\begin_inset Formula $J$ +\end_inset + + in +\begin_inset Formula $L$ +\end_inset + + limiti zaporedja +\begin_inset Formula $\left(a_{n}\right)_{n\to\infty}$ +\end_inset + +. + Torej +\begin_inset Foot +status open + +\begin_layout Plain Layout +Ko trdimo, + da obstaja +\begin_inset Formula $n_{0}$ +\end_inset + +, + še ne vemo, + ali sta za +\begin_inset Formula $L$ +\end_inset + + in +\begin_inset Formula $J$ +\end_inset + + ta +\begin_inset Formula $n_{0}$ +\end_inset + + ista. + Ampak trditev še vedno velja, + ker lahko vzamemo večjega izmed njiju, + ako bi bila drugačna. +\end_layout + +\end_inset + + po definiciji +\begin_inset Formula $\forall\varepsilon>0\exists n_{0}\in\mathbb{N}\forall n\in\mathbb{N}:n\geq n_{0}\Rightarrow\left|a_{n}-L\right|<\varepsilon\wedge\left|a_{n}-J\right|<\varepsilon$ +\end_inset + +. + Velja torej +\begin_inset Formula $\forall\varepsilon>0:\left|J-L\right|<\varepsilon$ +\end_inset + +. + PDDRAA +\begin_inset Formula $J\not=L$ +\end_inset + +. + Tedaj +\begin_inset Formula $\left|J-L\right|\not=0$ +\end_inset + +, + naj bo +\begin_inset Formula $\left|J-L\right|=k$ +\end_inset + +. + Tedaj +\begin_inset Formula $\exists\varepsilon>0:\left|J-L\right|\not<\varepsilon$ +\end_inset + +, + ustrezen +\begin_inset Formula $\varepsilon$ +\end_inset + + je na primer +\begin_inset Formula $\frac{\left|J-L\right|}{2}$ +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset CommandInset label +LatexCommand label +name "Konvergentno-zaporedje-v-R-je-omejeno" + +\end_inset + +Konvergentno zaporedje v +\begin_inset Formula $\mathbb{R}$ +\end_inset + + je omejeno. +\end_layout + +\begin_layout Proof +Naj bo +\begin_inset Formula $L=\lim_{n\to\infty}a_{n}$ +\end_inset + +. + Znotraj intervala +\begin_inset Formula $\left(L-1,L+1\right)$ +\end_inset + + so vsi členi zaporedja razen končno mnogo ( +\begin_inset Formula $\left\{ a_{1},\dots,a_{n_{0}}\right\} $ +\end_inset + +). + +\begin_inset Formula $\left\{ a_{n}\right\} _{n\in\mathbb{N}}$ +\end_inset + + je unija dveh omejenih množic; + +\begin_inset Formula $\left(L-1,L+1\right)$ +\end_inset + + in +\begin_inset Formula $\left\{ a_{1},\dots,a_{n_{0}}\right\} $ +\end_inset + +, + zato je tudi sama omejena. +\end_layout + +\begin_layout Claim* +Naj bosta +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + in +\begin_inset Formula $\left(b_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + konvergentni zaporedji v +\begin_inset Formula $\mathbb{R}$ +\end_inset + +. + Tedaj so tudi +\begin_inset Formula $\left(a_{n}*b_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + konvergentna in velja +\begin_inset Formula $\lim_{n\to\infty}a_{n}*b_{n}=\lim_{n\to\infty}a_{n}*\lim_{n\to\infty}b_{n}$ +\end_inset + + za +\begin_inset Formula $*\in\left\{ +,-,\cdot\right\} $ +\end_inset + +. + Če je +\begin_inset Formula $\lim_{n\to\infty}b_{n}\not=0$ +\end_inset + +, + isto velja tudi za deljenje. +\end_layout + +\begin_layout Proof +Naj bo +\begin_inset Formula $a_{n}\to A$ +\end_inset + + in +\begin_inset Formula $b_{n}\to B$ +\end_inset + + oziroma +\begin_inset Formula $\forall\varepsilon>0\exists n_{1},n_{2}\ni:\left(n>n_{1}\Rightarrow\left|a_{n}-A\right|<\varepsilon\right)\wedge\left(n>n_{2}\Rightarrow\left|b_{n}-B\right|<\varepsilon\right)$ +\end_inset + +, + torej +\begin_inset Formula $\forall\varepsilon>0\exists n_{0}=\max\left\{ n_{1},n_{2}\right\} \ni:n>n_{0}\Rightarrow\left|a_{n}-A\right|<\varepsilon\wedge\left|b_{n}-B\right|<\varepsilon$ +\end_inset + +. + Dokažimo za vse operacije: +\end_layout + +\begin_deeper +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $+$ +\end_inset + + Po predpostavki velja +\begin_inset Formula $\forall\varepsilon>0\exists n_{0}\ni:n>n_{0}\Rightarrow\left|a_{n}-A\right|+\left|a_{n}-B\right|<2\varepsilon$ +\end_inset + +. + Oglejmo si sedaj +\begin_inset Formula +\[ +\left|\left(a_{n}+b_{n}\right)-\left(A+B\right)\right|=\left|\left(a_{n}-A\right)+\left(b_{n}-B\right)\right|\leq\left|a_{n}-A\right|+\left|b_{n}-B\right| +\] + +\end_inset + +in uporabimo še prejšnjo trditev, + torej +\begin_inset Formula $\forall2\varepsilon\exists n_{0}\ni:\left|\left(a_{n}+b_{n}\right)-\left(A+B\right)\right|\leq2\varepsilon$ +\end_inset + +, + s čimer dokažemo +\begin_inset Formula $\left(a_{n}+b_{n}\right)\to A+B$ +\end_inset + +. +\end_layout + +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $-$ +\end_inset + + Oglejmo si +\begin_inset Formula +\[ +\left|\left(a_{n}-b_{n}\right)-\left(A-B\right)\right|=\left|a_{n}-b_{n}-A+B\right|=\left|\left(a_{n}-A\right)+\left(-\left(b_{n}-B\right)\right)\right|\leq\left|a_{n}-A\right|+\left|b_{n}-B\right| +\] + +\end_inset + +in nato kot zgoraj. +\end_layout + +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $\cdot$ +\end_inset + + Oglejmo si +\begin_inset Formula +\[ +\left|a_{n}b_{n}-AB\right|=\left|a_{n}b_{n}-Ab_{n}+Ab_{n}-AB\right|=\left|\left(a_{n}-A\right)b_{n}+A\left(b_{n}-B\right)\right|\leq\left|a_{n}-A\right|\left|b_{n}\right|+\left|A\right|\left|b_{n}-B\right|. +\] + +\end_inset + +Od prej vemo, + da sta zaporedji omejeni, + ker sta konvergentni, + zato +\begin_inset Formula $\exists M>0\forall n\in\mathbb{N}:\left|b_{n}\right|\leq M$ +\end_inset + +. + Naj bo +\begin_inset Formula $\varepsilon>0$ +\end_inset + + poljuben +\begin_inset Formula $n_{1},n_{2}\in\mathbb{N}$ +\end_inset + + taka, + da +\begin_inset Formula $n\geq n_{1}\Rightarrow\left|a_{n}-A\right|<\frac{\varepsilon}{2M}$ +\end_inset + + in +\begin_inset Formula $n\geq n_{2}\Rightarrow\left|b_{n}-B\right|<\frac{\varepsilon}{2\left|A\right|}$ +\end_inset + +. + Tedaj za +\begin_inset Formula $n_{0}\coloneqq\max\left\{ n_{1},n_{2}\right\} $ +\end_inset + + velja +\begin_inset Formula $\left|a_{n}b_{n}-AB\right|\leq\left|a_{n}-A\right|\left|b_{n}\right|+\left|A\right|\left|b_{n}-B\right|<\frac{\varepsilon}{2M}M+\left|A\right|\frac{\varepsilon}{2\left|A\right|}=\varepsilon$ +\end_inset + +, + skratka +\begin_inset Formula $\left|a_{n}b_{n}-AB\right|<\varepsilon$ +\end_inset + +, + s čimer dokažemo +\begin_inset Formula $\left(a_{n}+b_{n}\right)\to A+B$ +\end_inset + +. +\end_layout + +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $/$ +\end_inset + + Ker je +\begin_inset Formula $B\not=0$ +\end_inset + +, + +\begin_inset Formula $\exists n_{0}\in\mathbb{N}\forall n\geq n_{0}:\left|b_{n}\right|\geq\frac{\left|B\right|}{2}>0$ +\end_inset + +. + ZDB vsi členi zaporedja razen končno mnogo so v poljubno majhni okolici +\begin_inset Formula $\left|B\right|$ +\end_inset + +. + Če torej vzamemo točko na polovici med 0 in +\begin_inset Formula $\left|B\right|$ +\end_inset + +, + to je +\begin_inset Formula $\frac{\left|B\right|}{2}$ +\end_inset + +, + bo neskončno mnogo absolutnih vrednosti členov večjih od +\begin_inset Formula $\frac{\left|B\right|}{2}$ +\end_inset + +. + Pri razumevanju pomaga številska premica. + Nadalje uporabimo predpostavko z +\begin_inset Formula $\varepsilon=\frac{\left|B\right|}{2}$ +\end_inset + +, + torej je za +\begin_inset Formula $n>n_{0}:$ +\end_inset + + +\begin_inset Formula $\left|B-b_{n}\right|<\frac{\left|B\right|}{2}$ +\end_inset + + in velja +\begin_inset Formula +\[ +\left|b_{n}\right|=\left|B-\left(B-b_{n}\right)\right|=\left|B+\left(-\left(B-b_{n}\right)\right)\right|\overset{\text{trik. neen.}}{\geq}\left|\left|B\right|-\left|B-b_{n}\right|\right|=\left|B\right|-\left|B-b_{n}\right|\overset{\text{predp.}}{>}\left|B\right|-\frac{\left|B\right|}{2}=\frac{\left|B\right|}{2}, +\] + +\end_inset + +skratka +\begin_inset Formula $\left|b_{n}\right|>\frac{\left|B\right|}{2}$ +\end_inset + +. + Če spet izpustimo končno začetnih členov, + velja +\begin_inset Formula +\[ +\frac{a_{n}}{b_{n}}-\frac{A}{B}=\frac{a_{n}B-Ab_{n}}{b_{n}B}\overset{\text{prištejemo in odštejemo člen}}{=}\frac{\left(a_{n}-A\right)B+A\left(B-b_{n}\right)}{Bb_{n}}=\frac{1}{b_{n}}\left(a_{n}-A\right)+\frac{A/B}{b_{n}}\left(B-b_{n}\right) +\] + +\end_inset + +sedaj uporabimo na obeh straneh absolutno vrednost: +\begin_inset Formula +\[ +\left|\frac{a_{n}}{b_{n}}-\frac{A}{B}\right|=\left|\frac{1}{b_{n}}\left(a_{n}-A\right)+\frac{A}{Bb_{n}}\left(B-b_{n}\right)\right|\leq\frac{1}{\left|b_{n}\right|}\left|a_{n}-A\right|+\frac{\left|A\right|}{\left|B\right|\left|b_{n}\right|}\left|B-b_{n}\right|<\frac{2}{\left|B\right|}\left|a_{n}-A\right|+\frac{2\left|A\right|}{\left|B\right|^{2}}\left|B-B_{n}\right| +\] + +\end_inset + +skratka +\begin_inset Formula $\left|\frac{a_{n}}{b_{n}}-\frac{A}{B}\right|<\frac{2}{\left|B\right|}\left|a_{n}-A\right|+\frac{2\left|A\right|}{\left|B\right|^{2}}\left|B-B_{n}\right|$ +\end_inset + +. + Opazimo, + da +\begin_inset Formula $\frac{2}{\left|B\right|}$ +\end_inset + + in +\begin_inset Formula $\frac{2\left|A\right|}{\left|B\right|^{2}}$ +\end_inset + + nista odvisna od +\begin_inset Formula $n$ +\end_inset + +. + Sedaj vzemimo poljuben +\begin_inset Formula $\varepsilon>0$ +\end_inset + + in +\begin_inset Formula $n_{1},n_{2}\in\mathbb{N}$ +\end_inset + + takšna, + da velja: +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $n\geq n_{1}\Rightarrow\left|a_{n}-A\right|<\frac{\varepsilon\left|B\right|}{4}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +\begin_inset Formula $n\geq n_{2}\Rightarrow\left|b_{n}-B\right|<\frac{\varepsilon\left|B\right|^{2}}{4\left|A\right|}$ +\end_inset + + +\end_layout + +\begin_layout Standard +Tedaj iz zgornje ocene sledi za +\begin_inset Formula $n\geq\max\left\{ n_{0},n_{1},n_{2}\right\} $ +\end_inset + +: +\begin_inset Formula +\[ +\left|\frac{a_{n}}{b_{n}}-\frac{A}{B}\right|<\frac{\cancel{2}}{\cancel{\left|B\right|}}\cdot\frac{\varepsilon\cancel{\left|B\right|}}{\cancelto{2}{4}}+\frac{\cancel{2}\cancel{\left|A\right|}}{\cancel{\left|B\right|^{2}}}\cdot\frac{\varepsilon\cancel{\left|B\right|^{2}}}{\cancelto{2}{4}\cancel{\left|A\right|}}=\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon, +\] + +\end_inset + +s čimer dokažemo +\begin_inset Formula $a_{n}/b_{n}\to A/B$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Example* +Naj bo +\begin_inset Formula $a>0$ +\end_inset + +. + Izračunajmo +\begin_inset Formula +\[ +\sqrt{a+\sqrt{a+\sqrt{a+\sqrt{\cdots}}}}\eqqcolon\alpha. +\] + +\end_inset + + +\end_layout + +\begin_layout Example* +\begin_inset Formula $\alpha$ +\end_inset + + je torej +\begin_inset Formula $\lim_{n\to\infty}x_{n}$ +\end_inset + +, + kjer je +\begin_inset Formula $x_{0}=0,x_{1}=\sqrt{a},x_{2}=\sqrt{a+\sqrt{a}},x_{3}=\sqrt{a+\sqrt{a+\sqrt{a}}},\dots,x_{n+1}=\sqrt{a+x_{n}}$ +\end_inset + +. + Iz zadnjega sledi +\begin_inset Formula $x_{n+1}^{2}=a+x_{n}$ +\end_inset + +. + Če torej limita +\begin_inset Formula $\alpha\coloneqq\lim x_{n}$ +\end_inset + + obstaja, + mora veljati +\begin_inset Formula $\alpha^{2}=a+\alpha$ +\end_inset + + oziroma +\begin_inset Formula $\alpha_{1,2}=\frac{1\pm\sqrt{1+4a}}{2}$ +\end_inset + +. + Opcija z minusom ni mogoča, + ker je zaporedje +\begin_inset Formula $\left(x_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + očitno pozitivno. + Če torej limita obstaja ( +\series bold +česar še nismo dokazali +\series default +), + je enaka +\begin_inset Formula $\frac{1+\sqrt{1+4a}}{2}$ +\end_inset + +, + za primer +\begin_inset Formula $a=2$ +\end_inset + + je torej +\begin_inset Formula $\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{\cdots}}}}=2$ +\end_inset + +. +\end_layout + +\begin_layout Remark* +Lahko se zgodi, + da limita rekurzivno podanega zaporedja ne obstaja, + čeprav jo znamo izračunati, + če bi obstajala. + Na primer +\begin_inset Formula $y_{1}\coloneqq1$ +\end_inset + +, + +\begin_inset Formula $y_{n+1}=1-2y_{n}$ +\end_inset + + nam da zaporedje +\begin_inset Formula $1,-1,3,-5,11,\dots$ +\end_inset + +, + kar očitno nima limite. + Če bi limita obstajala, + bi zanjo veljalo +\begin_inset Formula $\beta=1-2\beta$ +\end_inset + + oz. + +\begin_inset Formula $3\beta=1$ +\end_inset + +, + +\begin_inset Formula $\beta=\frac{1}{3}$ +\end_inset + +. + Navedimo torej nekaj zadostnih in potrebnih pogojev za konvergenco zaporedij. +\end_layout + +\begin_layout Theorem* +Naj bo +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + monotono realno zaporedje. + Če narašča, + ima limito +\begin_inset Formula $\lim_{n\to\infty}a_{n}=\sup\left\{ a_{n},n\in\mathbb{N}\right\} $ +\end_inset + +. + Če pada, + ima limito +\begin_inset Formula $\lim_{n\to\infty}a_{n}=\inf\left\{ a_{n},n\in\mathbb{N}\right\} $ +\end_inset + +. + ( +\begin_inset Formula $\sup$ +\end_inset + + in +\begin_inset Formula $\inf$ +\end_inset + + imata lahko tudi vrednost +\begin_inset Formula $\infty$ +\end_inset + + in +\begin_inset Formula $-\infty$ +\end_inset + + — + zaporedje s tako limito ni konvergentno v +\begin_inset Formula $\mathbb{R}$ +\end_inset + +). +\end_layout + +\begin_layout Proof +Denimo, + da +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + narašča. + Pišimo +\begin_inset Formula $s\coloneqq\sup_{n\in\mathbb{N}}a_{n}$ +\end_inset + +. + Vzemimo poljuben +\begin_inset Formula $\varepsilon>0$ +\end_inset + +. + Tedaj +\begin_inset Formula $s-\varepsilon$ +\end_inset + + ni zgornja meja za +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + +, + zato +\begin_inset Formula $\exists n_{0}\in\mathbb{N}\ni:s-\varepsilon<a_{n_{0}}$ +\end_inset + +. + Ker pa je +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + +naraščajoče, + sledi +\begin_inset Formula $\forall n\geq n_{0}:a_{n}\geq a_{n_{0}}>s-\varepsilon$ +\end_inset + +. + Hkrati je +\begin_inset Formula $a_{n}\leq s$ +\end_inset + +, + saj je +\begin_inset Formula $s$ +\end_inset + + zgornja meja. + Torej +\begin_inset Formula $\forall n\geq n_{0}:a_{n}\in(s-\varepsilon,s]\subset\left(s-\varepsilon,s+\varepsilon\right)$ +\end_inset + +, + s čimer dokažemo konvergenco. +\end_layout + +\begin_layout Proof +Denimo sedaj, + da +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + pada. + Dokaz je povsem analogen. + Pišimo +\begin_inset Formula $m\coloneqq\inf_{n\in\mathbb{N}}a_{n}$ +\end_inset + +. + Vzemimo poljuben +\begin_inset Formula $\varepsilon>0$ +\end_inset + +. + Tedaj +\begin_inset Formula $m+\varepsilon$ +\end_inset + + ni spodnja meja za +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + +, + zato +\begin_inset Formula $\exists n_{0}\in\mathbb{N}\ni:m+\varepsilon>a_{n_{0}}$ +\end_inset + +. + Ker pa je +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + padajoče, + sledi +\begin_inset Formula $\forall n\geq n_{0}:a_{n}\leq a_{n_{0}}<m+\varepsilon$ +\end_inset + +. + Hkrati je +\begin_inset Formula $a_{n}\geq m$ +\end_inset + +, + saj je +\begin_inset Formula $m$ +\end_inset + + spodnja meja. + Torej +\begin_inset Formula $\forall n\geq n_{0}:a_{n}\in[m,m+\varepsilon)\subset\left(m-\varepsilon,m+\varepsilon\right)$ +\end_inset + +. +\end_layout + +\begin_layout Corollary* +Za monotono zaporedje velja, + da je v +\begin_inset Formula $\mathbb{R}$ +\end_inset + + konvergentno natanko tedaj, + ko je omejeno. +\end_layout + +\begin_layout Example* +Naj bo, + kot prej, + +\begin_inset Formula $a>0$ +\end_inset + + in +\begin_inset Formula $x_{0}=0,x_{n+1}=\sqrt{a+x_{n}}$ +\end_inset + +. + Dokažimo, + da je +\begin_inset Formula $\left(x_{n}\right)_{n}$ +\end_inset + + konvergentno. + Dovolj je pokazati, + da je naraščajoče in navzgor omejeno. +\end_layout + +\begin_deeper +\begin_layout Itemize +Naraščanje z indukcijo: + Baza: + +\begin_inset Formula $0=x_{0}>x_{1}=\sqrt{a}$ +\end_inset + +. + Dokažimo +\begin_inset Formula $x_{n+1}-x_{n}>0$ +\end_inset + +. +\begin_inset Formula +\[ +\left(x_{n+1}-x_{n}\right)\left(x_{n+1}+x_{n}\right)=x_{n+1}^{2}-x_{n}^{2}=\left(a+x_{n}\right)-\left(a+x_{n-1}\right)=x_{n}-x_{n-1} +\] + +\end_inset + +Ker je zaporedje pozitivno, + je +\begin_inset Formula $x_{n+1}+x_{n}>0$ +\end_inset + +. + Desna stran je po I. + P. + pozitivna, + torej tudi +\begin_inset Formula $x_{n+1}-x_{n}>0$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +Omejenost: + Če je zaporedje res omejeno, + je po zgornjem tudi konvergentno in je +\begin_inset Formula $\sup_{n\in\mathbb{N}}x_{n}=\lim_{n\to\infty}x_{n}=\frac{1+\sqrt{1+4a}}{2}\leq\frac{1+\sqrt{1+4a+4a^{2}}}{2}=\frac{1+\sqrt{\left(2a+1\right)^{2}}}{}=1+a$ +\end_inset + +. + Uganili smo neko zgornjo mejo. + Domnevamo, + da +\begin_inset Formula $\forall n\in\mathbb{N}:x_{n}\leq1+a$ +\end_inset + +. + Dokažimo to z indukcijo: + Baza: + +\begin_inset Formula $0=x_{0}<1+a$ +\end_inset + +. + Po I. + P. + +\begin_inset Formula $x_{n}>1+a$ +\end_inset + +. + Korak: +\begin_inset Formula +\[ +x_{n+1}=\sqrt{x_{n}+a}\leq\sqrt{1+a+a}=\sqrt{1+2a}<\sqrt{1+2a+2a^{2}}=1+a +\] + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Example* +S tem smo dokazali, + da +\begin_inset Formula $\lim_{n\to\infty}x_{n}=\frac{1+\sqrt{1+4a}}{2}$ +\end_inset + +. +\end_layout + +\begin_layout Example* +To lahko dokažemo tudi na alternativen način. + Vidimo, + da je edini kandidat za limito, + če obstaja +\begin_inset Formula $L=\frac{1+\sqrt{1+4a}}{2}$ +\end_inset + + in da torej velja +\begin_inset Formula $L^{2}=a+L$ +\end_inset + +. + Preverimo, + da je +\begin_inset Formula $L$ +\end_inset + + res limita: + +\begin_inset Formula +\[ +x_{n+1}-L=\sqrt{a+x_{n}}-L=\frac{\left(\sqrt{a+x_{n}}-L\right)\left(\sqrt{a+x_{n}}+L\right)}{\sqrt{a+x_{n}}+L}=\frac{\left(a+x_{n}\right)-L^{2}}{\sqrt{a+x_{n}}+L}=\frac{\left(a+x_{n}\right)-\left(a+L\right)}{\sqrt{a+x_{n}}+L}=\frac{x_{n}-L}{\sqrt{a+x_{n}}+L}. +\] + +\end_inset + +Vpeljimo sedaj +\begin_inset Formula $y_{n}\coloneqq x_{n}-L$ +\end_inset + +. + Sledi +\begin_inset Formula $\left|y_{n+1}\right|\leq\frac{\left|y_{n}\right|}{\sqrt{a+x_{n}}+L}\leq\frac{\left|y_{n}\right|}{L}$ +\end_inset + +. + Ker je +\begin_inset Formula $\left|y_{0}\right|=L$ +\end_inset + +, + dobimo +\begin_inset Foot +status open + +\begin_layout Plain Layout +Za razumevanje si oglej nekaj členov rekurzivnega zaporedje +\begin_inset Formula $y_{0}=L,y_{n}=\frac{\left|y_{n+1}\right|}{L}$ +\end_inset + +. + Začnemo z 1 in nato vsakič delimo z +\begin_inset Formula $L$ +\end_inset + +. +\end_layout + +\end_inset + + oceno +\begin_inset Formula $\left|y_{n}\right|\leq\frac{1}{L^{n-1}}$ +\end_inset + + oziroma +\begin_inset Formula $\left|x_{n}-L\right|\leq\frac{1}{L^{n-1}}$ +\end_inset + +. + Ker iz definicije +\begin_inset Formula $L$ +\end_inset + + sledi +\begin_inset Formula $L>1$ +\end_inset + +, + je +\begin_inset Formula $L^{n}\to\infty$ +\end_inset + + za +\begin_inset Formula $n\to\infty$ +\end_inset + +, + torej smo dokazali, + da +\begin_inset Formula $\left|x_{n}-L\right|$ +\end_inset + + eksponentno pada proti 0 za +\begin_inset Formula $n\to\infty$ +\end_inset + +. + Eksponentno padanje +\begin_inset Formula $\left|x_{n}-L\right|$ +\end_inset + + proti 0 je dovolj, + da rečemo, + da zaporedje konvergira k +\begin_inset Formula $L$ +\end_inset + + +\begin_inset Foot +status open + +\begin_layout Plain Layout +a res, + vprašaj koga. + ne razumem. + zakaj. + TODO. +\end_layout + +\end_inset + +. +\end_layout + +\begin_layout Claim* +\begin_inset Formula $\lim_{n\to\infty}\sin n$ +\end_inset + + in +\begin_inset Formula $\lim_{n\to\infty}\cos n$ +\end_inset + + ne obstajata. +\end_layout + +\begin_layout Proof +Pišimo +\begin_inset Formula $a_{n}=\sin n$ +\end_inset + + in +\begin_inset Formula $b_{n}=\cos n$ +\end_inset + +. + Iz adicijskih izrekov dobimo +\begin_inset Formula $a_{n+1}=\sin\left(n+1\right)=\sin n\cos1+\cos n\sin1=a_{n}\cos1+b_{n}\sin1$ +\end_inset + +. + Torej +\begin_inset Formula $b_{n}=\frac{a_{n+1}-a_{n}\cos1}{\sin1}$ +\end_inset + +. + Torej če +\begin_inset Formula $\exists a\coloneqq\lim_{n\to\infty}a_{n},a\in\mathbb{R}$ +\end_inset + +, + potem tudi +\begin_inset Formula $\exists b\coloneqq\lim_{n\to\infty}b_{n},b\in\mathbb{R}$ +\end_inset + +. + Podobno iz adicijske formule za +\begin_inset Formula $\cos\left(n+1\right)$ +\end_inset + + sledi +\begin_inset Formula $a_{n}=\frac{b_{n}\cos1-b_{n+1}}{\sin1}$ +\end_inset + +, + torej če +\begin_inset Formula $\exists b$ +\end_inset + +, + potem tudi +\begin_inset Formula $\exists a$ +\end_inset + +. + Iz obojega sledi, + da +\begin_inset Formula $\exists a\Leftrightarrow\exists b$ +\end_inset + +. + Posledično, + če +\begin_inset Formula $a$ +\end_inset + + in +\begin_inset Formula $b$ +\end_inset + + obstajata, + iz zgornjih obrazcev za +\begin_inset Formula $a_{n}$ +\end_inset + + in +\begin_inset Formula $b_{n}$ +\end_inset + + sledi, + da za +\begin_inset Formula +\[ +\lambda=\frac{1-\cos1}{\sin1}\in\left(0,1\right) +\] + +\end_inset + +velja +\begin_inset Formula $b=\lambda a$ +\end_inset + + in +\begin_inset Formula $a=-\lambda b$ +\end_inset + + in zato +\begin_inset Formula $b=\lambda\left(-\lambda b\right)$ +\end_inset + + oziroma +\begin_inset Formula $1=-\lambda^{2}$ +\end_inset + +, + torej +\begin_inset Formula $-1=\lambda^{2}$ +\end_inset + +, + torej +\begin_inset Formula $\lambda=i$ +\end_inset + +, + kar je v protislovju z +\begin_inset Formula $\lambda\in\left(0,1\right)$ +\end_inset + +. + Podobno za +\begin_inset Formula $a=-\lambda\left(\lambda a\right)$ +\end_inset + + oziroma +\begin_inset Formula $1=-\lambda^{2}$ +\end_inset + +, + kar je zopet +\begin_inset Formula $\rightarrow\!\leftarrow$ +\end_inset + +. + Edina druga opcija je, + da je +\begin_inset Formula $a=b=0$ +\end_inset + +. + Hkrati pa vemo, + da +\begin_inset Formula $a_{n}^{2}+b_{n}^{2}=1$ +\end_inset + +, + zato +\begin_inset Formula $a+b=1$ +\end_inset + +, + kar ni mogoče za ničelna +\begin_inset Formula $a$ +\end_inset + + in +\begin_inset Formula $b$ +\end_inset + +. + Torej +\begin_inset Formula $a$ +\end_inset + + in +\begin_inset Formula $b$ +\end_inset + + ne obstajata. +\end_layout + +\begin_layout Subsection +Eulerjevo število +\end_layout + +\begin_layout Theorem* +Bernoullijeva neenakost. + +\begin_inset Formula $\forall\alpha\leq1,n\in\mathbb{N}$ +\end_inset + + velja +\begin_inset Formula $\left(1-\alpha\right)^{n}\geq1-n\alpha$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Z indukcijo na +\begin_inset Formula $n$ +\end_inset + + ob fiksnem +\begin_inset Formula $\alpha$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Itemize +Baza: + +\begin_inset Formula $n=1$ +\end_inset + +: + +\begin_inset Formula $\left(1-\alpha\right)^{1}=1-1\alpha$ +\end_inset + +. + Velja celo enakost. +\end_layout + +\begin_layout Itemize +I. + P.: + Velja +\begin_inset Formula $\left(1-\alpha\right)^{n}\geq1-n\alpha$ +\end_inset + + +\end_layout + +\begin_layout Itemize +Korak: + +\begin_inset Formula $\left(1-\alpha\right)^{n+1}=\left(1-\alpha\right)\left(1-\alpha\right)^{n}\geq\left(1-\alpha\right)$ +\end_inset + + +\begin_inset Formula $\left(1-n\alpha\right)=1-n\alpha-\alpha-n\alpha^{2}=1-\left(n+1\right)\alpha-n\alpha^{2}\geq1-\left(n+1\right)\alpha$ +\end_inset + +, + torej ocena velja tudi za +\begin_inset Formula $n+1$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Definition* +Vpeljimo oznaki: +\end_layout + +\begin_deeper +\begin_layout Itemize +Za +\begin_inset Formula $n\in\mathbb{N}$ +\end_inset + + označimo +\begin_inset Formula $n!=1\cdot2\cdot3\cdot\cdots\cdot n$ +\end_inset + + (pravimo +\begin_inset Formula $n-$ +\end_inset + +faktoriala oziroma +\begin_inset Formula $n-$ +\end_inset + +fakulteta). + Ker velja +\begin_inset Formula $n!=n\cdot\left(n-1\right)!$ +\end_inset + + za +\begin_inset Formula $n\geq2$ +\end_inset + +, + je smiselno definirati še +\begin_inset Formula $0!=1$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +Za +\begin_inset Formula $n,k\in\mathbb{N}$ +\end_inset + + označimo še binomski simbol: + +\begin_inset Formula $\binom{n}{k}\coloneqq\frac{n!}{k!\left(n-k\right)!}$ +\end_inset + + (pravimo +\begin_inset Formula $n$ +\end_inset + + nad +\begin_inset Formula $k$ +\end_inset + +). +\end_layout + +\begin_layout Itemize +Če je +\begin_inset Formula $\left(a_{k}\right)_{k}$ +\end_inset + + neko zaporedje (lahko tudi končno), + lahko pišemo +\begin_inset Formula $\sum_{k=1}^{n}a_{k}\coloneqq a_{1}+a_{2}+\cdots+a_{n}$ +\end_inset + + (pravimo summa) in +\begin_inset Formula $\prod_{k=1}^{n}a_{k}\coloneqq a_{1}\cdot\cdots\cdot a_{n}$ +\end_inset + + (pravimo produkt). +\end_layout + +\end_deeper +\begin_layout Example* +\begin_inset Formula $\sum_{k=1}^{n}\frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ +\end_inset + + in +\begin_inset Formula $\prod_{k=1}^{n}k=1\cdot2\cdot3\cdot\cdots\cdot n=n!$ +\end_inset + +. +\end_layout + +\begin_layout Theorem* +Binomska formula. + +\begin_inset Formula $\forall a,b\in\mathbb{R},n\in\mathbb{N}:\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Indukcija po +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_deeper +\begin_layout Itemize +Baza +\begin_inset Formula $n=1$ +\end_inset + +: + +\begin_inset Formula $\sum_{k=0}^{1}\binom{n}{k}a^{k}b^{n-k}=\binom{1}{0}a^{0}b^{1-0}+\binom{1}{1}a^{1}b^{1-1}=a+b=\left(a+b\right)^{1}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +I. + P. + +\begin_inset Formula $\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}=\left(a+b\right)^{n}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +Korak: + +\begin_inset Formula +\[ +\left(a+b\right)^{n+1}=\left(a+b\right)\left(a+b\right)^{n}=\left(a+b\right)\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}=\sum_{k=0}^{n}\binom{n}{k}a^{k+1}b^{n-k}+\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k+1}= +\] + +\end_inset + +sedaj naj bo +\begin_inset Formula $m=k+1$ +\end_inset + + v levem členu: +\begin_inset Formula +\[ +=\sum_{m=1}^{n+1}\binom{n}{m-1}a^{m}b^{n-\left(m-1\right)}+\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k+1}=a^{n+1}+\sum_{k=1}^{n}\left[\binom{n}{k-1}+\binom{n}{k}\right]a^{k}b^{n-k+1}+b^{n+1}= +\] + +\end_inset + +Sedaj obravnavajmo le izraz v oglatih oklepajih: +\begin_inset Formula +\[ +\binom{n}{k-1}+\binom{n}{k}=\frac{n!}{\left(k-1\right)!\left(n-k+1\right)!}+\frac{n!}{k!\left(n-k\right)!}=\frac{kn!}{k!\left(n-k+1\right)!}+\frac{n!\left(n-k+1\right)}{k!\left(n-k+1\right)!}=\frac{kn!+n!\left(n-k+1\right)}{k!\left(n-k+1\right)!}= +\] + +\end_inset + + +\begin_inset Formula +\[ +=\frac{n!\left(\cancel{k+}n\cancel{-k}+1\right)}{k!\left(n+1-k\right)!}=\frac{n!\left(n+1\right)}{k!\left(n+1-k\right)!}=\frac{\left(n+1\right)!}{k!\left(n+1-k\right)}=\binom{n+1}{k} +\] + +\end_inset + +in skratka dobimo +\begin_inset Formula $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$ +\end_inset + +. + Vstavimo to zopet v naš zgornji račun: +\begin_inset Formula +\[ +\cdots=a^{n+1}+\sum_{k=1}^{n}\left[\binom{n}{k-1}+\binom{n}{k}\right]a^{k}b^{n-k+1}+b^{n+1}=a^{n+1}+\sum_{k=1}^{n}\binom{n+1}{k}a^{k}b^{n-k+1}+b^{n+1}= +\] + +\end_inset + + +\begin_inset Formula +\[ +=a^{n+1}+\sum_{k=1}^{n}\binom{n+1}{k}a^{k}b^{n-k+1}+b^{n+1}=a^{n+1}+\sum_{k=0}^{n}\binom{n+1}{k}a^{k}b^{n-k+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{k}b^{n-k+1} +\] + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Theorem* +Bernoulli. + Zaporedje +\begin_inset Formula $a_{n}\coloneqq\left(1+\frac{1}{n}\right)^{n}$ +\end_inset + + je konvergentno. +\end_layout + +\begin_layout Proof +Dokazali bomo, + da je naraščajoče in omejeno. +\end_layout + +\begin_deeper +\begin_layout Itemize +Naraščanje: + Dokazujemo, + da za +\begin_inset Formula $n\geq2$ +\end_inset + + velja +\begin_inset Formula $a_{n}\geq a_{n-1}$ +\end_inset + + oziroma +\begin_inset Formula +\[ +\left(1+\frac{1}{n}\right)^{n}\overset{?}{\geq}\left(1+\frac{1}{n-1}\right)^{n-1}=\left(\frac{n-1}{n-1}+\frac{1}{n-1}\right)^{n-1}=\left(\frac{n}{n-1}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{1-n}=\left(1-\frac{1}{n}\right)^{1-n} +\] + +\end_inset + + +\begin_inset Formula +\[ +\left(1+\frac{1}{n}\right)^{n}\overset{?}{\geq}\left(1-\frac{1}{n}\right)^{1-n} +\] + +\end_inset + + +\begin_inset Formula +\[ +\left(1+\frac{1}{n^{2}}\right)^{n}=\left(\left(1+\frac{1}{n}\right)\left(1-\frac{1}{n}\right)\right)^{n}=\left(1+\frac{1}{n}\right)^{n}\left(1-\frac{1}{n}\right)^{n}\overset{?}{\geq}1-\frac{1}{n} +\] + +\end_inset + + +\begin_inset Formula +\[ +\left(1+\frac{1}{n^{2}}\right)^{n}\overset{?}{\geq}1-\frac{1}{n}, +\] + +\end_inset + +kar je poseben primer Bernoullijeve neenakosti za +\begin_inset Formula $\alpha=\frac{1}{n^{2}}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +Omejenost: + Po binomski formuli je +\begin_inset Formula +\[ +a_{n}=\left(1+\frac{1}{n}\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}\left(\frac{1}{n}\right)^{k}=\sum_{k=0}^{n}\frac{n!}{k!\left(n-k\right)!n^{k}}=1+1+\sum_{k=2}^{n}\frac{n!}{k!\left(n-k\right)!n^{k}}=2+\sum_{k=2}^{n}\frac{1}{k!}\cdot\frac{n\left(n-1\right)\left(n-2\right)\cdots\left(n-k+1\right)}{n^{k}}= +\] + +\end_inset + + +\begin_inset Formula +\[ +=2+\sum_{k=2}^{n}\frac{1}{k!}\cdot\frac{n}{n}\cdot\frac{n-1}{n}\cdot\frac{n-2}{n}\cdot\cdots\cdot\frac{n-k+1}{n}=2+\sum_{k=2}^{n}\frac{1}{k!}\cdot\cancel{\left(1-0\right)}\cdot\left(1-\frac{1}{n}\right)\cdot\left(1-\frac{2}{n}\right)\cdot\cdots\cdot\left(1-\frac{k-1}{n}\right)= +\] + +\end_inset + + +\begin_inset Formula +\[ +=2+\sum_{k=2}^{n}\frac{1}{k!}\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)<2+\sum_{k=2}^{n}\frac{1}{k!}<2+\sum_{k=2}^{n}\frac{1}{2^{k-1}}=\cdots +\] + +\end_inset + +Opomnimo, + da je +\begin_inset Formula $1-\frac{j}{n}<1$ +\end_inset + +, + zato +\begin_inset Formula $\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)<1$ +\end_inset + + (prvi neenačaj) ter +\begin_inset Formula $k!=1\cdot2\cdot3\cdot\cdots\cdot k\geq1\cdot2\cdot2\cdot\cdots\cdot2=2^{k-1}$ +\end_inset + + (drugi). + Sedaj si z indukcijo dokažimo +\begin_inset Formula $\sum_{k=2}^{n}\frac{1}{2^{k-1}}=1-\frac{1}{2^{n-1}}$ +\end_inset + +: +\end_layout + +\begin_deeper +\begin_layout Itemize +Baza: + +\begin_inset Formula $n=2$ +\end_inset + +: + +\begin_inset Formula $\frac{1}{2^{2-1}}=1-\frac{1}{2^{2-1}}=1-\frac{1}{2}=\frac{1}{2}$ +\end_inset + +. + Velja! +\end_layout + +\begin_layout Itemize +I. + P.: + +\begin_inset Formula $\sum_{k=2}^{n}\frac{1}{2^{k-1}}=1-\frac{1}{2^{n-1}}$ +\end_inset + + +\end_layout + +\begin_layout Itemize +Korak: + +\begin_inset Formula $\sum_{k=2}^{n+1}\frac{1}{2^{k-1}}=1-\frac{1}{2^{n-1}}+\frac{1}{2^{n+1-1}}=1-2\cdot2^{-n}+2^{-n}=1+2^{-n}\left(1-2\right)=1+2^{-n}$ +\end_inset + + +\end_layout + +\begin_layout Standard +In nadaljujmo z računanjem: +\begin_inset Formula +\[ +\cdots=2+1-\frac{1}{2^{n-1}}=3-\frac{1}{2^{n-1}}, +\] + +\end_inset + +s čimer dobimo zgornjo mejo +\begin_inset Formula $\forall n\in\mathbb{N}:a_{n}<3$ +\end_inset + +. + Ker je očitno +\begin_inset Formula $\forall n\in\mathbb{N}:a_{n}>0$ +\end_inset + +, + je torej zaporedje omejeno in ker je tudi monotono po prejšnjem izreku konvergira. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Definition* +Označimo število +\begin_inset Formula $e\coloneqq\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{n}$ +\end_inset + + in ga imenujemo Eulerjevo število. + Velja +\begin_inset Formula $e\approx2,71828$ +\end_inset + +. +\end_layout + +\begin_layout Remark* +V dokazu vidimo moč izreka +\begin_inset Quotes gld +\end_inset + +omejenost in monotonost +\begin_inset Formula $\Rightarrow$ +\end_inset + + konvergenca +\begin_inset Quotes grd +\end_inset + +, + saj nam omogoča dokazati konvergentnost zaporedja brez kandidata za limito. + Jasno je, + da ne bi mogli vnaprej uganiti, + da je limita ravno +\shape italic +transcendentno število +\shape default + +\begin_inset Formula $e$ +\end_inset + +. +\end_layout + +\begin_layout Definition* +Podzaporedje zaporedja +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + je poljubno zaporedje oblike +\begin_inset Formula $\left(a_{\varphi\left(n\right)}\right)_{n\in\mathbb{N}}$ +\end_inset + +, + kjer je +\begin_inset Formula $\varphi:\mathbb{N}\to\mathbb{N}$ +\end_inset + + strogo naraščajoča funkcija. + Definicijsko območje +\begin_inset Formula $\varphi$ +\end_inset + + mora vsebovati števno neskončno elementov. +\end_layout + +\begin_layout Theorem* +Če je +\begin_inset Formula $L=\lim_{n\to\infty}a_{n}$ +\end_inset + +, + tedaj je +\begin_inset Formula $L$ +\end_inset + + tudi limita vsakega podzaporedja. +\end_layout + +\begin_layout Proof +Po predpostavki velja +\begin_inset Formula $\forall\varepsilon>0\exists n_{0}\in\mathbb{N}\forall n\in\mathbb{N}:n\geq n_{0}:\left|a_{n}-L\right|<\varepsilon$ +\end_inset + +. + Vzemimo poljuben +\begin_inset Formula $\varepsilon>0$ +\end_inset + +. + Po predpostavki obstaja +\begin_inset Formula $n_{0}\in\mathbb{N}$ +\end_inset + +, + da bodo vsi členi zaporedja po +\begin_inset Formula $n_{0}-$ +\end_inset + +tem v +\begin_inset Formula $\left(L-\varepsilon,L+\varepsilon\right)$ +\end_inset + +. + Iz definicijskega območja +\begin_inset Formula $\varphi$ +\end_inset + + vzemimo poljuben element +\begin_inset Formula $n_{1}$ +\end_inset + +, + da velja +\begin_inset Formula $n_{1}\geq n_{0}$ +\end_inset + +. + Gotovo obstaja, + ker je definicijsko območje števno neskončne moči in s pogojem +\begin_inset Formula $n_{1}\geq n_{0}$ +\end_inset + + onemogočimo izbiro le končno mnogo elementov. + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +Če slednji ne obstaja, + je v +\begin_inset Formula $D_{\varphi}$ +\end_inset + + končno mnogo elementov, + tedaj vzamemo +\begin_inset Formula $n_{1}\coloneqq\max D_{\varphi}+1$ +\end_inset + + in je pogoj za limito izpolnjen na prazno. + Sicer pa v +\end_layout + +\end_inset + +Velja +\begin_inset Formula $\forall n\in\mathbb{N}:n>n_{1}\Rightarrow\left|a_{\varphi n}-L\right|<\varepsilon$ +\end_inset + +, + ker je +\begin_inset Formula $\varphi$ +\end_inset + + strogo naraščajoča in izbiramo le elemente podzaporedja, + ki so v izvornem zaporedju za +\begin_inset Formula $n_{0}-$ +\end_inset + +tim členom in zato v +\begin_inset Formula $\left(L-\varepsilon,L+\varepsilon\right)$ +\end_inset + +. +\end_layout + +\begin_layout Example* +\begin_inset Formula $\lim_{n\to\infty}\frac{1}{2n+3}=\lim_{n\to\infty}\frac{1}{n}=0$ +\end_inset + + za zaporedje +\begin_inset Formula $a_{n}=\frac{1}{n}$ +\end_inset + + in podzaporedje +\begin_inset Formula $a_{\varphi n}$ +\end_inset + +, + kjer je +\begin_inset Formula $\varphi\left(n\right)=2n+3$ +\end_inset + +. +\end_layout + +\begin_layout Theorem* +Karakterizacija limite s podzaporedji. + Naj bo +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}$ +\end_inset + + realno zaporedje in +\begin_inset Formula $L\in\mathbb{R}$ +\end_inset + +. + Tedaj +\begin_inset Formula $L=\lim_{n\to\infty}a_{n}\Leftrightarrow$ +\end_inset + + za vsako podzaporedje +\begin_inset Formula $\left(a_{n_{k}}\right)_{k\in\mathbb{N}}$ +\end_inset + + zaporedja +\begin_inset Formula $\left(a_{n}\right)_{n}$ +\end_inset + + obstaja njegovo podzaporedje +\begin_inset Formula $\left(a_{n_{k_{l}}}\right)_{l\in\mathbb{N}}$ +\end_inset + +, + ki konvergira k +\begin_inset Formula $L$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Dokazujemo ekvivalenco: +\end_layout + +\begin_deeper +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $\left(\Rightarrow\right)$ +\end_inset + + Dokazano poprej. + Limita se pri prehodu na podzaporedje ohranja. +\end_layout + +\begin_layout Labeling +\labelwidthstring 00.00.0000 +\begin_inset Formula $\left(\Leftarrow\right)$ +\end_inset + + PDDRAA +\begin_inset Formula $a_{n}\not\to L$ +\end_inset + +. + Tedaj +\begin_inset Formula $\exists\varepsilon>0$ +\end_inset + + in podzaporedje +\begin_inset Formula $\left(a_{n_{k}}\right)_{k\in\mathbb{N}}\ni:\forall k\in\mathbb{N}:\left|a_{n_{k}}-K\right|>\varepsilon$ +\end_inset + + (*) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +tu je na +\begin_inset Quotes gld +\end_inset + +Zaporedja 2 +\begin_inset Quotes grd +\end_inset + + napaka, + neenačaj obrne v drugo smer +\end_layout + +\end_inset + +. + Po predpostavki sedaj +\begin_inset Formula $\exists\left(a_{n_{k_{l}}}\right)_{l\in\mathbb{N}}\ni:\lim_{l\to\infty}a_{n_{k_{l}}}=L$ +\end_inset + +. + To pa je v protislovju z (*), + torej je začetna predpostavka +\begin_inset Formula $a_{n}\not\to L$ +\end_inset + + napačna, + torej +\begin_inset Formula $a_{n}\to L$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Subsection +Stekališča +\end_layout + +\begin_layout Definition* +Točka +\begin_inset Formula $s\in\mathbb{R}$ +\end_inset + + je stekališče zaporedje +\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}}\subset\mathbb{R}$ +\end_inset + +, + če v vsaki okolici te točke leži neskončno členov zaporedja. +\end_layout + +\begin_layout Remark* +Pri limiti zahtevamo več; + da izven vsake okolice limite leži le končno mnogo členov. +\end_layout + +\begin_layout Example* +Primeri stekališč. +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $L=\lim_{n\to\infty}a_{n}\Rightarrow L$ +\end_inset + + je stekališče za +\begin_inset Formula $a_{n}$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $0,1,0,1,\dots$ +\end_inset + + stekališči sta +\begin_inset Formula $\left\{ 0,1\right\} $ +\end_inset + + in zaporedje nima limite (ni konvergentno) +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $1,1,2,1,2,3,1,2,3,4,\dots$ +\end_inset + + ima neskončno stekališč, + +\begin_inset Formula $\mathbb{N}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $b_{n}=n-$ +\end_inset + +to racionalno število +\begin_inset Foot +status open + +\begin_layout Plain Layout +Racionalnih števil je števno mnogo, + zato jih lahko linearno uredimo in oštevilčimo +\end_layout + +\end_inset + + ima neskončno stekališč, + +\begin_inset Formula $\mathbb{R}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Remark* +Limita je stakališče, + stekališče pa ni nujno limita. + Poleg tega, + če se spomnimo, + velja, + da vsota konvergentnih zaporedij konvergira k vsoti njunih limit, + ni pa nujno res, + da so stekališča vsote dveh zaporedij paroma vsote stekališč teh dveh zaporedij. + Primer: + +\begin_inset Formula $a_{n}=\left(-1\right)^{n}$ +\end_inset + + in +\begin_inset Formula $b_{n}=-\left(-1\right)^{n}$ +\end_inset + +. + Njuni stekališči sta +\begin_inset Formula $\left\{ -1,1\right\} $ +\end_inset + +, + toda +\begin_inset Formula $a_{n}+b_{n}=0$ +\end_inset + + ima le stekališče +\begin_inset Formula $\left\{ 0\right\} $ +\end_inset + +, + ne pa tudi +\begin_inset Formula $\left\{ 1,-1,2,-2\right\} $ +\end_inset + +. +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\begin_layout Corollary* +sssssssssss +\end_layout + +\end_body +\end_document diff --git a/šola/citati.bib b/šola/citati.bib new file mode 100644 index 0000000..3c34475 --- /dev/null +++ b/šola/citati.bib @@ -0,0 +1,227 @@ +Osebna bibtex knjižnica citatov. +Canonical: ~/projects/r/šola/citati.bib od 2024-07-28 +Stara različica je v ~/projects/sola-gimb-4/citati.bib + +@online{hpstrings, + author = {Nave, Carl Rod}, + title = {{HyperPhysics Concepts: Standing Waves on a String}}, + year = {2016}, + url = {http://hyperphysics.phy-astr.gsu.edu./hbase/Waves/string.html}, + urldate = {2016-11-09} +} +@online{cohen01, + author = {Cohen, Bram}, + title = {BitTorrent - a new P2P app}, + year = {2001}, + url = {http://finance.groups.yahoo.com/group/decentralization/message/3160}, + urldate = {2007-04-15}, + note = "Internet Archive" +} +@online{harrison07, + author = {Harrison, David}, + url = {http://www.bittorrent.org/beps/bep_0000.html}, + urldate = {2023-02-28}, + year = {2008}, + title = {Index of BitTorrent Enhancement Proposals} +} +@online{norberg08, + author = {Loewenstern, Andrew and Norberg, Arvid}, + url = {https://www.bittorrent.org/beps/bep_0005.html}, + urldate = {2023-02-28}, + year = {2020}, + title = {DHT Protocol} +} +@online{jones15, + author = {Jones, Ben}, + url = {https://torrentfreak.com/bittorrents-dht-turns-10-years-old-150607/}, + urldate = {2023-02-28}, + year = {2015}, + title = {BitTorrent’s DHT Turns 10 Years Old} +} +@online{muo11, + author = {Mukherjee, Abhijeet}, + url = {https://www.makeuseof.com/tag/btdigg-trackerless-torrent/}, + urldate = {2023-02-28}, + year = {2011}, + title = {BTDigg: A Trackerless Torrent Search Engine} +} +@online{evseenko11, + author = {Evseenko, Nina}, + url = {http://btdig.com}, + urldate = {2023-02-28}, + year = {2011}, + title = {Btdigg BitTorrent DHT search engine} + +} +@online{griffin17, + author = {Griffin, Andrew}, + url = {https://www.independent.co.uk/tech/torrent-website-download-safe-legal-privacy-i-know-what-you-friends-spying-a7504266.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {'I Know What You Download': Website claims to let people see everything their friends have torrented} +} +@online{ikwyd, + url = {http://iknowwhatyoudownload.com}, + urldate = {2023-02-28}, + title = {I know what you download} +} +@online{cohen08, + author = {Choen, Bram}, + url = {https://www.bittorrent.org/beps/bep_0003.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {The BitTorrent Protocol Specification} +} +@online{norberg09, + author = {Norberg, Arvid}, + url = {https://www.bittorrent.org/beps/bep_0029.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {uTorrent transport protocol} +} +@online{hazel08, + author = {Hazel, Greg and Norberg, Arvid}, + url = {https://www.bittorrent.org/beps/bep_0009.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {Extension for Peers to Send Metadata Files} +} +@online{strigeus08, + author = {Norberg, Arvid and Strigeus, Ludvig and Hazel, Greg}, + url = {https://www.bittorrent.org/beps/bep_0010.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {Extension Protocol} +} +@online{v2, + author = {Cohen, Bram}, + url = {https://www.bittorrent.org/beps/bep_0052.html}, + urldate = {2023-02-28}, + year = {2017}, + title = {The BitTorrent Protocol Specification v2} +} +@incollection{maymounkov2002kademlia, + title={Kademlia: A peer-to-peer information system based on the xor metric}, + author={Maymounkov, Petar and Mazieres, David}, + booktitle={Peer-to-Peer Systems: First InternationalWorkshop, IPTPS 2002 Cambridge, MA, USA, March 7--8, 2002 Revised Papers}, + pages={53--65}, + year={2002}, + publisher={Springer} +} +@inproceedings{pezoa2016foundations, + title={Foundations of JSON schema}, + author={Pezoa, Felipe and Reutter, Juan L and Suarez, Fernando and Ugarte, Mart{\'\i}n and Vrgo{\v{c}}, Domagoj}, + booktitle={Proceedings of the 25th International Conference on World Wide Web}, + pages={263--273}, + year={2016}, + organization={International World Wide Web Conferences Steering Committee} +} +@online{harrison08, + author = {Harrison, David}, + title = {Private Torrents}, + year = {2008}, + url = {https://www.bittorrent.org/beps/bep_0027.html}, + urldate = {2023-02-28}, +} +@techreport{Eastlake2001, + added-at = {2011-05-12T13:55:38.000+0200}, + author = {Eastlake, D. and Jones, P.}, + biburl = {https://www.bibsonomy.org/bibtex/2d2dcad25e57d68db18495f062e955cae/voj}, + interhash = {276256be69453291def2a6fdbed1389d}, + intrahash = {d2dcad25e57d68db18495f062e955cae}, + keywords = {hash identifier sha1}, + month = {9}, + number = 3174, + organization = {IETF}, + publisher = {IETF}, + series = {RFC}, + timestamp = {2013-01-06T13:13:36.000+0100}, + title = {{US Secure Hash Algorithm 1 (SHA1)}}, + type = {RFC}, + year = 2001 +} +@online{dis, + author = {Gams, Matjaž and others}, + year = {2008}, + title = {DIS Slovarček}, + url = {https://dis-slovarcek.ijs.si/}, + urldate = {2023-02-28} +} +@online{rhilip20, + author = {Rhilip}, + year = {2020}, + urldate = {2023-02-28}, + url = {https://github.com/Rhilip/Bencode}, + title = {A pure and simple PHP library for encoding and decoding Bencode data} +} +@conference{Kluyver2016jupyter, + Title = {Jupyter Notebooks -- a publishing format for reproducible computational workflows}, + Author = {Thomas Kluyver and Benjamin Ragan-Kelley and Fernando P{\'e}rez and Brian Granger and Matthias Bussonnier and Jonathan Frederic and Kyle Kelley and Jessica Hamrick and Jason Grout and Sylvain Corlay and Paul Ivanov and Dami{\'a}n Avila and Safia Abdalla and Carol Willing}, + Booktitle = {Positioning and Power in Academic Publishing: Players, Agents and Agendas}, + Editor = {F. Loizides and B. Schmidt}, + Organization = {IOS Press}, + Pages = {87 - 90}, + Year = {2016} +} +@online{sampleih, + author = {The 8472}, + url = {https://www.bittorrent.org/beps/bep_0051.html}, + title = {DHT Infohash Indexing}, + urldate = {2023-02-28}, + year = {2017} +} +@Article{Hunter:2007, + Author = {Hunter, J. D.}, + Title = {Matplotlib: A 2D graphics environment}, + Journal = {Computing in Science \& Engineering}, + Volume = {9}, + Number = {3}, + Pages = {90--95}, + abstract = {Matplotlib is a 2D graphics package used for Python for + application development, interactive scripting, and publication-quality + image generation across user interfaces and operating systems.}, + publisher = {IEEE COMPUTER SOC}, + doi = {10.1109/MCSE.2007.55}, + year = 2007 +} +@online{norberg14, + author = {Norberg, Arvid}, + title = {DHT Security extension}, + url = {https://www.bittorrent.org/beps/bep_0042.html}, + urldate = {2023-02-28}, + year = {2016} +} +@InProceedings{10.1007/3-540-45748-8_24, + author="Douceur, John R.", + editor="Druschel, Peter + and Kaashoek, Frans + and Rowstron, Antony", + title="The Sybil Attack", + booktitle="Peer-to-Peer Systems", + year="2002", + publisher="Springer Berlin Heidelberg", + address="Berlin, Heidelberg", + pages="251--260", + abstract="Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these ``Sybil attacks'' is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.", + isbn="978-3-540-45748-0" +} +@book{cedilnik12, + place={Radovljica}, + title={Matematični Priročnik}, + publisher={Didakta}, + author={Cedilnik, Anton and Razpet, Nada and Razpet, Marko}, + year={2012} +} +@online{wikihashuniformity, + author="{Wikipedia contributors}", + title={Hash function}, + url={https://w.wiki/An3L}, + urldate={2024-07-29}, + year={2024} +} +@online{maxmindgeoip2, + author={MaxMind}, + title={GeoLite2 Free Geolocation Data}, + url={https://dev.maxmind.com/geoip/geolite2-free-geolocation-data}, + urldate={2024-07-31}, + year={2024} diff --git a/šola/članki/dht/.gitignore b/šola/članki/dht/.gitignore new file mode 100644 index 0000000..abd26b3 --- /dev/null +++ b/šola/članki/dht/.gitignore @@ -0,0 +1,3 @@ +*.svg +*.png +*.tsv diff --git a/šola/članki/dht/dokument.lyx b/šola/članki/dht/dokument.lyx new file mode 100644 index 0000000..af668ed --- /dev/null +++ b/šola/članki/dht/dokument.lyx @@ -0,0 +1,2306 @@ +#LyX 2.4 created this file. For more info see https://www.lyx.org/ +\lyxformat 620 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass paper +\begin_preamble +% for subfigures/subtables +\usepackage[caption=false,font=footnotesize]{subfig} +\usepackage{textcomp} +\usepackage[ + type={CC}, + modifier={by-sa}, + version={3.0}, +]{doclicense} +\usepackage{bera}% optional: just to have a nice mono-spaced font +\usepackage{listings} +\usepackage{xcolor} +\lstset{ + extendedchars=true, + literate={č}{{\v{c}}}1 {ž}{{\v{z}}}1 {š}{{\v{s}}}1, +} + +\colorlet{punct}{red!60!black} +\definecolor{background}{HTML}{EEEEEE} +\definecolor{delim}{RGB}{20,105,176} +\colorlet{numb}{magenta!60!black} + +\lstdefinelanguage{json}{ + basicstyle=\normalfont\ttfamily, + numbers=left, + numberstyle=\scriptsize, + stepnumber=1, + numbersep=8pt, + showstringspaces=false, + breaklines=true, + frame=lines, + backgroundcolor=\color{background}, + literate= + *{0}{{{\color{numb}0}}}{1} + {1}{{{\color{numb}1}}}{1} + {2}{{{\color{numb}2}}}{1} + {3}{{{\color{numb}3}}}{1} + {4}{{{\color{numb}4}}}{1} + {5}{{{\color{numb}5}}}{1} + {6}{{{\color{numb}6}}}{1} + {7}{{{\color{numb}7}}}{1} + {8}{{{\color{numb}8}}}{1} + {9}{{{\color{numb}9}}}{1} + {:}{{{\color{punct}{:}}}}{1} + {,}{{{\color{punct}{,}}}}{1} + {\{}{{{\color{delim}{\{}}}}{1} + {\}}{{{\color{delim}{\}}}}}{1} + {[}{{{\color{delim}{[}}}}{1} + {]}{{{\color{delim}{]}}}}{1}, +} +\end_preamble +\options journal +\use_default_options false +\maintain_unincluded_children no +\language slovene +\language_package babel +\inputencoding utf8 +\fontencoding auto +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_roman_osf false +\font_sans_osf false +\font_typewriter_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures false +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command bibtex +\index_command default +\float_placement H +\float_alignment class +\paperfontsize default +\spacing single +\use_hyperref true +\pdf_title "Your Title" +\pdf_author "Your Name" +\pdf_bookmarks true +\pdf_bookmarksnumbered true +\pdf_bookmarksopen true +\pdf_bookmarksopenlevel 1 +\pdf_breaklinks false +\pdf_pdfborder true +\pdf_colorlinks false +\pdf_backref false +\pdf_pdfusetitle false +\pdf_quoted_options "pdfpagelayout=OneColumn, pdfnewwindow=true, pdfstartview=XYZ, plainpages=false" +\papersize default +\use_geometry true +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 0 +\use_formatted_ref 0 +\use_minted 0 +\use_lineno 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\leftmargin 0.5cm +\topmargin 0.5cm +\rightmargin 0.5cm +\bottommargin 1.25cm +\headheight 0.5cm +\headsep 0.5cm +\footskip 0.5cm +\columnsep 0.5cm +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style german +\dynamic_quotes 0 +\papercolumns 2 +\papersides 1 +\paperpagestyle default +\tablestyle default +\tracking_changes false +\output_changes false +\change_bars false +\postpone_fragile_content false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\docbook_table_output 0 +\docbook_mathml_prefix 1 +\end_header + +\begin_body + +\begin_layout Title +Kaj prenašamo s protokolom BitTorrent? +\end_layout + +\begin_layout Author +Anton Luka Šijanec, + +\begin_inset CommandInset href +LatexCommand href +name "anton@sijanec.eu" +target "anton@sijanec.eu" +type "mailto:" +literal "true" + +\end_inset + + +\end_layout + +\begin_layout Institution +Fakulteta za računalništvo in informatiko Univerze v Ljubljani +\end_layout + +\begin_layout Abstract +V članku predstavimo metodo za učinkovito in za omrežje neinvazivno metodo prenašanja metapodatkov iz pomožnega omrežja Kademlia mainline DHT protokola BitTorrent za izmenjavo datotek. + Sledi pregled/analiza z opisano metodo pridobljenih metapodatkov o datotekah na voljo v omrežju BitTorrent. +\end_layout + +\begin_layout Abstract +Porazdeljene razpršilne tabele (angl. + distributed hash table) so razpršilne tabele, + ki podatke, + ponavadi so to dokumenti, + strukturirani kot vrednost in njej pripadajoči ključ, + hranijo distribuirano na več vozliščih, + na katerih se podatki shranjujejo. + V računalniških sistemih se DHT uporablja za hrambo podatkov v omrežjih P2P (angl. + peer to peer), + kjer se podatki vseh uporabnikov enakomerno porazdelijo med vozlišča in so tako decentralizirani in preprosto dostopni članom omrežja. + Ker se podatki izmenjujejo znotraj omrežja na vozliščih, + ki z izvorom in destinacijo podatkov niso povezani, + jih lahko vozlišča v velikih količinah shranjujejo za potrebe statistične analize omrežja. +\end_layout + +\begin_layout Abstract +V raziskavi preverimo praktično zmožnost pridobivanja velike količine podatkov v omrežju BitTorrent za P2P izmenjavo datotek, + nato še analiziramo pridobljene podatke. + Vsaka poizvedba po seznamu imetnikov datotek vsebuje ključ podatka v DHT in se prenese preko okoli +\begin_inset Formula $\log_{2}n$ +\end_inset + + vozlišč, + kjer je +\begin_inset Formula $n$ +\end_inset + + število vseh uporabnikov v omrežju. + Ker vsaka poizvedba obišče tako veliko število vozlišč, + lahko med poizvedbo eno drugače nepovezano vozlišče prejme veliko obstoječih ključev v omrežju, + ki jih lahko uporabi za prenos metapodatkov v omrežju BitTorrent. +\end_layout + +\begin_layout Abstract +Osredotočili smo se le na na pridobivanje metapodatkov v omrežju BitTorrent, + samih datotek, + na katere se le-ti metapodatki sklicujejo in so v omrežju na voljo, + ker jih ponujajo drugi računalniki, + pa tako vsled tehničnih (njihove ogromne skupne velikosti) kot tudi pravnih razlogov (avtorsko zaščitena in protizakonita vsebina) nismo prenašali. + Metapodatki konceptualno sicer niso shranjeni v DHT (namesto metapodatkov o datotekah so v omrežju shranjeni seznami računalnikov, + od katerih si metapodatke lahko prenesemo), + vendar odkrivanje njihovega obstoja omogoči DHT. +\end_layout + +\begin_layout Abstract +S pridobljenimi metapodatki ugotovimo, + kateri odjemalci so najpopularnejši ter kakšna je razporeditev vsebine glede na tip datotek, + ki je na voljo preko protokola BitTorrent. +\end_layout + +\begin_layout Keywords +porazdeljena razpršilna tabela, + porazdeljeni sistemi, + omrežje P2P, +\end_layout + +\begin_layout Keywords +podatkovno rudarjenje, + BitTorrent +\end_layout + +\begin_layout Section +Introduction +\end_layout + +\begin_layout Subsection +Distribucija datotek po principu P2P +\end_layout + +\begin_layout Standard +Koncept P2P (angl. + +\shape italic +peer-to-peer +\shape default +) predstavlja alternativen način distribucije identičnih datotek večim odjemalcem. + Namesto enega strežnika, + ki iste podatke odjemalcem pošlje vsakič znova, + v omrežjih P2P za distribucijo datotek vsak odjemalec podatke tako prejema kot tudi pošilja. + Odjemalec prejeto vsebino tudi sam deli drugim te vsebine željanim odjemalcem, + s čimer razbremeni ostale odjemalce. +\end_layout + +\begin_layout Standard +Odjemalec za druge izve s pomočjo centralnega strežnika ali pa drugačnega signalizacijskega protokola. + Ker se povezujejo neposredno, + medsebojno poznajo svoje internetne naslove. +\end_layout + +\begin_layout Subsection +Protokol BitTorrent +\end_layout + +\begin_layout Standard +Od 2008 +\begin_inset CommandInset citation +LatexCommand cite +key "harrison07" +literal "false" + +\end_inset + + je eden izmed popularnejših protokolov za P2P distribucijo BitTorrent, + razvit že 2001 +\begin_inset CommandInset citation +LatexCommand cite +key "cohen01" +literal "false" + +\end_inset + +. + Zaradi razširljive zasnove ga je moč dopolnjevati — + dodajati nove funkcije. + Sprva je BitTorrent temeljil na centralnih strežnikih za koordinacijo rojev, + od leta 2005 pa z uvedbo protokola DHT lahko deluje povsem neodvisno. +\begin_inset CommandInset citation +LatexCommand cite +key "jones15" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float table +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\noindent +\align center +\begin_inset Tabular +<lyxtabular version="3" rows="8" columns="3"> +<features tabularvalignment="middle" tabularwidth="100col%"> +<column alignment="center" valignment="top" width="0pt"> +<column alignment="center" valignment="top" width="0pt"> +<column alignment="center" valignment="top" width="0pt" varwidth="true"> +<row> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Pojem +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Angleško +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Razlaga +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +soležnik +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +peer +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +odjemni program na računalniku, + za povezavo nanj potrebujemo IP naslov in vrata +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +roj +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +swarm +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +več soležnikov, + ki prenašajo datoteke nekega torrenta +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +torrent/ +\begin_inset Newline newline +\end_inset + +metainfo +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +torrent/ +\begin_inset Newline newline +\end_inset + +metainfo +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +datoteka z metapodatki datotek; + imena, + velikosti, + zgoščene vrednosti in drugo +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +sledilnik +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +tracker +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +koordinacijski strežnik z naslovi soležnikov v rojih +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +košček +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +piece +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +delček datoteke konstantne dolžine +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +infohash +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +infohash +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +zgoščena vrednost serializiranih podatkov pod ključem +\family typewriter +info +\family default + v torrentu, + ki unikatno opišejo ključne metapodatke o torrentu +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +objavi +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +announce +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +pošiljanje obvestila v DHT ali na sledilnik, + da se odjemalec želi priključiti nekemu roju +\end_layout + +\end_inset +</cell> +</row> +</lyxtabular> + +\end_inset + + +\begin_inset Caption Standard + +\begin_layout Plain Layout +Slovar pojmov BitTorrenta +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Za prenos je treba poznati metapodatke o obstoječih datotekah, + ki so shranjeni v t. + i. + obliki .torrent, + strojno berljivi z bencoding serializirani datoteki. + Vsebujejo vsaj imena in poti datotek ter njihove zgoščene vrednosti, + ime torrenta, + lastnosti prenosa in velikost koščka. +\end_layout + +\begin_layout Standard +V raziskavi ne iščemo soležnikov s sledilniki in ne prenašamo datotek, + temveč samo prenašamo in analiziramo metapodatke. +\end_layout + +\begin_layout Subsection +Protokol Kademlia mainline DHT +\end_layout + +\begin_layout Standard +V BitTorrent je za iskanje soležnikov v roju uporabljen DHT (angl. + +\shape italic +distributed hash table +\shape default +), + ki odpravi odvisnost od sledilnika. +\end_layout + +\begin_layout Standard +\begin_inset Float table +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\noindent +\align center +\begin_inset Tabular +<lyxtabular version="3" rows="6" columns="3"> +<features tabularvalignment="middle" tabularwidth="100col%"> +<column alignment="center" valignment="top" width="0pt"> +<column alignment="center" valignment="top" width="0pt"> +<column alignment="center" valignment="top" width="0pt" varwidth="true"> +<row> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Pojem +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Angleško +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Razlaga +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +vozlišče +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +node +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +odjemni program na računalniku +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +usmerjevalna +\begin_inset Newline newline +\end_inset + +tabela +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +routing +\begin_inset Newline newline +\end_inset + +table +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +seznam vozlišč (IP, + vrata, + ID), + ki ga hrani posamezno vozlišče +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +ID vozlišča +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +node ID +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +160-bitna ob zagonu generirana naključna vozlišču pripadajoča številka +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +merilo +\begin_inset Newline newline +\end_inset + +razdalje +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +distance +\begin_inset Newline newline +\end_inset + +metric +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +funkcija (XOR), + ki izrazi razdaljo med vozliščema kot 160-bitno številko +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +koš +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +bucket +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +element usmerjevalne tabele, + ki glede na merilo razdalje vsebuje bližnja vozlišča +\end_layout + +\end_inset +</cell> +</row> +</lyxtabular> + +\end_inset + + +\begin_inset Caption Standard + +\begin_layout Plain Layout +Slovar pojmov Kademlie. + Slovenski prevodi niso ustaljeni. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Na visokem nivoju gre za abstraktno razpršilno tabelo, + shranjeno porazdeljeno na velikem omrežju vozlišč. + Podpira naslednji operaciji +\begin_inset CommandInset citation +LatexCommand cite +key "norberg08" +literal "false" + +\end_inset + +: +\end_layout + +\begin_layout Paragraph + +\family typewriter +get_peers +\end_layout + +\begin_layout Standard +Vrne seznam soležnikov (IP naslov in vrata) za torrent, + opisan z njegovim infohashom. +\end_layout + +\begin_layout Paragraph + +\family typewriter +announce +\begin_inset Note Note +status open + +\begin_layout Plain Layout +qbittorrent pravi sporoči, + v deluge in transmission nisem našel prevoda +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +V seznam soležnikov za torrent, + opisan z njegovim infohashom, + vstavi IP naslov in vrata pošiljatelja zahteve. +\end_layout + +\begin_layout Standard +V raziskavi s sodelovanjem v DHT prestrezamo obstoječe ključe v razpršilni tabeli, + z njimi pridobimo soležnike, + od katerih prenesemo metapodatke o torrentih za kasnejšo analizo. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/predst/dht.svg + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Shematski prikaz DHT +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Opis standardov +\end_layout + +\begin_layout Paragraph +Serializacija bkodiranje +\family typewriter +(bencoding) +\end_layout + +\begin_layout Standard +V BEP-0003 +\begin_inset CommandInset citation +LatexCommand cite +key "cohen08" +literal "false" + +\end_inset + + je opisan bencoding. + Z njim je serializirana večina struktur BitTorrenta in Kademlie. + Bkodiranje je podobno bolj znanemu JSONu +\begin_inset CommandInset citation +LatexCommand cite +key "pezoa2016foundations" +literal "false" + +\end_inset + + — + vsebuje štiri podatkovne tipe: + niz, + število, + seznam in slovar. +\end_layout + +\begin_layout Paragraph +Datoteka metainfo/.torrent +\end_layout + +\begin_layout Standard +Za distribucijo vsebine s protokolom BitTorrent ustvarimo .torrent datoteko, + bkodiran slovar z metapodatki, + nujnimi za prenos datotek. + Za raziskavo so pomembni metapodatki pod ključem +\family typewriter +info +\family default +: +\begin_inset CommandInset citation +LatexCommand cite +key "cohen08" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +private +\family default +: + prepoved objavljanja preko DHT, + le preko sledilnikov (ti torrenti niso zajeti v raziskavi) +\begin_inset CommandInset citation +LatexCommand cite +key "harrison08" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +name +\family default +: + ime torrenta oz. + datoteke za enodatotečne torrente +\end_layout + +\begin_layout Itemize + +\family typewriter +piece length +\family default +: + velikost koščka — + datoteke so spojene skupaj in razdeljene na enako velike koščke +\end_layout + +\begin_layout Itemize + +\family typewriter +pieces +\family default +: + niz dolžine +\begin_inset Formula $20n$ +\end_inset + + ( +\begin_inset Formula $n$ +\end_inset + + je število koščkov) s SHA-1 vrednostmi koščkov +\begin_inset CommandInset citation +LatexCommand cite +key "Eastlake2001" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +length +\family default +: + dolžina datoteke za enodatotečne torrente +\end_layout + +\begin_layout Itemize + +\family typewriter +files +\family default +: + seznam datotek v večdatotečnem torrentu — + vsaka datoteka je predstavljena kot slovar z +\family typewriter +length +\family default + in +\family typewriter +path +\family default +. +\end_layout + +\begin_layout Standard +Kdor pozna infohash, + lahko od soležnika prenese metainfo in posledično tudi pripadajoče datoteke. + Roj najde in se vanj vključi s poizvedbo v DHT, + saj je infohash ključ v tej razpršilni tabeli +\begin_inset CommandInset citation +LatexCommand cite +key "hazel08" +literal "false" + +\end_inset + +. + Infohash običajno oblikujemo v t. + i. + magnetno povezavo (magnet URI): + +\family typewriter + magnet:?dn= +\series bold +ime torrenta +\series default +&xt=urn:btih: +\series bold +infohash +\end_layout + +\begin_layout Standard +Druga različica BitTorrenta ima drugačno metainfo strukturo s podobnimi podatki. + Uporablja SHA-256 in namesto +\family typewriter +pieces +\family default + uporablja +\family typewriter +merkle hash tree +\family default + +\begin_inset CommandInset citation +LatexCommand cite +key "v2" +literal "false" + +\end_inset + + za zgoščene vrednosti datotek. +\end_layout + +\begin_layout Paragraph +Graf DHT +\end_layout + +\begin_layout Standard +DHT vzdržuje sezname soležnikov v roju vseh obstoječih torrentov. + Vozlišča komunicirajo preko UDP in so del velikega usmerjenega grafa, + vsako s +\begin_inset Formula $K\log_{2}n$ +\end_inset + + (konstanta +\begin_inset Formula $K=8$ +\end_inset + +, + +\begin_inset Formula $n$ +\end_inset + + je število vseh vozlišč na svetu) povezavami — + vpisi v usmerjevalno tabelo. +\end_layout + +\begin_layout Standard +Vozlišče skrbi za urejeno usmerjevalno tabelo dosegljivih +\begin_inset Foot +status open + +\begin_layout Plain Layout +dvosmerna komunikacija zaradi NAT ni samoumevna +\end_layout + +\end_inset + + vozlišč v koših; + +\begin_inset Formula $i$ +\end_inset + +ti koš hrani do +\begin_inset Formula $K$ +\end_inset + + med +\begin_inset Formula $2^{i}$ +\end_inset + + in +\begin_inset Formula $2^{i-1}$ +\end_inset + + po merilu XOR oddaljenih vozlišč, + torej je shranjenih veliko bližnjih in malo zelo oddaljenih vozlišč. +\begin_inset CommandInset citation +LatexCommand cite +key "maymounkov2002kademlia" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Paragraph +Poizvedbe po grafu +\end_layout + +\begin_layout Standard +Sprehod po grafu med poljubnima vozliščema je torej dolg v povprečju +\begin_inset Formula $\log n$ +\end_inset + + ( +\begin_inset Formula $n$ +\end_inset + + kot prej). + Roj torrenta z infohashom +\begin_inset Formula $x$ +\end_inset + + je shranjen na vozliščih z ID blizu +\begin_inset Formula $x$ +\end_inset + +, + tedaj ima poizvedba po soležnikih/objavljanje soležnika časovno kompleksnost +\begin_inset Formula $O\left(\log n\right)$ +\end_inset + +. + Za pridobitev seznama soležnikov torrenta pošljemo bkodiran UDP paket tipa +\family typewriter +get_peers +\family default + +\begin_inset Formula $t$ +\end_inset + + +\begin_inset Foot +status open + +\begin_layout Plain Layout +odvisno od implementacije +\end_layout + +\end_inset + + vozliščem iz usmerjevalne tabele, + ki so blizu infohasha. + Pozvana vozlišča odgovorijo s seznamom do +\begin_inset Formula $K$ +\end_inset + + temu infohashu najbližjih vozlišč in seznamom soležnikov za ta torrent, + če ga imajo. + Novodobljenim vozliščem spet pošljemo poizvedbo +\family typewriter +get_peers +\family default + in postopek nadaljujemo, + dokler ne najdemo nekaj infohashu najbližjih vozlišč. + V tista pošiljamo objave in od njih še naprej prejemamo informacije o roju. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\align center +\begin_inset Graphics + filename Dht_example_SVG.svg + width 50col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Usmerjevalna-tabela-za" + +\end_inset + +Usmerjevalna tabela za vozlišče 110 (koši so osenčeni) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Metode +\end_layout + +\begin_layout Standard +Vsaka poizvedba obišče +\begin_inset Formula $\log n$ +\end_inset + + vozlišč, + torej vsako vozlišče v DHT prejema ogromno ključev — + infohashov. + V raziskavi v C spišemo program travnik, + nepopolno implementacijo odjemalca BitTorrent s poudarkom na DHT. + Osredotočimo se na zajem metapodatkov iz ključev, + ki jih prejmemo s sodelovanjem v omrežju. +\end_layout + +\begin_layout Standard +Ko vozlišče, + na katerem teče travnik, + prejme paket z infohashom, + ga doda v seznam željenih torrentov. + Neprestano posodablja roje torrentov znanih infohashov in se povezuje na soležnike iz njih, + dokler mu ne uspe prenesti metapodatkov torrenta oziroma dokler ne obupa/preteče 256 sekundni TTL torrenta. + Izdeluje .torrent datoteke z najdenimi metapodatki in internetnim naslovom ter ime programske opreme soležnika, + od katerega je metapodatke prejel. + Ne objavlja se v roj, + ker ne redistribuira niti metapodatkov niti datotek. +\end_layout + +\begin_layout Standard +Da program prvič začne sodelovati z omrežjem — + da ga sosednja vozlišča vpišejo v svoje usmerjevalne tabele — + prenese metapodatke vgrajenega torrenta +\family typewriter +Big Buck Bunny +\family default +. +\end_layout + +\begin_layout Standard +Za implementacijo spišemo knjižnico za bkodiranje in bdekodiranje, + knjižnico za DHT in nekaj funkcij za prenos metapodatkov od soležnikov preko TCP. +\end_layout + +\begin_layout Standard +Za obdelavo dobljenih torrent datotek uporabimo Jupyter Notebook +\begin_inset CommandInset citation +LatexCommand cite +key "Kluyver2016jupyter" +literal "false" + +\end_inset + + in spišemo preprosto knjižnico za razčlenjevanje .torrent metainfo datotek, + ki jih generira travnik. +\end_layout + +\begin_layout Section +Rezultati +\end_layout + +\begin_layout Subsection +Zajem +\end_layout + +\begin_layout Standard +Podatke smo zajemali iz različnih lokacij in v različnih časovnih obdobjih: +\end_layout + +\begin_layout Itemize +januarja in februarja 2023: +\end_layout + +\begin_deeper +\begin_layout Itemize +16 dni: + domači optični priključek v Sloveniji (T-2): + 47863 torrentov (3084321 datotek, + 259 TiB, + 29 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +travnik +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Itemize +31 dni VPS v Grčiji (grNet) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + +: + +\family roman +\series medium +\shape up +\size normal +\emph off +\nospellcheck off +\bar no +\strikeout off +\xout off +\uuline off +\uwave off +\noun off +\color none +412846 +\family default +\series default +\shape default +\size default +\emph default +\nospellcheck default +\bar default +\strikeout default +\xout default +\uuline default +\uwave default +\noun default +\color inherit + torrentov (17101702 datotek, + 1881 TiB, + 6 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +okeanos +\end_layout + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +XX dni VPS v Grčiji (grNet) 2: + 342220 torrentov () +\begin_inset Note Note +status open + +\begin_layout Plain Layout +oliwerix +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Itemize +5 dni junija 2024 na domačem optičnem priključku v Sloveniji (T-2): + 62110 torrentov (3725125 datotek, + 345 TiB, + 7 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +2024b +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Primer strukture torrent datoteke z metapodatki +\end_layout + +\begin_layout Standard +Spodaj je iz bencoding v JSON pretvorjena metainfo datoteka prevzetega torrenta z infohashom +\family typewriter +696802a16728636cd72617e4cd7b64e3ca314e71 +\family default +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +lstinputlisting[language=json,firstnumber=1, + numbers=none, + breaklines=true, + basicstyle= +\backslash +tiny]{../../../../sola-gimb-4/inf/rn/predst/torrent.json} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Analiza +\end_layout + +\begin_layout Subsubsection +Odjemalci, + od katerih so bili prejeti torrenti +\end_layout + +\begin_layout Standard +Imenom programom odstranimo različico in jim ročno normaliziramo ime +\begin_inset Foot +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +textmu Torrent +\end_layout + +\end_inset + + se sicer pojavi dvakrat, + enkrat ima znak mikro, + enkrat pa grško črko mu. + Unicode namreč ta dva znaka, + ki sicer izgledata identično, + hrani pod dvema različnima kodama. +\end_layout + +\end_inset + + ter prikažemo njihovo gostoto v populaciji. +\begin_inset CommandInset citation +LatexCommand cite +key "Hunter:2007" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/odjemalci_1_ods.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentacija odjemalcev, + ki predstavljajo vsaj en odstotek populacije, + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Različice odjemalca +\family typewriter +qBittorrent +\family default + skozi čas +\end_layout + +\begin_layout Standard +Primerjava porazdelitve različic po zgornji analizi najpopularnejšega odjemalca na +\begin_inset Formula $\log_{10}$ +\end_inset + + skali pokaže višanje različic skozi čas. + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +Različice smo razvrstili s pythonsko funkcijo +\family typewriter +packaging.version.Version +\family default +. +\end_layout + +\end_inset + + V obeh letih smo prejeli torrente od skupno 88 različnih inačic qBittorrenta. + V 2023 smo največ torrentov prejeli od odjemalcev različice 4.5.0, + v 2024 pa od odjemalcev različice 4.6.3. + +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Note Note +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/r/šola/članki/dht/verzije2324.png + width 100col% + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Graphics + filename /root/projects/r/šola/članki/dht/verzije2324promil.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Primerjava distribucij različic odjemalca +\family typewriter +qBittorrent +\family default + med 2023 (plavo) in 2024 (roza), + ki predstavljajo vsaj promil populacije (delež). +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Geolokacija IP naslovov odjemalcev +\end_layout + +\begin_layout Standard +Z uporabo podatkovne zbirke MaxMind GeoLite2 +\begin_inset CommandInset citation +LatexCommand cite +key "maxmindgeoip2" +literal "false" + +\end_inset + + IP naslovom, + od katerih smo prejeli torrente, + določimo izvirno državo. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename countries_procent.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentativnost držav, + iz katerih smo prenesli metainfo, + na linearni skali. + Prikazane so le države, + iz katerih izvira vsaj odstotek populacije. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Predstavnost ključev v prejetih slovarjih +\family typewriter +info +\end_layout + +\begin_layout Standard +Poleg standardnih obveznih nekateri torrenti vsebujejo tudi dodatne metapodatke v slovarju info. + Pogostost slednjih prikazuje spodnji grafikon. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/vsi_ključi.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentacija ključev v slovarju +\family typewriter +info +\family default + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Tipi datotek, + ki se prenašajo v torrentih +\end_layout + +\begin_layout Standard +Iz končnice datoteke izvemo tip datoteke. + Vsakemu torrentu priredimo reprezentativen tip, + tisti, + ki po velikosti prevladuje v torrentu. + Glede na število torrentov z nekim reprezentativnim tipom kvantificiramo pogostost tega datotečnega tipa za tipe, + ki zavzemajo vsaj promil populacije. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/reprezentativni_.1_ods.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentativni tipi torrentov, + ki predstavljajo vsaj en promil populacije, + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Razvidno je, + da je večina torrentov namenjena prenosu videovsebin, + zvočnih datotek in stisnjenih arhivov. +\end_layout + +\begin_layout Standard +Če bi za določilo pojavnosti tipa uporabili število datotek, + bi prevladovali tipi vsebin, + ki so ponavadi preneseni kot kopica datotek, + denimo slike (diagram v prilogi na sliki +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Pojavnost-tipa-kot" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +), + če pa bi za določilo pojavnosti tipa uporabili velikost datotek tega tipa, + pa bi prevladovali tisti tipi, + ki zasedajo več prostora. + V tem primeru bi npr. + videovsebine zaradi svoje velikosti občutno presegale digitalne knjige (diagram v prilogi na sliki +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Pojavnost-tipa-kot-velikost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +). +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Subsubsection +\begin_inset CommandInset label +LatexCommand label +name "subsec:Porazdeljenost-infohashov" + +\end_inset + +Porazdeljenost infohashov +\end_layout + +\begin_layout Plain Layout +Zaradi delovanja poizvedb v DHT pričakujemo, + da je porazdelitev infohashov po celotnem sprektru števil z intervala +\begin_inset Formula $\left[0,2^{160}-1\right]$ +\end_inset + + gostejša okoli IDja vozlišča, + ki ga je med prenašanjem imelo naše iskalno vozlišče. + IDje smo izbrali naključno na vsaki merilni lokaciji in jih med meritvijo tudi nekajkrat zamenjali, + zato spodnjem grafikonu opazimo vrhove tam, + kjer so bili naši IDji med zajemom podatkov. +\end_layout + +\begin_layout Plain Layout +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Razporeditev pridobljenih infohashov na spektru vseh infohashov +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Diskusija +\end_layout + +\begin_layout Paragraph +Statistična kvaliteta vzorca +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +V razdelku +\begin_inset CommandInset ref +LatexCommand ref +reference "subsec:Porazdeljenost-infohashov" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + opazimo neenakomerno porazdeljenost infohashov, + kar je posledica načina vzorčenja torrentov. + Vsa populacija ima namreč zaradi delovanja zgoščevalne funkcije SHA-1 homogeno porazdeljene infohashe. + Kljub temu trdimo, + da pridobljen vzorec torrentov dobro predstavlja celotno populacijo. + +\end_layout + +\end_inset + +Zaradi lastnosti uniformne porazdelitve zgoščevalne funkcije +\begin_inset CommandInset citation +LatexCommand cite +key "wikihashuniformity" +literal "false" + +\end_inset + + mesto infohasha na intervalu vseh možnih infohashov ni odvisno od metapodatkov. + Kot posledico načina vzorčenja z DHT pričakujemo, + da je porazdelitev infohashov prejetih torrentov po celotnem sprektru števil z intervala +\begin_inset Formula $\left[0,2^{160}-1\right]$ +\end_inset + + gostejša okoli IDja vozlišča, + ki ga je med prenašanjem imelo naše iskalno vozlišče. + IDje smo tekom raziskave izbrali naključno na vsaki merilni lokaciji in jih med meritvijo tudi nekajkrat zamenjali. + Kljub temu je vsled nepovezanosti vsebine in infohasha vzorec še vedno statistično reprezentativen. + Zajem ne more biti pristranski glede na metapodatke, + ker nikjer v procesu zajema ne obravnavamo torrentov glede na metainfo, + temveč le glede na infohash. +\end_layout + +\begin_layout Paragraph +Težava z zajemom podatkov +\end_layout + +\begin_layout Standard +Vsled majhne velikosti UDP paketov DHT glavno ozko grlo pri zajemu predstavlja število paketov, + ki jih mrežna oprema lahko posreduje v sekundi. + Domača optična povezava dopušča do okoli 2000 paketov na sekundo na naključno porazdeljene IP naslove, + odjemno mesto na VPS pa je imelo to omejitev veliko višjo, + zato smo tam v istem časovnem intervalu shranili veliko več torrent datotek. +\end_layout + +\begin_layout Paragraph +Etičnost in legitimnost rudarjenja podatkov +\end_layout + +\begin_layout Standard +Čeprav gre za izrazito osebne podatke, + se morajo uporabniki BitTorrent omrežja zavedati, + da so njihovi prenosi +\shape italic +a priori +\shape default + javni, + tudi če jih nihče aktivno ne zajema. + Nekateri BitTorrent odjemalci uporabnike ob prvem zagonu o tem obvestijo. +\end_layout + +\begin_layout Section +Priloge +\end_layout + +\begin_layout Standard +Izvorna koda programa travnik in ipynb datotek za analizo podatkov je na voljo na +\begin_inset CommandInset href +LatexCommand href +name "http://ni.šijanec.eu./sijanec/travnik" +target "http://ni.šijanec.eu./sijanec/travnik" +literal "false" + +\end_inset + +. +\end_layout + +\begin_layout Standard +Korpus zajetih metapodatkov je na voljo na +\begin_inset CommandInset href +LatexCommand href +name "rsync://b.sjanec.eu./travnik" +target "rsync://b.sijanec.eu./travnik" +type "other" +literal "false" + +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename po_številu_datotek.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Pojavnost-tipa-kot" + +\end_inset + +Pojavnost tipa kot število datotek +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/po_velikosti_datotek.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Pojavnost-tipa-kot-velikost" + +\end_inset + +Pojavnost tipa kot velikost datotek (tipi, + ki zavzamejo vsaj odstotek populacije) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset CommandInset bibtex +LatexCommand bibtex +btprint "btPrintCited" +bibfiles "/root/projects/r/šola/citati" +options "IEEEtran" +encoding "default" + +\end_inset + + +\end_layout + +\begin_layout Section* +Viri slik +\end_layout + +\begin_layout Itemize +Slika +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Usmerjevalna-tabela-za" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +: + Limaner: + nespremenjena, + izvorna pod CC BY-SA +\end_layout + +\begin_layout Section* +Dovoljenje +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +doclicenseImage[imagewidth=2cm] +\end_layout + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +TODO: + preštej datoteke v oliwerix, + še enkrat nariši vse grafe upoštevajoč vse torrente, + primerjaj verzije med travnik in 2024b +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document diff --git a/šola/članki/dht/makefile b/šola/članki/dht/makefile new file mode 100644 index 0000000..5be42f0 --- /dev/null +++ b/šola/članki/dht/makefile @@ -0,0 +1,13 @@ +all: Dht_example_SVG.svg bt.svg + +Dht_example_SVG.svg: + wget https://upload.wikimedia.org/wikipedia/commons/6/63/Dht_example_SVG.svg + +infohash.png: # tole je treba pognati na strežniku b + ./infohash.sh + +bt.svg: + wget -O- https://upload.wikimedia.org/wikipedia/commons/0/09/BitTorrent_network.svg | sed -e s/Downloader/Soležnik/ -e s/Uploader/Soležnik/ > bt.svg + +clean: + rm *.svg *.png *.tsv |