diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-02-24 03:18:58 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-02-24 04:39:07 +0400 |
| commit | bc5c88fc6d6220775059a2d02d49f7b81591785b (patch) | |
| tree | fcdfc05e68f486a2021b912ad83a7fd2de915db9 | |
Добавил первую лабораторную работу
| -rw-r--r-- | .gitignore | 14 | ||||
| -rw-r--r-- | lab1/lab1.py | 135 | ||||
| -rw-r--r-- | lab1/report/SCWorks.cls | 991 | ||||
| -rw-r--r-- | lab1/report/images/mat3.png | bin | 0 -> 506483 bytes | |||
| -rw-r--r-- | lab1/report/images/mat4.png | bin | 0 -> 514473 bytes | |||
| -rw-r--r-- | lab1/report/images/mat4_id.png | bin | 0 -> 615095 bytes | |||
| -rw-r--r-- | lab1/report/lab1.tex | 459 | ||||
| -rw-r--r-- | lab1/report/preamble.sty | 51 | ||||
| -rw-r--r-- | lab1/report/titlepage.tex | 54 |
9 files changed, 1704 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..4f359ad --- /dev/null +++ b/.gitignore @@ -0,0 +1,14 @@ +venv +.DS_Store +_minted* +*.aux +*.bbl +*.bcf +*.blg +*.fdb_latexmk +*.fls +*.log +*.xml +*.gz +*.toc +*.pdf
\ No newline at end of file diff --git a/lab1/lab1.py b/lab1/lab1.py new file mode 100644 index 0000000..bc4bd00 --- /dev/null +++ b/lab1/lab1.py @@ -0,0 +1,135 @@ +import numpy as np +from dataclasses import dataclass + + +@dataclass +class BinaryRelation: + matrix: np.array + reflexive: bool = False + antireflexive: bool = False + symmetric: bool = False + antisymmetric: bool = False + transitive: bool = False + + +def check_reflexivity(relation: BinaryRelation): + diagonal = np.diagonal(relation.matrix) + result = diagonal[diagonal == True].shape[0] == diagonal.shape[0] + relation.reflexive = result + + +def check_antireflexivity(relation: BinaryRelation): + diagonal = np.diagonal(relation.matrix) + result = diagonal[diagonal == False].shape[0] == diagonal.shape[0] + relation.antireflexive = result + + +def check_symmetry(relation: BinaryRelation): + relation.symmetric = (relation.matrix == relation.matrix.T).all() + + +def check_antisymmetry(relation: BinaryRelation): + relation.antisymmetric = True + multiplied = relation.matrix @ relation.matrix.T + n = multiplied.shape[0] + for i in range(n): + for j in range(n): + if i != j and multiplied[i][j] != False: + relation.antisymmetric = False + + +def check_transitivity(relation: BinaryRelation): + multiplied = relation.matrix @ relation.matrix + relation.transitive = (multiplied <= relation.matrix).all() + + +def is_equivalence(relation: BinaryRelation) -> bool: + return relation.reflexive and relation.symmetric and relation.transitive + + +def is_quasiorder(relation: BinaryRelation) -> bool: + return relation.reflexive and relation.transitive + + +def is_partial_order(relation: BinaryRelation) -> bool: + return relation.reflexive and relation.antisymmetric and relation.transitive + + +def is_strict_order(relation: BinaryRelation) -> bool: + return relation.antireflexive and relation.antisymmetric and relation.transitive + + +def reflexive_closure(relation: BinaryRelation) -> BinaryRelation: + matrix = np.copy(relation.matrix) + for i in range(matrix.shape[0]): + matrix[i][i] = True + return BinaryRelation(matrix) + + +def symmetric_closure(relation: BinaryRelation) -> BinaryRelation: + matrix = np.copy(relation.matrix) + n = matrix.shape[0] + for i in range(n): + for j in range(n): + if matrix[i][j]: + matrix[j][i] = True + return BinaryRelation(matrix) + + +def transitive_closure(relation: BinaryRelation) -> BinaryRelation: + matrix = np.copy(relation.matrix) + n = matrix.shape[0] + for _ in range(n): + for i in range(n): + for j in range(n): + for k in range(n): + if matrix[i][k] and matrix[k][j]: + matrix[i][j] = True + return BinaryRelation(matrix) + + +def main(): + n = int(input("Введите размер матрицы: ")) + l = [] + print(f"На следующих {n} строках введите матрицу:") + for _ in range(n): + l.extend(map(int, input().split())) + matrix = np.array(l, dtype=np.bool8).reshape(n, n) + + relation = BinaryRelation(matrix) + check_reflexivity(relation) + check_antireflexivity(relation) + check_symmetry(relation) + check_antisymmetry(relation) + check_transitivity(relation) + + print("Указанное бинарное отношение обладает следующими свойствами:") + if relation.reflexive: print("- Рефлексивность;") + if relation.antireflexive: print("- Антирефлексивность;") + if relation.symmetric: print("- Симметричность;") + if relation.antisymmetric: print("- Антисимметричность;") + if relation.transitive: print("- Транзитивность.") + + classes = [] + if is_equivalence(relation): classes.append("эквивалентностью") + if is_quasiorder(relation): classes.append("квазипорядком") + if is_partial_order(relation): classes.append("частичным порядком") + if is_strict_order(relation): classes.append("строгим порядком") + if classes: + print(f"Отношение является {', '.join(classes)}") + else: + print("Отношение не относится ни к какому особому виду") + + print("Рефлексивное замыкание:") + print(np.array(reflexive_closure(relation).matrix, dtype=np.int8)) + print("Симметричное замыкание:") + print(np.array(symmetric_closure(relation).matrix, dtype=np.int8)) + print("Транзитивное замыкание:") + print(np.array(transitive_closure(relation).matrix, dtype=np.int8)) + print("Эквивалентное замыкание:") + eq = transitive_closure(symmetric_closure(reflexive_closure(relation))) + print(np.array(eq.matrix, dtype=np.int8)) + + +if __name__ == "__main__": + main() diff --git a/lab1/report/SCWorks.cls b/lab1/report/SCWorks.cls new file mode 100644 index 0000000..f905804 --- /dev/null +++ b/lab1/report/SCWorks.cls @@ -0,0 +1,991 @@ +\LoadClass[14pt]{extarticle} +%\RequirePackage[14pt]{extsizes} +\RequirePackage[ + a4paper, mag=1000, + left=2.5cm, right=1.5cm, top=2cm, bottom=2cm, bindingoffset=0cm, + headheight=0cm, footskip=1cm, headsep=0cm + ]{geometry} +\RequirePackage{setspace} +\RequirePackage{calc} +\RequirePackage{titlesec} +\RequirePackage{titletoc} +\RequirePackage{caption} +\RequirePackage{graphicx} +\RequirePackage[inline]{enumitem} + + + + +% --------------------------------------------------------------------------% +% Input data +% --------------------------------------------------------------------------% +\def\chair#1{\gdef\@chair{#1}}\chair{\hbox to 3cm{\hrulefill}} +\def\worktype#1{\gdef\@worktype{#1}} +\def\worktitle{\@title} +\def\subject#1{\gdef\@subject{#1}} +\def\typework#1{\gdef\@typework{#1}} +\def\disserform#1{\gdef\@disserform{#1}} +\def\disserformP#1{\gdef\@disserformP{#1}} +\def\disserformR#1{\gdef\@disserformR{#1}} +\def\disserformV#1{\gdef\@disserformV{#1}} +\def\course#1{\gdef\@course{#1}}\course{2} +\def\group#1{\gdef\@group{#1}}\group{211} +\def\department#1{\gdef\@department{#1}}\department{\cyr\cyrf\cyra\cyrk% +\cyru\cyrl\cyrsftsn\cyrt\cyre\cyrt\cyra\ \CYRK\CYRN\cyri\CYRI\CYRT} +\def\otdelenie#1{\gdef\@otdelenie{#1}} +\def\studentName{\@author} +%\def\studentName#1{\gdef\@studentName{#1}} +\def\satitle#1{\gdef\@satitle{#1}}\satitle{\hbox to 3cm{\hrulefill}} +\def\saname#1{\gdef\@saname{#1}}\saname{\hbox to 3cm{\hrulefill}} +\def\critictitle#1{\gdef\@critictitle{#1}}\critictitle{\hbox to 3cm{\hrulefill}} +\def\criticname#1{\gdef\@criticname{#1}}\criticname{\hbox to 3cm{\hrulefill}} +\def\secrname#1{\gdef\@secrname{#1}}\secrname{\hbox to 3cm{\hrulefill}} +\def\chtitle#1{\gdef\@chtitle{#1}}\chtitle{\hbox to 3cm{\hrulefill}} +\def\chname#1{\gdef\@chname{#1}}\chname{\hbox to 3cm{\hrulefill}} +%\def\year#1{\gdef\@year{#1}} +\def\spectype#1{\gdef\@spectype{#1}} +\def\spectyperod#1{\gdef\@spectyperod{#1}} +\def\workform#1{\gdef\@workform{#1}} +\def\practtype#1{\gdef\@practtype{#1}}\practtype{\cyr\cyru\cyrch\cyre\cyrb% +\cyrn\cyra\cyrya} +\def\term#1{\gdef\@term{#1}}\term{2} +\def\duration#1{\gdef\@duration{#1}}\duration{2} +\def\protnum#1{\gdef\@protnum{#1}}\protnum{\hbox to 1cm{\hrulefill}} +\def\protdate#1{\gdef\@protdate{#1}}\protdate{\hbox to 3cm{\hrulefill}} +\def\practStart#1{\gdef\@practStart{#1}}\practStart{\hbox to 3cm{\hrulefill}} +\def\practFinish#1{\gdef\@practFinish{#1}}\practFinish{\hbox to 3cm{\hrulefill}} +\def\reviewtype#1{\gdef\@reviewtype{#1}}\reviewtype{\CYRO\CYRT% +\CYRZ\CYRERY\CYRV} + +\def\patitle#1{\gdef\@patitle{#1}}\patitle{\@satitle} +\def\paname#1{\gdef\@paname{#1}}\paname{\@saname} + +\def\napravlenie#1{\gdef\@napravlenie{#1}}\napravlenie{\hbox to 3cm{\hrulefill}} +\def\Napravlenie{\@napravlenie} + + +\def\studenttitle#1{\gdef\@studenttitle{#1}}\studenttitle{\cyr\cyrs\cyrt% +\cyru\cyrd\cyre\cyrn\cyrt\cyra} +\def\studentdone#1{\gdef\@studentdone{#1}}\studentdone{\cyrp\cyrr\cyro% +\cyrsh\cyre\cyrd\cyrsh\cyre\cyrg\cyro} +\def\studentfemale{\studenttitle{\cyrs\cyrt\cyru\cyrd\cyre\cyrn\cyrt% +\cyrk\cyri}\studentdone{\cyrp\cyrr\cyro\cyrsh\cyre\cyrd\cyrsh% +\cyre\cyrishrt}} + +%\newcommand{\MakeTitle}{} + +\def\workname#1{\gdef\@workname{#1}} + +%\hbox to 3cm{\hrulefill} + +% --------------------------------------------------------------------------% + + +\newcommand{\signature}[2]{ +\hbox to 7cm{#1\hfill} \hbox to 3cm{\hrulefill} \hbox to 6cm{\hfill #2}} + +\newcommand{\inlinesignature}[2]{% +#1\qquad \hbox to 3cm{\hrulefill}\quad #2} + + +\newcommand{\signatureline}{} + +% --------------------------------------------------------------------------% +\newcommand{\scaleUnivName}{0.97} + +\DeclareOption{times}{% + \renewcommand{\rmdefault}{ftm} + \renewcommand{\scaleUnivName}{1.0} +} + +\DeclareOption{spec}{% + \spectype{\cyr\cyrs\cyrp\cyre\cyrc\cyri\cyra\cyrl\cyrsftsn\cyrn\cyro% + \cyrs\cyrt\cyri} + \spectyperod{\cyrs\cyrp\cyre\cyrc\cyri\cyra\cyrl\cyrsftsn\cyrn\cyro% + \cyrs\cyrt\cyri} + \workform{\cyr\CYRS\CYRP\CYRE\CYRC\CYRI\CYRA\CYRL\CYRI\CYRS\CYRT\CYRA} + \disserform{\CYRD\CYRI\CYRP\CYRL\CYRO\CYRM\CYRN\CYRA\CYRYA\ \CYRR\CYRA% + \CYRB\CYRO\CYRT\CYRA} + \disserformP{\CYRD\CYRI\CYRP\CYRL\CYRO\CYRM\CYRN\CYRO\CYRISHRT\ \CYRR% + \CYRA\CYRB\CYRO\CYRT\CYRE} + \disserformR{\CYRD\CYRI\CYRP\CYRL\CYRO\CYRM\CYRN\CYRO\CYRISHRT\ \CYRR% + \CYRA\CYRB\CYRO\CYRT\CYRERY} + \disserformV{\CYRD\CYRI\CYRP\CYRL\CYRO\CYRM\CYRN\CYRU\CYRYU\ \CYRR\CYRA% + \CYRB\CYRO\CYRT\CYRU} +} + +\DeclareOption{bachelor}{% + \spectype{\cyr\cyrn\cyra\cyrp\cyrr\cyra\cyrv\cyrl\cyre\cyrn\cyri\cyrya} + \spectyperod{\cyr\cyrn\cyra\cyrp\cyrr\cyra\cyrv\cyrl\cyre\cyrn\cyri \cyryu} + \workform{\cyr\CYRB\CYRA\CYRK\CYRA\CYRL\CYRA\CYRV\CYRR\CYRA} + \disserform{\CYRB\CYRA\CYRK\CYRA\CYRL\CYRA\CYRV\CYRR\CYRS\CYRK\CYRA% + \CYRYA\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRA} + \disserformP{\CYRB\CYRA\CYRK\CYRA\CYRL\CYRA\CYRV\CYRR\CYRS\CYRK\CYRO% + \CYRISHRT\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRE} + \disserformR{\CYRB\CYRA\CYRK\CYRA\CYRL\CYRA\CYRV\CYRR\CYRS\CYRK\CYRO% + \CYRISHRT\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRERY} + \disserformV{\CYRB\CYRA\CYRK\CYRA\CYRL\CYRA\CYRV\CYRR\CYRS\CYRK\CYRU% + \CYRYU\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRU} +} + +\DeclareOption{master}{% + \spectype{\cyr\cyrn\cyra\cyrp\cyrr\cyra\cyrv\cyrl\cyre\cyrn\cyri\cyrya} + \spectyperod{\cyr\cyrn\cyra\cyrp\cyrr\cyra\cyrv\cyrl\cyre\cyrn\cyri \cyryu} + \workform{\cyr\CYRM\CYRA\CYRG\CYRI\CYRS\CYRT\CYRR\CYRA} + \disserform{\CYRM\CYRA\CYRG\CYRI\CYRS\CYRT\CYRE\CYRR\CYRS\CYRK\CYRA% + \CYRYA\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRA} + \disserformP{\CYRM\CYRA\CYRG\CYRI\CYRS\CYRT\CYRE\CYRR\CYRS\CYRK\CYRO% + \CYRISHRT\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRE} + \disserformR{\CYRM\CYRA\CYRG\CYRI\CYRS\CYRT\CYRE\CYRR\CYRS\CYRK\CYRO% + \CYRISHRT\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRERY} + \disserformV{\CYRM\CYRA\CYRG\CYRI\CYRS\CYRT\CYRE\CYRR\CYRS\CYRK\CYRU% + \CYRYU\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRU} +} + +\DeclareOption{coursework}{% + \worktype{\cyr\CYRK\cyru\cyrr\cyrs\cyro\cyrv\cyra\cyrya\ \cyrr\cyra\cyrb% + \cyro\cyrt\cyra} + \renewcommand{\maketitle}{\CDMakeTitle} + \workname{\MakeUppercase{\@worktype}} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn\cyra} +} + +\DeclareOption{diploma}{% + \worktype{\cyr\CYRV\cyrery\cyrp\cyru\cyrs\cyrk\cyrn\cyra\cyrya\ \cyrk\cyrv% + \cyra\cyrl\cyri\cyrf\cyri\cyrk\cyra\cyrc\cyri\cyro\cyrn\cyrn\cyra% + \cyrya\ \cyrr\cyra\cyrb\cyro\cyrt\cyra} + \worktype{\ \cyrr\cyra\cyrb\cyro\cyrt\cyra} + \renewcommand{\maketitle}{\CDMakeTitle} + \workname{\MakeUppercase{\@disserform}} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn\cyra} +} + +\DeclareOption{autoref}{% + \workname{\cyr\CYRA\CYRV\CYRT\CYRO\CYRR\CYRE\CYRF\CYRE\CYRR\CYRA\CYRT\ % + \MakeUppercase{\@disserformR}} + \worktype{\ \cyrr\cyra\cyrb\cyro\cyrt\cyra} + \renewcommand{\maketitle}{\CDMakeTitle} + %\workname{\MakeUppercase{\@disserform}} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn\cyra} +} + +\DeclareOption{nir}{% + \workname{\cyr\CYRO\CYRT\CYRCH\CYRE\CYRT\ \CYRO\ \CYRN\CYRA\CYRU\CYRCH% + \CYRN\CYRO-\CYRI\CYRS\CYRS\CYRL\CYRE\CYRD\CYRO\CYRV\CYRA\CYRT\CYRE\CYRL% + \CYRSFTSN\CYRS\CYRK\CYRO\CYRISHRT\ \CYRR\CYRA\CYRB\CYRO\CYRT\CYRE} + \worktype{\ \cyrr\cyra\cyrb\cyro\cyrt\cyra} + \renewcommand{\maketitle}{\CDMakeTitle} + %\workname{\MakeUppercase{\@disserform}} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn\cyra} +} + +\DeclareOption{pract}{% + \worktype{\cyr\CYRO\cyrt\cyrch\cyre\cyrt\ \cyro\ \cyrp\cyrr\cyra\cyrk\cyrt% + \cyri\cyrk\cyre} + \renewcommand{\maketitle}{\MakeTitlePr} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn} +} + +\DeclareOption{review}{% + \reviewtype{\CYRO\CYRT\CYRZ\CYRERY\CYRV} + \worktype{\cyrn\cyra\cyru\cyrch\cyrn\cyro\cyrg\cyro\ \cyrr\cyru\cyrk% + \cyro\cyrv\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrya\ \cyro\ \cyrv\cyrery% + \cyrp\cyru\cyrs\cyrk\cyrn\cyro\cyrishrt\ \cyrk\cyrv\cyra\cyrl\cyri\cyrf% + \cyri\cyrk\cyra\cyrc\cyri\cyro\cyrn\cyrn\cyro\cyrishrt\ \cyrr\cyra\cyrb% + \cyro\cyrt\cyre} + \workname{\cyr\cyrn\cyra\cyru\cyrch\cyrn\cyro\cyrg\cyro\ \cyrr\cyru\cyrk% + \cyro\cyrv\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrya\ \cyro\ \MakeLowercase{\@disserformP}} + %\workname{\@worktype\ \MakeLowercase{\@workform}} + \renewcommand{\maketitle}{\MakeTitleReview} + \renewcommand{\signatureline}{% + \par\noindent% + \CYRN\cyra\cyru\cyrch\cyrn\cyrery\cyrishrt\ \cyrr\cyru\cyrk\cyro\cyrv% + \cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrsftsn\\% + \signature{\@satitle}{\@saname}\\% + } +} + +\DeclareOption{assignment}{% + \reviewtype{\CYRZ\CYRA\CYRD\CYRA\CYRN\CYRI\CYRE} + \worktype{\cyrn\cyra\ \cyrv\cyrery\cyrp\cyru\cyrs\cyrk\cyrn\cyru% + \cyryu\ \cyrk\cyrv\cyra\cyrl\cyri\cyrf\cyri\cyrk\cyra\cyrc\cyri\cyro% + \cyrn\cyrn\cyru\cyryu\ \cyrr\cyra\cyrb\cyro\cyrt\cyru} + \workname{\cyr\cyrn\cyra\ \MakeLowercase{\@disserformV}} + %\workname{\@worktype\ \MakeLowercase{\@workform}} + \renewcommand{\maketitle}{\MakeTitleAssign} + \renewcommand{\signatureline}{% + + \vfill% + \noindent% + \textbf{\CYRS\cyrr\cyro\cyrk\ \cyrp\cyrr\cyre\cyrd\cyro\cyrs\cyrt\cyra% + \cyrv\cyrl\cyre\cyrn\cyri\cyrya\ \cyrr\cyra\cyrb\cyro\cyrt\cyrery:}\ \@practFinish + + \vspace{2em}\raggedright + \noindent \CYRR\cyra\cyrs\cyrs\cyrm\cyro\cyrt\cyrr\cyre\cyrn\cyro\ % + \cyrn\cyra\ \cyrz\cyra\cyrs\cyre\cyrd\cyra\cyrn\cyri\cyri\ \cyrk\cyra% + \cyrf\cyre\cyrd\cyrr\cyrery\ \@chair + + \vspace{1em} + \CYRP\cyrr\cyro\cyrt\cyro\cyrk\cyro\cyrl\ \textnumero\ \@protnum\ \cyro% + \cyrt\ \@protdate + + \vspace{1em} + \raggedright + \noindent + \inlinesignature{\CYRS\cyre\cyrk\cyrr\cyre\cyrt\cyra\cyrr\cyrsftsn}{\@secrname} + + \vspace{2em} + \noindent\raggedright + \CYRD\cyra\cyrt\cyra\ \cyrv\cyrery\cyrd\cyra\cyrch\cyri\ \cyrz\cyra% + \cyrd\cyra\cyrn\cyri\cyrya\ \@practStart + + \vspace{1em} + \noindent\raggedright + \inlinesignature{\CYRZ\cyra\cyrd\cyra\cyrn\cyri\cyre\ \cyrp\cyro\cyrl% + \cyru\cyrch\cyri\cyrl}{\hbox to 3cm{\hrulefill}} + + \vspace{1cm} + } +} + +\DeclareOption{critique}{% + \reviewtype{\CYRR\CYRE\CYRC\CYRE\CYRN\CYRZ\CYRI\CYRYA} + \worktype{\cyrn\cyra\ \cyrv\cyrery\cyrp\cyru\cyrs\cyrk\cyrn\cyru% + \cyryu\ \cyrk\cyrv\cyra\cyrl\cyri\cyrf\cyri\cyrk\cyra\cyrc\cyri\cyro% + \cyrn\cyrn\cyru\cyryu\ \cyrr\cyra\cyrb\cyro\cyrt\cyru} + \workname{\cyr\cyrn\cyra\ \MakeLowercase{\@disserformV}} + %\workname{\@worktype\ \MakeLowercase{\@workform}} + \renewcommand{\maketitle}{\MakeTitleReview} + \renewcommand{\signatureline}{% + \par\noindent% + \CYRR\cyre\cyrc\cyre\cyrn\cyrz\cyre\cyrn\cyrt\\% + \signature{\@critictitle}{\@criticname}\\% + } +} + + +\DeclareOption{referat}{% + \worktype{\cyr\CYRR\cyre\cyrf\cyre\cyrr\cyra\cyrt} + \workname{\MakeUppercase{\@worktype}} + \renewcommand{\maketitle}{\RefMakeTitle} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn} +} + +\DeclareOption{labwork}{% + \worktype{\cyr\CYRL\cyra\cyrb\cyro\cyrr\cyra\cyrt\cyro\cyrr\cyrn\cyra\cyrya\ \cyrr\cyra\cyrb\cyro\cyrt\cyra} + \workname{\MakeUppercase{\@worktype}} + \renewcommand{\maketitle}{\RefMakeTitle} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn} +} + +\DeclareOption{labwork2}{% + \worktype{\CYRO\cyrt\cyrch\cyryo\cyrt\ \cyrp\cyro\ \cyrd\cyri\cyrs\cyrc\cyri\cyrp\cyrl\cyri\cyrn\cyre} + \workname{\MakeUppercase{\@worktype}} + \renewcommand{\maketitle}{\LabTwoMakeTitle} + \typework{\cyr\cyrn\cyra\cyrp\cyri\cyrs\cyra\cyrn} +} + +\DeclareOption{och}{% + \otdelenie{\cyr\cyro\cyrch\cyrn\cyro\cyrishrt\ \cyrf\cyro\cyrr\cyrm% + \cyrery\ \cyro\cyrb\cyru\cyrch\cyre\cyrn\cyri\cyrya} +} + +\DeclareOption{zaoch}{% + \otdelenie{\cyr\cyrz\cyra\cyro\cyrch\cyrn\cyro\cyrishrt\ \cyrf\cyro\cyrr% + \cyrm\cyrery\ \cyro\cyrb\cyru\cyrch\cyre\cyrn\cyri\cyrya} +} + +\ExecuteOptions{coursework,och,bachelor} +\ProcessOptions + +% --------------------------------------------------------------------------% +\newcommand*{\hm}[1]{#1\nobreak\discretionary{}% +{\hbox{$\mathsurround=0pt #1$}}{}} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% + +\onehalfspacing +\parindent=1.25cm +\pagestyle{headings} +\renewcommand{\@oddhead}{} +\renewcommand{\@oddfoot}{\hfil \thepage} + +% --------------------------------------------------------------------------% +% Table and figure numbering by sections +% --------------------------------------------------------------------------% +\newif\if@secNumbering\@secNumberingfalse +\newcommand{\secNumbering}{ + \renewcommand{\thefigure}{\arabic{section}.\arabic{figure}} + \renewcommand{\thetable}{\arabic{section}.\arabic{table}} + \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} + \@addtoreset{figure}{section} + \@addtoreset{table}{section} + \@addtoreset{equation}{section} + \@secNumberingtrue +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Table and figure captions +% --------------------------------------------------------------------------% +\def\CaptionName#1{\gdef\@captionname{#1}} +\newlength\tmp %10cm +\setlength{\tmp}{1ex} +\setlength{\belowcaptionskip}{1ex} +\setlength{\abovecaptionskip}{1ex} + +\captionsetup[figure]{name=\CYRR\cyri\cyrs\cyru\cyrn\cyro\cyrk, labelsep=endash, + justification=centering, font={small}, skip=\abovecaptionskip, position=below} +\captionsetup[table]{name=\CYRT\cyra\cyrb\cyrl\cyri\cyrc\cyra, labelsep=endash, format=plain, + justification=RaggedRight, singlelinecheck=false, font={small}, position=top} + +% --------------------------------------------------------------------------% +% Table of contents +% --------------------------------------------------------------------------% +\renewcommand{\tableofcontents}% +{\structformat\section*{\uppercase{\cyr\CYRS\CYRO\CYRD\CYRE\CYRR\CYRZH\CYRA% +\CYRN\CYRI\CYRE}}\secformat\@starttoc{toc} +\thispagestyle{empty}} + +\renewcommand{\@dotsep}{1.5} +\renewcommand{\@pnumwidth}{1.0em} + +\newcommand{\l@abcd}[2]{{\@dottedtocline{0}{0pt}{0pt}{#1}{#2}}} + +\renewcommand{\l@section}{\@dottedtocline{1}{0em}{1.5em}} +\renewcommand{\l@subsection}{\@dottedtocline{2}{1.5em}{2.3em}} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Sections, subsections +% --------------------------------------------------------------------------% +% Numbering +\renewcommand{\thesection}{\arabic{section}} +\renewcommand{\thesubsection}{\arabic{section}.\arabic{subsection}} +\renewcommand{\thesubsubsection}{\arabic{section}.\arabic{subsection}.\arabic{subsubsection}} + +\newcommand{\sectionbreak}{\clearpage} + +% Contents, intro, conclusion +\newcommand{\structformat} +{ + \titlespacing{\section} + {0cm}{3ex plus 1ex minus .2ex}{1.4ex plus.2ex} + \titleformat{\section}[block] + {\centering\bfseries} + {\thesection}{0ex}{} +} + +% Sections, subsections +\newcommand{\secformat} +{ + \titlespacing{\section} + {0cm}{3ex plus 1ex minus .2ex}{0.4ex plus.2ex} + \titleformat{\section}[block] + {\hspace{1.25cm}\raggedright\bfseries} + {\thesection}{1ex}{} +} + +\newif\if@hyperrefloaded\@hyperrefloadedfalse +\AtBeginDocument{\@ifpackageloaded{hyperref}% + {\@hyperrefloadedtrue}{\@hyperrefloadedfalse}% +} + +%\RequirePackage{ifthen} +\newcommand{\starsection}[1]{ + \structformat + \section*{#1}% + \if@hyperrefloaded + \phantomsection + \fi + \addcontentsline{toc}{section}{#1} + \setcounter{section}{0} + \secformat +} + + +\setcounter{section}{0} +\secformat + + +\newcommand{\intro}{\starsection{\cyr\CYRV\CYRV\CYRE\CYRD\CYRE% +\CYRN\CYRI\CYRE}} +\newcommand{\abbreviations}{\starsection{\CYRO\CYRB\CYRO\CYRZ\CYRN\CYRA% +\CYRCH\CYRE\CYRN\CYRI\CYRYA\ \CYRI\ \CYRS\CYRO\CYRK\CYRR\CYRA\CYRSHCH% +\CYRE\CYRN\CYRI\CYRYA}} +\newcommand{\definitions}{\starsection{\CYRO\CYRP\CYRR\CYRE\CYRD\CYRE% +\CYRL\CYRE\CYRN\CYRI\CYRYA}} +\newcommand{\defabbr}{\starsection{\CYRO\CYRP\CYRR\CYRE\CYRD\CYRE\CYRL% +\CYRE\CYRN\CYRI\CYRYA, \CYRO\CYRB\CYRO\CYRZ\CYRN\CYRA\CYRCH\CYRE\CYRN% +\CYRI\CYRYA\ \CYRI\ \CYRS\CYRO\CYRK\CYRR\CYRA\CYRSHCH\CYRE\CYRN\CYRI\CYRYA}} +\newcommand{\conclusion}{\starsection{\cyr\CYRZ\CYRA\CYRK\CYRL\CYRYU% +\CYRCH\CYRE\CYRN\CYRI\CYRE}} + +% Section and subsection parameters +\titlespacing{\section} +{0cm}{3ex plus 1ex minus .2ex}{0.4ex plus.2ex} + +\titleformat{\subsection}[block] +{\hspace{1.25cm}\normalfont\bfseries} +{\thesubsection}{1ex}{} +\titlespacing{\subsection} +{0cm}{2ex plus 1ex minus .2ex}{.4ex plus.2ex} + +\titleformat{\subsubsection}[block] +{\hspace{1.25cm}\normalfont} +{\thesubsubsection}{1ex}{} +\titlespacing{\subsubsection} +{0cm}{2ex plus 1ex minus .2ex}{.4ex plus.2ex} + +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% + + +%\AddEnumerateCounter{\Asbuk}{\@Asbuk}{\CYRM} +%\AddEnumerateCounter{\asbuk}{\@asbuk}{\cyrm} + +\makeatletter +\def\redeflsection{\def\l@section{\@dottedtocline{1}{0em}{10em}}} +\renewcommand{\appendix}{\par% + + \renewcommand{\secNumbering}{ + \renewcommand{\thefigure}{\Asbuk{section}.\arabic{figure}} + \renewcommand{\thetable}{\Asbuk{section}.\arabic{table}} + \renewcommand{\theequation}{\Asbuk{section}.\arabic{equation}} + \@addtoreset{figure}{section} + \@addtoreset{table}{section} + \@addtoreset{equation}{section} + + } + \if@secNumbering + \secNumbering + \fi + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \renewcommand{\appendixname}{\cyr\CYRP\CYRR\CYRI\CYRL\CYRO\CYRZH\CYRE% + \CYRN\CYRI\CYRE}% + \def\sectionname{\appendixname}% + \addtocontents{toc}{\protect\redeflsection}% + \gdef\thesection{\Asbuk{section}}% + \titlespacing{\section} + %{0cm}{1ex plus 0.1ex minus .2ex}{1.1ex plus.1ex} + {0cm}{3ex plus 1ex minus .2ex}{0.4ex plus.2ex} + \titleformat{\section}[display] + {\centering\normalfont\bfseries} + {\appendixname\hspace{1ex}\thesection}{0ex}{} + + + \titlecontents{section} + [3ex] + {\hspace{-3ex}} + {\appendixname~\thecontentslabel\hspace{2ex}} + {\hspace{2.3em}} + {\titlerule*[0.98ex]{.}\contentspage} + +} + + + +% --------------------------------------------------------------------------% +% Title pages +% --------------------------------------------------------------------------% +%\newcommand{\shapka}{{\centering \CYRM\CYRI\CYRN\CYRO\CYRB\CYRR\CYRN\CYRA% +%\CYRU\CYRK\CYRI\ \CYRR\CYRO\CYRS\CYRS\CYRI\CYRI\\ % +%\CYRF\cyre\cyrd\cyre\cyrr\cyra\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyrg\cyro% +%\cyrs\cyru\cyrd\cyra\cyrr\cyrs\cyrt\cyrv\cyre\cyrn\cyrn\cyro\cyre\ % +%\cyrb\cyryu\cyrd\cyrzh\cyre\cyrt\cyrn\cyro\cyre\ \cyro\cyrb\cyrr\cyra% +%\cyrz\cyro\cyrv\cyra\cyrt\cyre\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyru% +%\cyrch\cyrr\cyre\cyrzh\cyrd\cyre\cyrn\cyri\cyre\ \cyrv\cyrery\cyrs% +%\cyrsh\cyre\cyrg\cyro\ \cyro\cyrb\cyrr\cyra\cyrz% +%\cyro\cyrv\cyra\cyrn\cyri\cyrya\\ +%\textbf{<<\CYRS\CYRA\CYRR\CYRA\CYRT\CYRO\CYRV\CYRS\CYRK\CYRI\CYRISHRT\ % +%\CYRN\CYRA\CYRC\CYRI\CYRO\CYRN\CYRA\CYRL\CYRSFTSN\CYRN\CYRERY% +%\CYRISHRT\ \CYRI\CYRS\CYRS\CYRL\CYRE\CYRD\CYRO\CYRV\CYRA\CYRT\CYRE\CYRL% +%\CYRSFTSN\CYRS\CYRK\CYRI\CYRISHRT\ % +%\CYRG\CYRO\CYRS\CYRU\CYRD\CYRA\CYRR\CYRS\CYRT\CYRV\CYRE\CYRN\CYRN\CYRERY% +%\CYRISHRT\ \CYRU\CYRN\CYRI\CYRV\CYRE\CYRR\CYRS\CYRI\CYRT\CYRE\CYRT\ % +%\CYRI\CYRM\CYRE\CYRN\CYRI~\CYRN.\,\CYRG.\,\CYRCH\CYRE\CYRR\CYRN\CYRERY% +%\CYRSH\CYRE\CYRV\CYRS\CYRK\CYRO\CYRG\CYRO>>}\\}} + +%\newcommand{\shapka}{{\centering \CYRM\CYRI\CYRN\CYRO\CYRB\CYRR\CYRN\CYRA% +%\CYRU\CYRK\CYRI\ \CYRR\CYRO\CYRS\CYRS\CYRI\CYRI\\ \hspace{-1em}% +%\CYRF\cyre\cyrd\cyre\cyrr\cyra\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyrg\cyro% +%\cyrs\cyru\cyrd\cyra\cyrr\cyrs\cyrt\cyrv\cyre\cyrn\cyrn\cyro\cyre\ % +%\cyrb\cyryu\cyrd\cyrzh\cyre\cyrt\cyrn\cyro\cyre\ \cyro\cyrb\cyrr\cyra% +%\cyrz\cyro\cyrv\cyra\cyrt\cyre\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyru% +%\cyrch\cyrr\cyre\cyrzh\cyrd\cyre\cyrn\cyri\cyre\ \\\cyrv\cyrery\cyrs% +%\cyrsh\cyre\cyrg\cyro\ \cyro\cyrb\cyrr\cyra\cyrz% +%\cyro\cyrv\cyra\cyrn\cyri\cyrya\\\hspace{-2em} +%{ +%\textbf{<<\CYRS\CYRA\CYRR\CYRA\CYRT\CYRO\CYRV\CYRS\CYRK\CYRI\CYRISHRT\ % +%\CYRN\CYRA\CYRC\CYRI\CYRO\CYRN\CYRA\CYRL\CYRSFTSN\CYRN\CYRERY% +%\CYRISHRT\ \CYRI\CYRS\CYRS\CYRL\CYRE\CYRD\CYRO\CYRV\CYRA\CYRT\CYRE\CYRL% +%\CYRSFTSN\CYRS\CYRK\CYRI\CYRISHRT}} \\% +%{\textbf{\CYRG\CYRO\CYRS\CYRU\CYRD\CYRA\CYRR\CYRS\CYRT\CYRV\CYRE\CYRN\CYRN\CYRERY% +%\CYRISHRT\ \CYRU\CYRN\CYRI\CYRV\CYRE\CYRR\CYRS\CYRI\CYRT\CYRE\CYRT}} \\% +%{\textbf{\CYRI\CYRM\CYRE\CYRN\CYRI~\CYRN.\,\CYRG.\,\CYRCH\CYRE\CYRR\CYRN\CYRERY% +%\CYRSH\CYRE\CYRV\CYRS\CYRK\CYRO\CYRG\CYRO>>}}\\}} + +% \newcommand{\shapka}{{\centering \CYRM\CYRI\CYRN\CYRO\CYRB\CYRR\CYRN\CYRA% +% \CYRU\CYRK\CYRI\ \CYRR\CYRO\CYRS\CYRS\CYRI\CYRI\\ % +% \CYRF\cyre\cyrd\cyre\cyrr\cyra\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyrg\cyro% +% \cyrs\cyru\cyrd\cyra\cyrr\cyrs\cyrt\cyrv\cyre\cyrn\cyrn\cyro\cyre\ % +% \cyrb\cyryu\cyrd\cyrzh\cyre\cyrt\cyrn\cyro\cyre\ \cyro\cyrb\cyrr\cyra% +% \cyrz\cyro\cyrv\cyra\cyrt\cyre\cyrl\cyrsftsn\cyrn\cyro\cyre\ \cyru% +% \cyrch\cyrr\cyre\cyrzh\cyrd\cyre\cyrn\cyri\cyre\ \\\cyrv\cyrery\cyrs% +% \cyrsh\cyre\cyrg\cyro\ \cyro\cyrb\cyrr\cyra\cyrz% +% \cyro\cyrv\cyra\cyrn\cyri\cyrya\\[0.2em] +\newcommand{\shapka}{{ +\centering +\centerline{\scalebox{\scaleUnivName}[1.0]{\parbox[t]{1.1\textwidth} +{\centering +\textbf{\CYRM\CYRI\CYRN\CYRO\CYRB\CYRR\CYRN\CYRA\CYRU\CYRK\CYRI\ +\CYRR\CYRO\CYRS\CYRS\CYRI\CYRI\\ +\CYRF\CYRG\CYRB\CYRO\CYRU\ \CYRV\CYRO\ +<<\CYRS\CYRG\CYRU\ +\CYRI\CYRM\CYRE\CYRN\CYRI~\CYRN.\,\CYRG.\,\CYRCH\CYRE\CYRR\CYRN\CYRERY% +\CYRSH\CYRE\CYRV\CYRS\CYRK\CYRO\CYRG\CYRO>>}}}}}} + +\newcommand{\shapkatwo}{{ +\centering +\centerline{\scalebox{\scaleUnivName}[1.0]{\parbox[t]{1.1\textwidth} +{\centering +\CYRM\CYRI\CYRN\CYRO\CYRB\CYRR\CYRN\CYRA\CYRU\CYRK\CYRI\ +\CYRR\CYRO\CYRS\CYRS\CYRI\CYRI\\ +Федеральное государственное бюджетное образовательное учреждение высшего образования\\ +\textbf{ +<<САРАТОВСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ\ +\CYRI\CYRM\CYRE\CYRN\CYRI~\CYRN.\,\CYRG.\,\CYRCH\CYRE\CYRR\CYRN\CYRERY% +\CYRSH\CYRE\CYRV\CYRS\CYRK\CYRO\CYRG\CYRO>>}}}}}} + +\newcommand{\CDMakeTitle} +{ +\thispagestyle{empty} +\shapka +%\vspace{0.5cm} +\begin{center} +%\parbox{8cm}{ +%\raggedright +\CYRK\cyra\cyrf\cyre\cyrd\cyrr\cyra\ \@chair +%} +\end{center} + +\vspace{14pt} +\vspace{1cm} +{\centering +\textbf{\MakeUppercase{\@title}} +\\[0.3cm] +{\@workname} + +} + +\vspace{1.5cm} +\begin{flushleft} +\@studenttitle\ \@course\ \cyrk\cyru\cyrr\cyrs\cyra\ \@group\ \cyrg% +\cyrr\cyru\cyrp\cyrp\cyrery\\ +\@spectype\ \@napravlenie\\ +\@department\\ +\@author +\end{flushleft} +\vfill + +\noindent +\CYRN\cyra\cyru\cyrch\cyrn\cyrery\cyrishrt\ \cyrr\cyru\cyrk\cyro\cyrv% +\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrsftsn\\ +\signature{\@satitle}{\@saname}\\[14pt] +\CYRZ\cyra\cyrv\cyre\cyrd\cyru\cyryu\cyrshch\cyri\cyrishrt\ \cyrk\cyra% +\cyrf\cyre\cyrd\cyrr\cyro\cyrishrt\\ +\signature{\@chtitle}{\@chname} + +\vfill +{\centering{\cyr\CYRS\cyra\cyrr\cyra\cyrt\cyro\cyrv\ \@date} + +} +\newpage +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Title page of internship +% --------------------------------------------------------------------------% +\newcommand{\MakeTitlePr} +{ +\thispagestyle{empty} +\begin{center} +\shapka +\end{center} +\vspace{0.5cm} + + +\begin{flushright} + \parbox{7cm}{ + \begin{flushleft} + \CYRU\CYRT\CYRV\CYRE\CYRR\CYRZH\CYRD\CYRA\CYRYU\\ + \CYRZ\cyra\cyrv\cyre\cyrd\cyru\cyryu\cyrshch\cyri\cyrishrt\ \cyrk\cyra\cyrf\cyre\cyrd\cyrr\cyro\cyrishrt\\ + \@chtitle\\ + \hbox to 7cm{\hrulefill\ \@chname} + \end{flushleft} + } +\end{flushright} + +\vspace{1cm} +\begin{center}\textbf{\MakeUppercase{\@worktype}}\end{center} +\begin{flushleft} + \vspace{12pt} + % TODO: ubrat nahui cifru 2 + \@studenttitle\ 2\ \cyrk\cyru\cyrr\cyrs\cyra\\ + \@department\\ + + { + \centering + \@author\\ + } + \vspace{0.5cm} + + { + \centering + \@practtype\ \cyrp\cyrr\cyra\cyrk\cyrt\cyri\cyrk\cyra\\ + (\CYRU\cyrch\cyre\cyrb\cyrn\cyra\cyrya\ \cyrp\cyrr\cyra\cyrk\cyrt\cyri\cyrk\cyra)\\ + } + \vspace{0.5cm} + + \cyrk\cyra\cyrf\cyre\cyrd\cyrr\cyra\ \@chair\\ + \cyrk\cyru\cyrr\cyrs\ \underline{\textit{\@course}}\\ + \cyrs\cyre\cyrm\cyre\cyrs\cyrt\cyrr\ \underline{\textit{\@term}}\\ + \cyrp\cyrr\cyro\cyrd\cyro\cyrl\cyrzh\cyri\cyrt\cyre\cyrl\cyrsftsn\cyrn% + \cyro\cyrs\cyrt\cyrsftsn\ \underline{\textit{\@duration\ \cyrn\cyre\cyrd\cyre\cyrl\cyri, \cyrs\ \@practStart\ \cyrg. \cyrp\cyro\ \@practFinish\ \cyrg.}} +\end{flushleft} +%\parindent=-0.2cm +\vspace{1cm} + +\noindent +\CYRR\cyru\cyrk\cyro\cyrv\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrsftsn\ \cyrp% +\cyrr\cyra\cyrk\cyrt\cyri\cyrk\cyri\\% +\signature{\@satitle}{\@saname}\\[14pt] + +\vfill +{\centering{\cyr\CYRS\cyra\cyrr\cyra\cyrt\cyro\cyrv\\\@date} + +} +% \CYRR\cyru\cyrk\cyro\cyrv\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrsftsn\ \cyrp% +% \cyrr\cyra\cyrk\cyrt\cyri\cyrk\cyri\ \cyro\cyrt\ \cyro\cyrr\cyrg\cyra% +% \cyrn\cyri\cyrz\cyra\cyrc\cyri\cyri\ (\cyru\cyrch\cyrr\cyre\cyrzh\cyrd% +% \cyre\cyrn\cyri\cyrya, \cyrp\cyrr\cyre\cyrd\cyrp\cyrr\cyri\cyrya\cyrt% +% \cyri\cyrya),\\[12pt]% +% \signature{\@patitle}{\@paname} + +% \newpage +% \thispagestyle{empty} +% \vspace*{11cm} +% \CYRT\cyre\cyrm\cyra\ \cyrp\cyrr\cyra\cyrk\cyrt\cyri\cyrk\cyri:<<\@title>> +% \parindent=1.25cm +% \newpage +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Title page of review +% --------------------------------------------------------------------------% +\newcommand{\MakeTitleReview} +{ +\pagestyle{empty} +\begin{center} +\shapka +\end{center} + + +{ +\centering +\textbf{\MakeUppercase{\@reviewtype}}\\[-0.3em] +\textbf{\@workname}\\[0.3em] +<<{\MakeUppercase{\@title}}>> + +\@studenttitle\ \@course\ \cyrk\cyru\cyrr\cyrs\cyra\ % +\@department\\ + +\centering +{\@author}\\ + +\centering +\@studentdone\ \cyro\cyrb\cyru\cyrch\cyre\cyrn\cyri\cyre\ \cyrp% +\cyro\ \@spectyperod\ \@napravlenie + +} +\vspace{2em} +} +% --------------------------------------------------------------------------% + + +% --------------------------------------------------------------------------% +% Title page of assignment +% --------------------------------------------------------------------------% +\newcommand{\MakeTitleAssign} +{ +\pagestyle{empty} +\begin{center} +\shapka +\end{center} + +{ +\centering +\CYRK\cyra\cyrf\cyre\cyrd\cyrr\cyra\ \@chair + + +\vspace{6em} +\centering +\textbf{\MakeUppercase{\@reviewtype}\\%[-0.3em] +\@workname} + +\vspace{0.3em} +\raggedright +\cyrp\cyro\ \@spectyperod\ \@napravlenie\\ +\@studenttitle\ \@course\ \cyrk\cyru\cyrr\cyrs\cyra\ % +\@department\\ +\MakeUppercase{\@author}\\ +\textbf{\CYRT\cyre\cyrm\cyra\ \cyrr\cyra\cyrb\cyro\cyrt\cyrery:} <<{\MakeUppercase{\@title}}>> + +} + +\vfill + +\noindent +\CYRN\cyra\cyru\cyrch\cyrn\cyrery\cyrishrt\ \cyrr\cyru\cyrk\cyro\cyrv% +\cyro\cyrd\cyri\cyrt\cyre\cyrl\cyrsftsn\\ +\signature{\@satitle}{\@saname}\\[14pt] +\CYRZ\cyra\cyrv\cyre\cyrd\cyru\cyryu\cyrshch\cyri\cyrishrt\ \cyrk\cyra% +\cyrf\cyre\cyrd\cyrr\cyro\cyrishrt\\ +\signature{\@chtitle}{\@chname} + +\vfill +{\centering{\cyr\CYRS\cyra\cyrr\cyra\cyrt\cyro\cyrv\ \@date} + +} +\newpage +\begin{center}\bf +C\cyro\cyrd\cyre\cyrr\cyrzh\cyra\cyrn\cyri\cyre\ \cyrr\cyra\cyrb% +\cyro\cyrt\cyrery +\end{center} +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Referat title page +% --------------------------------------------------------------------------% +\newcommand{\RefMakeTitle} +{ +\thispagestyle{empty} +\shapka + +\vspace{3cm} +{\centering +\textbf{\MakeUppercase{\@title}} +\\[0.3cm] +{\@workname} + +} + +\vspace{1.5cm} +\begin{flushleft} +\@studenttitle\ \@course\ \cyrk\cyru\cyrr\cyrs\cyra\ \@group\ \cyrg% +\cyrr\cyru\cyrp\cyrp\cyrery\\ +\@spectype\ \@napravlenie\\ +\@department\\ +\@author +\end{flushleft} +\vfill + +\noindent +\CYRP\cyrr\cyro\cyrv\cyre\cyrr\cyri\cyrl\\ +\signature{\@satitle}{\@saname} + +\vfill +{\centering{\cyr\CYRS\cyra\cyrr\cyra\cyrt\cyro\cyrv\ \@date} + +} +\newpage +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% LabWork2 title page +% --------------------------------------------------------------------------% +\newcommand{\LabTwoMakeTitle} +{ +\thispagestyle{empty} +\shapkatwo + +\vspace{1cm} +\hfill\begin{minipage}{0.4\linewidth} + Кафедра {\@chair} +\end{minipage} + +\vspace{1cm} +{\centering +\textbf{\MakeUppercase{\@title}} +\\[0.3cm] +{\@workname}\\ +<<{\MakeUppercase{\@subject}}>> + +} + +\vspace{1.5cm} +\begin{flushleft} +\@studenttitle\ \@course\ \cyrk\cyru\cyrr\cyrs\cyra\ \@group\ \cyrg\cyrr\cyru\cyrp\cyrp\cyrery\\ +\@spectype\ \@napravlenie\\ +\@department\\ +\centering\@author +\end{flushleft} +\vfill + +\noindent +Преподаватель\\ +\signature{\@satitle}{\@saname} + +\vfill +{\centering{\cyr\CYRS\cyra\cyrr\cyra\cyrt\cyro\cyrv\ \@date} + +} +\newpage +} +% --------------------------------------------------------------------------% + +% --------------------------------------------------------------------------% +% Last page +% --------------------------------------------------------------------------% +\newcommand{\lastpage} +{ +\newpage +\thispagestyle{empty} +\vspace*{11cm} +\@worktype\ <<\@title>>\ \@typework\ \cyrm\cyrn\cyro\cyrishrt\ % +\cyrs\cyra\cyrm\cyro\cyrs\cyrt\cyro\cyrya\cyrt\cyre\cyrl\cyrsftsn\cyrn% +\cyro, \cyri\ \cyrn\cyra\ \cyrv\cyrs\cyre\ \cyri\cyrs\cyrt\cyro\cyrch% +\cyrn\cyri\cyrk\cyri, \cyri\cyrm\cyre\cyryu\cyrshch\cyri\cyre\cyrs% +\cyrya\ \cyrv\ \cyrr\cyra\cyrb\cyro\cyrt\cyre, \cyrd\cyra\cyrn\cyrery\ % +\cyrs\cyro\cyro\cyrt\cyrv\cyre\cyrs\cyrt\cyrv\cyru\cyryu\cyrshch\cyri% +\cyre\ \cyrs\cyrs\cyrery\cyrl\cyrk\cyri.\par +\parindent=9cm +\parbox{8cm}{ +\begin{flushleft} +\hbox to 6cm{\hbox to 3.5cm{\hrulefill}/\hbox to 3.5cm{\hrulefill}/} +\end{flushleft} +} +} + +\AddEnumerateCounter{\Asbuk}{\@Asbuk}{\CYRM} +\AddEnumerateCounter{\asbuk}{\@asbuk}{\cyrm} + +% --------------------------------------------------------------------------% +% enumerations +% --------------------------------------------------------------------------% +\setlist{noitemsep} +%\setlist[1]{labelindent=\parindent} % < Usually a good idea +\setlist[itemize]{ +%leftmargin=52pt, +rightmargin=0pt, +labelsep=7pt, +labelwidth=20pt, +itemindent=0pt, +listparindent=0pt, +topsep=0pt,%4pt plus 2pt minus 4pt, +partopsep=0pt,% plus 1pt minus 1pt, +parsep=0pt,% plus 1pt, +itemsep=0 pt%\parsep +} +\setlist[enumerate]{ +%leftmargin=52pt, +rightmargin=0pt, +labelsep=5pt, +labelwidth=20pt, +itemindent=0pt, +listparindent=0pt, +topsep=0pt,%4pt plus 2pt minus 4pt, +partopsep=0pt,% plus 1pt minus 1pt, +parsep=0pt,% plus 1pt, +itemsep=0pt%\parsep +} +\setlist[itemize,1]{label={\normalfont\bfseries\textemdash}} +%\setlist[enumerate]{labelsep=*, leftmargin=1.5pc} +\setlist[enumerate,1]{label=\arabic*., ref=\arabic*} +\setlist[enumerate,2]{label=\emph{\asbuk*}), ref=\theenumi.\emph{\asbuk*}} +\setlist[enumerate,3]{label=\roman*., ref=\theenumii.\roman*} +\setlist[enumerate,4]{label=\Asbuk*., ref=\theenumiii.\Asbuk*} +%\setlist[description]{font=\sffamily\bfseries} + +%%%\renewcommand{\@listI}{% +%%%\leftmargin=52pt +%%%\rightmargin=0pt +%%%\labelsep=7pt +%%%\labelwidth=20pt +%%%\itemindent=0pt +%%%\listparindent=0pt +%%%\topsep=4pt plus 2pt minus 4pt +%%%\partopsep=0pt plus 1pt minus 1pt +%%%\parsep=0pt plus 1pt +%%%\itemsep=\parsep} + +%%%\renewcommand\theenumi {\@arabic\c@enumi} +%%%\renewcommand\theenumii {\asbuk{enumii}} +%%%\renewcommand\theenumiii{\@roman\c@enumiii} +%%%\renewcommand\theenumiv {\Asbuk{enumiv}} +%%%\newcommand\atheenumi{\asbuk{enumi}} +%%%\newcommand\atheenumii{\asbuk{enumii}} +%%%\renewcommand\labelenumi {\theenumi.} +%%%\renewcommand\labelenumii {\theenumii.} +%%%\renewcommand\labelenumiii{\theenumiii.} +%%%\renewcommand\labelenumiv {\theenumiv.} +%%%\renewcommand\p@enumii {\theenumi} +%%%\renewcommand\p@enumiii {\theenumi.\theenumii} +%%%\renewcommand\p@enumiv {\p@enumiii.\theenumiii} +%%%\renewcommand\labelitemi {\normalfont\bfseries\textemdash} +%%%\renewcommand\labelitemii {\normalfont\bfseries\textendash} +%%%\renewcommand\labelitemiii{\textperiodcentered} +%%%\renewcommand\labelitemiv {\textasteriskcentered} +%%% +%%%\renewcommand{\@listI}{% +%%%\leftmargin=52pt +%%%\rightmargin=0pt +%%%\labelsep=7pt +%%%\labelwidth=20pt +%%%\itemindent=0pt +%%%\listparindent=0pt +%%%\topsep=4pt plus 2pt minus 4pt +%%%\partopsep=0pt plus 1pt minus 1pt +%%%\parsep=0pt plus 1pt +%%%\itemsep=\parsep} +% --------------------------------------------------------------------------% + + +% --------------------------------------------------------------------------% +% References +% --------------------------------------------------------------------------% +\makeatletter +\def\@biblabel#1{#1 } + +\renewenvironment{thebibliography}[1] +{ + \starsection{\cyr\CYRS\CYRP\CYRI\CYRS\CYRO\CYRK\ \CYRI\CYRS\CYRP\CYRO\CYRL% + \CYRSFTSN\CYRZ\CYRO\CYRV\CYRA\CYRN\CYRN\CYRERY\CYRH\ \CYRI\CYRS\CYRT% + \CYRO\CYRCH\CYRN\CYRI\CYRK\CYRO\CYRV} + \list{\@biblabel{\@arabic\c@enumiv}}% + {\settowidth\labelwidth{\@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \setlength{\itemsep}{0pt} + \@openbib@code + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{\@arabic\c@enumiv}}% + \sloppy + \clubpenalty4000 + \@clubpenalty \clubpenalty + \widowpenalty4000% + \sfcode`\.\@m} +{\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} + +\makeatother +% --------------------------------------------------------------------------% diff --git a/lab1/report/images/mat3.png b/lab1/report/images/mat3.png Binary files differnew file mode 100644 index 0000000..7b8ec90 --- /dev/null +++ b/lab1/report/images/mat3.png diff --git a/lab1/report/images/mat4.png b/lab1/report/images/mat4.png Binary files differnew file mode 100644 index 0000000..5b694e5 --- /dev/null +++ b/lab1/report/images/mat4.png diff --git a/lab1/report/images/mat4_id.png b/lab1/report/images/mat4_id.png Binary files differnew file mode 100644 index 0000000..45e3c7e --- /dev/null +++ b/lab1/report/images/mat4_id.png diff --git a/lab1/report/lab1.tex b/lab1/report/lab1.tex new file mode 100644 index 0000000..75180e4 --- /dev/null +++ b/lab1/report/lab1.tex @@ -0,0 +1,459 @@ +\documentclass[spec, och, labwork2]{SCWorks} +\usepackage{preamble} + +\begin{document} +\include{titlepage.tex} +\tableofcontents + +\section{Постановка задачи} + +Цель работы --- изучение основных свойств бинарных отношений и операций замыкания бинарных отношений. +Порядок выполнения работы: +\begin{enumerate} + \item + Разобрать основные определения видов бинарных отношений и разработать + алгоритмы классификации бинарных отношений; + \item + Изучить свойства бинарных отношений и рассмотреть основные системы + замыкания на множестве бинарных отношений; + \item Разработать алгоритмы построения основных замыканий бинарных отношений. +\end{enumerate} + +\section{Теоретические сведения} + +\subsection{Основные определения видов бинарных отношений} + +Подмножества декартова произведения $A_1 \times \dots \times A_n$ множеств +$A_1, \dots, A_n$ называются $n$-ыми отношениями между элементами множеств +$A_1, \dots, A_n$. + +Подмножества декартова произведения $A \times B$ множеств $A$ и $B$ называются +бинарными отношениями между элементами множеств $A$ и $B$. + +Для бинарного отношения $\rho \subset A \times B$ область определения $D_\rho$ и +множество значений $E_\rho$ определяется как подмножества соответствующих +множеств $A$ и $B$ по следующим формулам: +\begin{align*} + D_\rho &= \left\{ a: (a, b) \in \rho \text{ для некоторого } b \in B \right\} \\ + E_\rho &= \left\{ b: (a, b) \in \rho \text{ для некоторого } a \in A \right\} +\end{align*} + +Бинарное отношение $\rho \subset A \times A$ называется: +\begin{enumerate} + \item \textit{рефлексивным}, если $(\forall a \in A) ~ (a, a) \in \rho$; + \item + \textit{антирефлексивным}, если + $(\forall a \in A) ~ (a, a) \not\in \rho$; + \item + \textit{симметричным}, если + $(\forall a, b \in A) ~ (a, b) \in \rho \implies (b,a) \in \rho$; + \item + \textit{антисимметричным}, если + $(\forall a, b \in A) ~ (a, b) \in \rho \land (b, a) \in \rho \implies a = b$; + \item + \textit{транзитивным}, если + $(\forall a, b, c \in A) ~ (a, b) \in \rho \land (b, c) \in \rho \implies (a, c) \in \rho$. +\end{enumerate} + +Символом $\Delta_A$ обозначается тождественное отношение на множестве $A$, +которое определяется по формуле: $\Delta_A = \{ (a, a) | a \in A \}$. + +Тогда бинарное отношение $\rho \subset A \times A$ является: +\begin{itemize} + \item + \textit{рефлексивным} $\iff$ $\Delta_A \subset \rho$. Это означает, что + бинарное отношение $\rho$ рефлексивно, если $M(\rho) \geq E$, где $E$ + --- единичная матрица. Если же матрица $M(\rho)$ несравнима с единичной + матрицей, то бинарное отношение $\rho$ не является рефлексивным; + \item + \textit{симметричным} $\iff$ $\rho^{-1} \subset \rho$. Это означает, что + бинарное отношение $\rho$ симметрично, если $M(\rho) \geq M(\rho)^T$, + где $M(\rho)^T$ – транспонированная матрица бинарного отношения $\rho$. + Если же матрица $M(\rho)$ несравнима с $M(\rho)^T$, то бинарное + отношение $\rho$ не является симметричным; + \item + \textit{антисимметричным} $\iff$ $\rho \cap \rho^{-1} \subset \Delta_A$. + Это означает, что бинарное отношение $\rho$ антисимметрично, если $E + \geq M(\rho) M(\rho)^T$ (значения элементов вне главной диагонали + матрицы $M(\rho) M(\rho)^T$ равны нулю); + \item + \textit{транзитивным} $\iff$ $\rho \rho \subset \rho$. Это означает, что + бинарное отношение $\rho$ транзитивно, если $M(\rho)M(\rho) \leq + M(\rho)$. + + +\end{itemize} + +Классификация бинарных отношений: +\begin{enumerate} + \item + Рефлексивное и транзитивное отношение называется отношением + \textit{квазипорядка}. + \item + Рефлексивное, симметричное и транзитивное отношение называется + отношением \textit{эквивалентности}. + \item + Рефлексивное антисимметричное транзитивное отношение называется + отношением \textit{частичного порядка}. + \item + Антирефлексивное, антисимметричное и транзитивное отношение называется + отношением \textit{строгого порядка}. +\end{enumerate} + +\subsection{Основные системы замыкания на множестве бинарных отношений} + +\textit{Замыканием} отношения $R$ относительно свойства $P$ называется такое +множество $R^*$, что: +\begin{enumerate} + \item $R \subset R^*$. + \item $R^*$ обладает свойством $P$. + \item + $R^*$ является подмножеством любого другого отношения, содержащего $R$ и + обладающего свойством $P$. +\end{enumerate} + +Множество Z подмножеств множества A называется \textit{системой замыканий}, если +оно замкнуто относительно пересечений, т.е. выполняется +\begin{equation*} + (\forall B \subset Z) ~ \bigcap B \in Z +\end{equation*} + +\begin{lemma}[О системах замыканий бинарных отношений] + На множестве $P(A^2)$ всех бинарных отношений между элементами множества $A$ + следующие множества являются системами замыканий: + \begin{enumerate} + \item + $Z_r$ - множество всех рефлексивных бинарных отношений между + элементами множества $A$; + \item + $Z_s$ – множество всех симметричных бинарных отношений между + элементами множества $A$; + \item + $Z_t$ – множество всех транзитивных бинарных отношений между + элементами множества $A$; + \item + $Z_{eq} = Eq(A)$ – множество всех отношений эквивалентности на + множестве $A$. + \end{enumerate} + + Множество $Z_{as}$ всех антисимметричных бинарных отношений между элементами + множества $A$ не является системой замыкания. +\end{lemma} + +\begin{lemma} + На множестве $P(A^2)$ всех бинарных отношений между элементами множества A + следующие отображения являются операторами замыканий: + \begin{enumerate} + \item + $f_r(\rho) = \delta \cup \Delta_A$ --- наименьшее рефлексивное + бинарное отношение, содержащее отношение $\rho \subset A^2$; + \item + $f_s(\rho) = \delta \cup \delta^{-1}$ --- наименьшее симметричное + бинарное отношение, содержащее отношение $\rho \subset A^2$; + \item + $f_t(\rho) = \bigcup_{n = 1}^\infty \rho^n$ наименьшее транзитивное + бинарное отношение, содержащее отношение $\rho \subset A^2$; + \item + $f_{eq} = f_t f_s f_r (\rho)$ наименьшее отношение эквивалентности, + содержащее отношение $\rho \subset A^2$; + \end{enumerate} + +\end{lemma} + +\section{Алгоритмы классификации бинарных отношений} + +%%% +\subsection{Проверка бинарного отношения на рефлексивность} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является рефлексивным>> или <<Отношение не является +рефлексивным>>. + +\begin{enumerate} + \item Взять диагональ матрицы $d(M) = \{ M_{ii} | i = \overline{1, N} \}$; + \item + Если $\exists a = 0 \in d(M)$, то ответ <<Отношение не является + рефлексивным>>; + \item Иначе ответ <<Отношение является рефлексивным>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N)$. + +%%% +\subsection{Проверка бинарного отношения на антирефлексивность} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является антирефлексивным>> или <<Отношение не +является антирефлексивным>>. + +\begin{enumerate} + \item Взять диагональ матрицы $d(M) = \{ M_{ii} | i = \overline{1, N} \}$; + \item + Если $\exists a = 1 \in d(M)$, то ответ <<Отношение не является + антирефлексивным>>; + \item Иначе ответ <<Отношение является антирефлексивным>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N)$. + +%%% +\subsection{Проверка бинарного отношения на симметричность} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является симметричным>> или <<Отношение не +является симметричным>>. + +\begin{enumerate} + \item Вычислить транспонированную матрицу $M^T$; + \item Если $M = M^T$, то ответ <<Отношение является симметричным>>; + \item Иначе ответ <<Отношение не является симметричным>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Проверка бинарного отношения на антисимметричность} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является антисимметричным>> или <<Отношение не +является антисимметричным>>. + +\begin{enumerate} + \item Вычислить транспонированную матрицу $M^T$; + \item Вычислить матрицу $A = M \times M^T$; + \item + Если $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) : i + \ne j$ выполняется $(A_{ij} = 0)$, то ответ <<Отношение + является антисимметричным>>; + \item Иначе ответ <<Отношение не является антисимметричным>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Проверка бинарного отношения на транзитивность} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является транзитивным>> или <<Отношение не является +транзитивным>>. + +\begin{enumerate} + \item Вычислить матрицу $A = M \times M$; + \item Если $A \leq M$, то ответ <<Отношение является транзитивным>>; + \item Иначе ответ <<Отношение не является транзитивным>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Классификация отношения как квазипорядка} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является квазипорядком>> или <<Отношение не является +квазипорядком>>. + +\begin{enumerate} + \item Выяснить является ли отношение рефлексивным; + \item Выяснить является ли отношение транзитивным; + \item + Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение + является квазипорядком>>; + \item Иначе ответ <<Отношение не является квазипорядком>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Классификация отношения как эквивалентности} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является эквивалентностью>> или <<Отношение не +является эквивалентностью>>. + +\begin{enumerate} + \item Выяснить является ли отношение рефлексивным; + \item Выяснить является ли отношение симметричным; + \item Выяснить является ли отношение транзитивным; + \item + Если на шагах 1, 2 и 3 получены положительные ответы, то ответ + <<Отношение является эквивалентностью>>; + \item Иначе ответ <<Отношение не является эквивалентностью>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Классификация отношения как частичного порядка} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является частичным порядком>> или <<Отношение не +является частичным порядком>>. + +\begin{enumerate} + \item Выяснить является ли отношение антисимметричным; + \item Выяснить является ли отношение транзитивным; + \item + Если на шагах 1 и 2 получены положительные ответы, то ответ + <<Отношение является частичным порядком>>; + \item Иначе ответ <<Отношение не является частичным порядком>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Классификация отношения как строгого порядка} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} <<Отношение является строгим порядком>> или <<Отношение не +является строгим порядком>>. + +\begin{enumerate} + \item Выяснить является ли отношение антирефлексивным; + \item Выяснить является ли отношение антисимметричным; + \item Выяснить является ли отношение транзитивным; + \item + Если на шагах 1, 2 и 3 получены положительные ответы, то ответ + <<Отношение является строгим порядком>>; + \item Иначе ответ <<Отношение не является строгим порядком>>. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +\section{Алгоритмы построения основных замыканий бинарных отношений} + +%%% +\subsection{Алгоритм построения рефлексивного замыкания} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} Матрица $M'(M(\rho))$ рефлексивного замыкания. + +\begin{enumerate} + \item + $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ + M'_{ij} = \begin{cases} + 1, &i = j \\ + M_{ij}, &i \ne j + \end{cases}$ +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Алгоритм построения симметричного замыкания} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} Матрица $M'(M(\rho))$ симметричного замыкания. + +\begin{enumerate} + \item + $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ + M'_{ij} = \begin{cases} + 1, &M_{ij} = 1 \lor M_{ji} = 1\\ + 0, &M_{ij} = 0 \land M_{ji} = 0 + \end{cases}$ +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^2)$. + +%%% +\subsection{Алгоритм построения транзитивного замыкания} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} Матрица $M'(M(\rho))$ транзитивного замыкания. + +\begin{enumerate} + \item + $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ + (\forall k = \overline{1, N}) ~ + M'_{ij} = \begin{cases} + 1, &M_{ik} = 1 \land M_{kj} = 1\\ + 0, &\text{в иных случаях} + \end{cases}$; + \item Шаг 1 необходимо повторить $N$ раз. +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^4)$. + +%%% +\subsection{Алгоритм построения эквивалентного замыкания} + +\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности +$N \times N$. + +\textit{Выход.} Матрица $M'(M(\rho))$ эквивалентного замыкания. + +\begin{enumerate} + \item + Вычислим матрицу $M_1 = \texttt{refl}(M)$, где \texttt{refl} --- + алгоритм построения рефлексивного замыкания; + \item + Вычислим матрицу $M_2 = \texttt{symm}(M)$, где \texttt{symm} --- + алгоритм построения симметричного замыкания; + \item + Вычислим матрицу $M' = \texttt{trans}(M)$, где \texttt{trans} --- + алгоритм построения транзитивного замыкания; +\end{enumerate} + +Трудоёмкость алгоритма --- $O(N^4)$. + +\section{Программная реализация} + +\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab1.py} + +\section{Результаты тестирования} + +Ниже представлены результаты запуска программы на некоторых бинарных отношениях. + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{mat3.png} + \caption{} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{mat4.png} + \caption{} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.9\textwidth]{mat4_id.png} + \caption{} +\end{figure} + +\conclusion + +В ходе выполнения данной лабораторной работы были изучены основные свойства +бинарных отношений, а также операций замыкания бинарных отношений. Были +разработаны алгоритмы классификации бинарных отношений, а также были произведена +оценка сложности вычисления данных алгоритмов. Также были разработаны алгоритмы +построения замыканий бинарных отношений на основе алгоритмов их классификации. +Программная реализация на языке Python с библиотекой numpy успешно прошла +тестирование. + +\end{document} diff --git a/lab1/report/preamble.sty b/lab1/report/preamble.sty new file mode 100644 index 0000000..890063f --- /dev/null +++ b/lab1/report/preamble.sty @@ -0,0 +1,51 @@ +\usepackage{subfigure} +\usepackage{tikz,pgfplots} +\pgfplotsset{compat=1.5} +\usepackage{float} +\setcounter{secnumdepth}{4} +\titleformat{\paragraph}[block] +{\hspace{1.25cm}\normalfont} +{\theparagraph}{1ex}{} +\titlespacing{\paragraph} +{0cm}{2ex plus 1ex minus .2ex}{.4ex plus.2ex} + +% --------------------------------------------------------------------------% + + +\usepackage[T2A]{fontenc} +\usepackage[utf8]{inputenc} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{tempora} +\usepackage{minted} + +% \usepackage[sort,compress]{cite} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{amsthm} +\usepackage{fancyvrb} +\usepackage{listings} +\usepackage{listingsutf8} +\usepackage{longtable} +\usepackage{array} +\usepackage[english,russian]{babel} +% \usepackage[colorlinks=false]{hyperref} +\usepackage{url} + +\usepackage[parentracker=true, + backend=biber, + hyperref=false, + language=russian, + autolang=other, + citestyle=gost-numeric, + defernumbers=true, + bibstyle=gost-numeric, +]{biblatex} +\addbibresource{sources.bib} +\usepackage{csquotes} + + +\newcommand{\eqdef}{\stackrel {\rm def}{=}} +\renewcommand\theFancyVerbLine{\small\arabic{FancyVerbLine}} +\newtheorem{lemma}{Лемма} +\newtheorem*{lemma*}{Лемма}
\ No newline at end of file diff --git a/lab1/report/titlepage.tex b/lab1/report/titlepage.tex new file mode 100644 index 0000000..4570220 --- /dev/null +++ b/lab1/report/titlepage.tex @@ -0,0 +1,54 @@ +\selectlanguage{russian} +\chair{теоретических основ компьютерной безопасности и криптографии} +\title{Классификация бинарных отношений и системы замыканий} +\course{3} +\group{331} +\department{факультета компьютерных наук и информационных технологий} +\napravlenie{10.05.01 "--- Компьютерная безопасность} +\subject{Прикладная универсальная алгебра} + +% Для студентки. Для работы студента следующая команда не нужна. +% \studenttitle{Студентки} + +% Фамилия, имя, отчество в родительном падеже +\author{Гущина Андрея Юрьевича} + +% Заведующий кафедрой +\chtitle{д.ф.-м.н.} % степень, звание +\chname{М. Б. Абросимов} + +%Научный руководитель (для реферата преподаватель проверяющий работу) +\satitle{аспирант} %должность, степень, звание +\saname{В. Н. Кутин} + +% Руководитель практики от организации (только для практики, +% для остальных типов работ не используется) +% \patitle{к.ф.-м.н.} +% \paname{С.~В.~Миронов} + +% Семестр (только для практики, для остальных +% типов работ не используется) +%\term{8} + +% Наименование практики (только для практики, для остальных +% типов работ не используется) +%\practtype{преддипломная} + +% Продолжительность практики (количество недель) (только для практики, +% для остальных типов работ не используется) +%\duration{4} + +% Даты начала и окончания практики (только для практики, для остальных +% типов работ не используется) +%\practStart{30.04.2019} +%\practFinish{27.05.2019} + +% Год выполнения отчета +\date{2022} + +\maketitle + +% Включение нумерации рисунков, формул и таблиц по разделам +% (по умолчанию - нумерация сквозная) +% (допускается оба вида нумерации) +% \secNumbering
\ No newline at end of file |