diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-05-29 12:06:47 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-05-29 12:06:47 +0400 |
| commit | 8e4c33ae45537211cbf50d236461fe6045f9ded1 (patch) | |
| tree | 71a503241df66080640d5f4a9f3a06abce72340d | |
| parent | c04fd874af4e641aeeba2e4a4a991fd81225a5d3 (diff) | |
| -rw-r--r-- | lab2/lab2.py | 391 | ||||
| -rw-r--r-- | lab2/report/SCWorks.cls | 991 | ||||
| -rw-r--r-- | lab2/report/images/hasse.png | bin | 0 -> 408698 bytes | |||
| -rw-r--r-- | lab2/report/images/test1.png | bin | 0 -> 524767 bytes | |||
| -rw-r--r-- | lab2/report/images/test2.png | bin | 0 -> 494291 bytes | |||
| -rw-r--r-- | lab2/report/images/test3.png | bin | 0 -> 479274 bytes | |||
| -rw-r--r-- | lab2/report/images/test4.png | bin | 0 -> 503201 bytes | |||
| -rw-r--r-- | lab2/report/lab2.tex | 247 | ||||
| -rw-r--r-- | lab2/report/preamble.sty | 54 | ||||
| -rw-r--r-- | lab2/report/titlepage.tex | 54 | ||||
| -rw-r--r-- | lab2/report/tmp/algo.tex | 280 | ||||
| -rw-r--r-- | lab2/test1.txt | 7 | ||||
| -rw-r--r-- | lab2/test2.txt | 8 | ||||
| -rw-r--r-- | lab2/test3.txt | 10 | ||||
| -rw-r--r-- | lab2/test4.txt | 7 | ||||
| -rw-r--r-- | lab3/tests.txt | 36 | ||||
| -rw-r--r-- | lab4/test2.txt | 11 | ||||
| -rw-r--r-- | lab4/test3.txt | 8 | ||||
| -rw-r--r-- | lab5/test.txt | 5 |
19 files changed, 2109 insertions, 0 deletions
diff --git a/lab2/lab2.py b/lab2/lab2.py new file mode 100644 index 0000000..e1616a9 --- /dev/null +++ b/lab2/lab2.py @@ -0,0 +1,391 @@ +import numpy as np +import math +import matplotlib.pyplot as plt + + +def check_reflexivity(matrix): + diag_values = np.diagonal(matrix) + diag_values = np.unique(diag_values) + return int(diag_values.size == 1 and diag_values == [1]) + + +def check_antisymmetry(matrix): + new_matrix = np.multiply(matrix, matrix.T) + for i in range(len(new_matrix)): + for j in range(len(new_matrix[i])): + if i != j and new_matrix[i][j] != 0: + return 0 + return 1 + + +def check_transitivity(matrix): + mlp_mx = np.matmul(matrix, matrix) + for i in range(len(mlp_mx)): + for j in range(len(mlp_mx[i])): + if mlp_mx[i][j] > 1: + mlp_mx[i][j] = 1 + return int((mlp_mx <= matrix).all()) + + +def order_check(relation): + return check_antisymmetry(relation) and \ + check_reflexivity(relation) and \ + check_transitivity(relation) + +############################ + +def reflexive_closure(matrix): + n = len(matrix) + for i in range(n): + matrix[i][i] = 1 + + +def symmetry_closure(matrix): + n = len(matrix) + for i in range(n): + for j in range(n): + if matrix[i][j]: + matrix[j][i] = 1 + + +def transitive_closure(matrix): + n = len(matrix) + 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] = 1 + + +def create_equivalent_closure(bin_relation): + relation = bin_relation.copy() + reflexive_closure(relation) + symmetry_closure(relation) + transitive_closure(relation) + return relation + +################################### + +def get_slices_list(relation_matrix, for_factor_set=1, attributes=None): + n = len(relation_matrix) + slices = [] + for i in range(n): + slice = [] + for j in range(n): + if relation_matrix[i][j]: + if attributes is None: + slice.append(j + for_factor_set) + else: + slice.append(attributes[j]) + slices.append(slice) + return slices + + +def create_factor_set(bin_relation): + slices = get_slices_list(bin_relation, 1, None) + print("Фактор-множество данной эквивалентности:") + print(set(map(tuple, slices))) + return slices + + +def create_representative_system(factor_set): + factor_set = sorted(factor_set, key=len) + d = {} + representative_system = [] + for eq_class in factor_set: + for representative in eq_class: + if representative not in representative_system: + d[representative] = eq_class + representative_system.append(representative) + break + + print("Система представителей данного фактор-множества:") + print(representative_system) + for representative, eq_class in d.items(): + print(representative, "принадлежит множеству", eq_class) + + +#################################################### + +def get_dividers(l): + d = {} + for elem in l: + dividers = [] + for divider in l: + if elem % divider == 0: + dividers.append(divider) + d[elem] = dividers + + return d + + +def get_min_elem(objects, elements, k=0): + min_elements = [] + for i in range(k, len(objects)): + is_min = True + for j in range(k, len(objects)): + if objects[j][i] != 0 and i != j: + is_min = False + if is_min: + min_elements.append(elements[i]) + return min_elements + + +def get_max_elem(some_set, objs, k=0): + max_elements = [] + for i in range(k, len(some_set)): + is_max = True + for j in range(k, len(some_set)): + if some_set[i][j] != 0 and i != j: + is_max = False + if is_max: + max_elements.append(objs[i]) + + return max_elements + + +def get_least_elem(some_set, objs): + min_elem_list = get_min_elem(some_set, objs) + if len(min_elem_list) != 1: + return None + else: + return min_elem_list[0] + + +def get_greatest_elem(some_set, objs): + max_elem_list = get_max_elem(some_set, objs) + if len(max_elem_list) != 1: + return None + else: + return max_elem_list[0] + + +def get_order_set_elem(): + objs = [] + print('Введите элементы множества:') + objs = input().split() + print("Введите значения матрицы бинарного отношения:") + n = len(objs) + entries = [list(map(int, input().split())) for i in range(n)] + some_set = np.array(entries).reshape(n, n) + if not order_check(some_set): + print("Введённое отношение не является отношением порядка") + return 0 + + print("Минимальные элементы в множестве:", get_min_elem(some_set, objs)) + print("Максимальные элементы в множестве:", get_max_elem(some_set, objs)) + print("Наименьший элемент в множестве:", get_least_elem(some_set, objs)) + print("Наибольший элемент в множестве:", get_greatest_elem(some_set, objs)) + +########################################### + +def get_dividers_list(n): + dividers_list = [1] + for i in range(2, int(math.sqrt(n)) + 1): + if n % i == 0: + dividers_list.append(i) + dividers_list.append(n // i) + dividers_list.append(n) + return sorted(dividers_list) + + +def make_hasse(): + print('Введите элементы множества:') + objs = input().split() + n = len(objs) + print("Введите значения матрицы бинарного отношения:") + entries = [list(map(int, input().split())) for _ in range(n)] + some_set = np.array(entries).reshape(n, n) + if not order_check(some_set): + print("Введенное отношение не является отношением порядка") + return [] + + hasse_levels = {key: 1 for key in objs} + i = 0 + some_k = 0 + while True: + min_elems = get_min_elem(some_set, objs, some_k) + i += 1 + + if not min_elems: + break + + for elem in min_elems: + hasse_levels[elem] = i + + some_k += len(min_elems) + + connected_values_dict = {} + for key, value in hasse_levels.items(): + lvl_diff = 1 + connected_values = [] + relation_list = get_slices_list(some_set, 0, objs)[objs.index(key)] + for i in relation_list: + if hasse_levels[i] == value + lvl_diff: + connected_values.append(i) + + connected_values = list(set(connected_values)) + connected_values.sort() + connected_values_dict[key] = connected_values + + hasse_data = [] + for i in hasse_levels: + hasse_data.append([i, hasse_levels[i], connected_values_dict[i]]) + + # связи здесь построены снизу-вверх + return hasse_data + + +def visualize_hasse(hasse_data): + plt.xlim(-1.0, len(hasse_data) * 2) + plt.ylim(0, len(hasse_data) * 3 + 1.5) + + lvl_to_elems = {key[1]: 0 for key in hasse_data} + for hasse_elem in hasse_data: + for level in lvl_to_elems: + if hasse_elem[1] == level: + lvl_to_elems[level] += 1 + + max_lvl_elem_amount = lvl_to_elems[max(lvl_to_elems, key=lvl_to_elems.get)] + + lvl = 4 + elem_address = {} + for hasse_elem in hasse_data: + elem_lvl = hasse_elem[1] + elem = hasse_elem[0] + hasse_elem_y = elem_lvl * lvl + hasse_elem_x = 1.5 * (max_lvl_elem_amount - lvl_to_elems[elem_lvl]) + lvl_to_elems[elem_lvl] += -1 + plt.text(hasse_elem_x - 0.1, hasse_elem_y - 0.1, f'{elem}') + plt.scatter(hasse_elem_x + 0.1, hasse_elem_y + 0.1, s=350, facecolors='none', edgecolors='black') + elem_address[elem] = [hasse_elem_x + 0.1, hasse_elem_y + 0.1] + + for hasse_elem in hasse_data: + x1, y1 = elem_address[hasse_elem[0]][0], elem_address[hasse_elem[0]][1] + for connected_elem in hasse_elem[2]: + plt.plot([x1, elem_address[connected_elem][0]], + [y1 + 1, elem_address[connected_elem][1] - 1], + color="black") + + plt.show() + +######################################################### + +def get_closure_system(rel_matrix, objs, attrs): + closure_system = [objs] + row_slices = get_slices_list(rel_matrix.copy().T, 1, objs) + is_empty_included = False + for attr_i in range(len(attrs)): + after_intersection = [list(row_slices[attr_i])] + for closure_i in range(len(closure_system)): + cs_set = set(closure_system[closure_i]) + intersection = set(row_slices[attr_i]) & cs_set + intersection = sorted(intersection) + if intersection not in after_intersection \ + and intersection or not is_empty_included: + after_intersection.append(intersection) + + if not intersection: + is_empty_included = True + + if after_intersection not in closure_system: + closure_system += after_intersection + + new_closure_system = [] + for closure in closure_system: + if closure not in new_closure_system: + new_closure_system.append(closure) + + print("Система замыканий:", new_closure_system) + return closure_system + + +def get_context(closure, rel_matrix, objs, attrs): + if not closure: + context = attrs + else: + column_slices = get_slices_list(rel_matrix, 1, attrs) + list_of_sets = [] + for elem in closure: + obj_i = objs.index(elem) + list_of_sets.append(set(column_slices[obj_i])) + + context = list_of_sets[0] + for cur_set in list_of_sets: + context = context.intersection(cur_set) + + return sorted(context) + + +def make_lattice_concept(): + print("Введите элементы множества:") + objects = input().split() + print("Введите множество атрибутов:") + attributes = input().split() + print('Введите матрицу отношения на декартовом произведении множеств объектов и атрибутов:') + entries = [] + for _ in range(len(objects)): + entries.extend(map(int, input().split())) + relation_matrix = np.array(entries).reshape(len(objects), len(attributes)) + closure_system = get_closure_system(relation_matrix, objects, attributes) + + lattice_concept = [] + for closure in closure_system: + context = get_context(closure, relation_matrix, objects, attributes) + concept = closure, context + lattice_concept.append(concept) + + new_lattice_concept = [] + for concept in lattice_concept: + if concept not in new_lattice_concept: + new_lattice_concept.append(concept) + + print("Решетка концептов:", new_lattice_concept) + +################################################## + +def main(): + print("1. Эквивалентное замыкание, система представителей") + print("2. минимальные и максимальные элементы") + print("3. Построение диаграммы Хассе") + print("4. Построение решётки концептов") + task = int(input("Выберите задачу: ")) + + if task == 1: + n = int(input("Введите размер матрицы: ")) + l = [] + + print(f"На следующих {n} строках введите матрицу:") + for _ in range(n): + l.extend(map(int, input().split())) + matrix = np.array(l, dtype=bool).reshape(n, n) + + # 1 - эквивалентное замыкание + eq = create_equivalent_closure(matrix) + print("Матрица эквивалентного замыкания:") + print(eq.astype(int)) + + # 2 - система представителей + factor_set = create_factor_set(matrix) + create_representative_system(factor_set) + + elif task == 2: + + # 3 - минимальные (максимальные) и наименьший (наибольший) элементы множества + get_order_set_elem() + + elif task == 3: + # 4 - Диаграмма Хассе + hasse_data = make_hasse() + if hasse_data: + print(hasse_data) + visualize_hasse(hasse_data) + + elif task == 4: + # 5 - Решётка концептов + make_lattice_concept() + + +if __name__ == "__main__": + main()
\ No newline at end of file diff --git a/lab2/report/SCWorks.cls b/lab2/report/SCWorks.cls new file mode 100644 index 0000000..f905804 --- /dev/null +++ b/lab2/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/lab2/report/images/hasse.png b/lab2/report/images/hasse.png Binary files differnew file mode 100644 index 0000000..0eb0d9f --- /dev/null +++ b/lab2/report/images/hasse.png diff --git a/lab2/report/images/test1.png b/lab2/report/images/test1.png Binary files differnew file mode 100644 index 0000000..52f55fa --- /dev/null +++ b/lab2/report/images/test1.png diff --git a/lab2/report/images/test2.png b/lab2/report/images/test2.png Binary files differnew file mode 100644 index 0000000..495de7f --- /dev/null +++ b/lab2/report/images/test2.png diff --git a/lab2/report/images/test3.png b/lab2/report/images/test3.png Binary files differnew file mode 100644 index 0000000..8998ddd --- /dev/null +++ b/lab2/report/images/test3.png diff --git a/lab2/report/images/test4.png b/lab2/report/images/test4.png Binary files differnew file mode 100644 index 0000000..a4fe9aa --- /dev/null +++ b/lab2/report/images/test4.png diff --git a/lab2/report/lab2.tex b/lab2/report/lab2.tex new file mode 100644 index 0000000..9ea1ffb --- /dev/null +++ b/lab2/report/lab2.tex @@ -0,0 +1,247 @@ +\documentclass[spec, och, labwork2]{SCWorks} +\usepackage{preamble} + +\begin{document} +\include{titlepage.tex} +\tableofcontents + +\section{Постановка задачи} + +Цель работы "--- изучение основных свойств бинарных отношений и операций +замыкания бинарных отношений. Порядок выполнения работы: + +\begin{enumerate} + \item + Разобрать определения отношения эквивалентности, фактор-множества. + Разработать алгоритмы построения эквивалентного замыкания бинарного + отношения и системы представителей фактор-множества. + \item + Разобрать определения отношения порядка и диаграммы Хассе. Разработать + алгоритмы вычисления минимальных (максимальных) и наименьших (наибольших + элементов и построения диаграммы Хассе. + \item + Разобрать определения контекста и концепта. Разработать алгоритм вычисления + решетки концептов. +\end{enumerate} + + +\section{Теоретические сведения} + +\subsection{Отношения эквивалентности и фактор"=множества} + +Бинарное отношение $\varepsilon$ на множестве $A$ называется отношением +эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично +и транзитивно. + +Для любого подмножества $X \subset A$ множество $\rho(X) = \{b \in B: (x, b) \in +\rho \text{ для некоторого } x \in X\}$ называется образом множества $X$ +относительно отношения $\rho$. + +Образ одноэлементного множества $X = \{a\}$ относительно отношения $\rho$ +обозначается символом $\rho(a)$ и называется также образом элемента $a$ или +срезом отношения $\rho$ через элемент $a$. + +Срезы $\varepsilon(a)$ называются классами эквивалентности по отношению +$\varepsilon$ и сокращенно обозначаются символом $[a]$. Множество всех таких +классов эквивалентности $\{[a]: a \in A\}$ называется фактор"=множеством +множества $A$ по эквивалентности $\varepsilon$ и обозначается символом +$A/\varepsilon$. + +\begin{lemma}[О замыканиях бинарных отношений] + На множестве $P(A^2)$ всех бинарных отношений между элементами множества $A$ + следующие отображения являются операторами замыканий: + \begin{enumerate} + \item + $f_r(\rho) = \rho \cup \triangle_A$ "--- наименьшее рефлексивное бинарное + отношение, содержащее отношение $\rho \subset A^2$, + \item + $f_s(\rho) = \rho \cup \rho^{-1}$ "--- наименьшее симметричное бинарное + отношение, содержащее отношение $\rho \subset A^2$, + \item + $f_t(\rho) = \bigcup^\infty_{n=1} \rho^{n}$ "--- наименьшее транзитивное + бинарное отношение, содержащее отношение $\rho \subset A^2$, + \item + $f_{eq}(\rho) = f_t f_s f_r(\rho)$ "--- наименьшее отношение эквивалентности, + на содержащее отношение $\rho \subset A^2$. + \end{enumerate} +\end{lemma} + + +\subsection{Отношения порядка} + +Бинарное отношение $\omega$ на множестве $A$ называется отношением порядка (или +просто порядком), если оно рефлексивно, антисимметрично и транзитивно. + +Поскольку отношение порядка интуитивно отражает свойство <<больше"=меньше>>, то +для обозначения порядка $\omega$ используется инфиксная запись с помощью символа +$\leq$: вместо $(a, b) \in \omega$ принято писать $a \leq b$ (читается <<a +меньше или равно b>>, <<a содержится в b>> или <<b больше или равно a>>, <<b +содержит a>>). + +Запись $<$ означает, что $a \leq b$ и $a \neq b$. + +Запись $\lessdot$ означает, что $a \leq b$ и нет элементов $x$, удовлетворяющих +условию $a < x < b$. В этом случае говорят, что элемент $b$ покрывает элемент +$a$ или что элемент $a$ покрывается элементом $b$. + +Элементы $a, b \in A$ называются сравнимыми, если $a \leq b$ или $b \leq a$, и +несравнимыми в противном случае. + +Множество $A$ с заданным на нем отношением порядка $\leq$ называется +упорядоченным множеством и обозначается $A = (A, \leq)$ или просто $(A, \leq)$. + +Элемент $a$ упорядоченного множества $(A, \leq)$ называется: +\begin{enumerate} + \item Минимальным, если $(\forall x \in A) \text{ } x \leq a \implies x = a$; + \item Максимальным, если $(\forall x \in A) \text{ } a \leq x \implies x = a$; + \item Наименьшим, если $(\forall x \in A) \text{ } a \leq x$; + \item Наибольшим, если $(\forall x \in A) \text{ } x \leq a$. +\end{enumerate} + +\begin{lemma} + Для любого конечного упорядоченного множества $A = (A, \leq)$ справедливы + следующие утверждения: + \begin{enumerate} + \item + Любой элемент множества $A$ содержится в некотором максимальном элементе и + содержит некоторый минимальный элемент; + \item + Если упорядоченное множество $A$ имеет один максимальный (соответственно, + минимальный) элемент, то он является наибольшим (соответственно, + наименьшим) элементом этого множества. + \end{enumerate} +\end{lemma} + + +\subsection{Диаграммы Хассе} + +Упорядоченное множество $A = (A, \leq)$ наглядно представляется диаграммой +Хассе, которая представляет элементы множества $A$ точками плоскости и пары $a +<\cdot \text{ } b$ представляет линиями, идущими вверх от элемента $a$ к +элементу $b$. + +Алгоритм построения диаграммы Хассе конечного упорядоченного множества $A = (A, +\leq)$. + +\begin{enumerate} + \item + В упорядоченном множестве $A = (A, \leq)$ найти множество $A_1$ всех + минимальных элементов и расположить их в один горизонтальный ряд (это первый + уровень диаграммы). + \item + В упорядоченном множестве $A \setminus A_1$, найти множество $A_2$ всех + минимальных элементов и расположить их в один горизонтальный ряд над первым + уровнем (это второй уровень диаграммы). Соединить отрезками элементы этого + ряда с покрываемыми ими элементами предыдущего ряда. + \item + В упорядоченном множестве $A \setminus (A_1 \cup A_2)$ найти множество $A_3$ + всех минимальных элементов и расположить их в один горизонтальный ряд над + вторым уровнем (это третий уровень диаграммы). Соединить отрезками элементы + этого ряда с покрываемыми ими элементами предыдущих рядов. + \item + Процесс продолжается до тех пор, пока не выберутся все элементы множества + $A$. +\end{enumerate} + + +\subsection{Определение контекста, концепта и решетки} + +Контекстом называется алгебраическая система $K = (G, M, \rho)$, состоящая из +множества объектов $G$, множества атрибутов $M$ и бинарного отношения $\rho +\subset G \times M$, показывающего $(g, m) \in \rho$, что объект $g$ имеет +атрибут $m$. + +Упорядоченная пара $(X, Y)$ замкнутых множеств $X \in Z_{f_G}, Y \in Z_{f_M}$, +удовлетворяющих условиям $\varphi(X) = Y$, $\psi(Y) = X$, называется концептом +контекста $K = (G, M, \rho)$. При этом компонента $X$ называется объемом и +компонента $Y$ "--- содержанием концепта $(X, Y)$. + +Порядок $\leq$ на множестве $A$ называется решеточным, если $\forall a, b \in A$ +существуют $sup \{a, b\}$ и $inf \{a, b\}$, которые обозначаются соответственно +$a \vee b$, $a \wedge b$ и называются также объединением и пересечением +элементов $a, b$. Множество с заданным на нем решеточным порядком называется +решеточно упорядоченным множеством или решеткой. + +Решетка $A$ называется полной, если любое ее подмножество $X \subset A$ имеет +точные грани $\text{inf} ~ X$ и $\text{sup} ~ X$. + +\begin{theorem}[О полной решетке] + Если в упорядоченном множестве $A$ каждое подмножество имеет точную верхнюю + грань, то $A$ является полной решеткой. + + Множество всех концептов $C(K)$ так упорядочивается отношением $(X, Y) \leq + (X_1, Y_1) \Leftrightarrow X \subset X_1$ (или равносильно $Y_1 \subset Y$), + что $(C(K), \leq)$ является полной решеткой, которая изоморфна решетке + замкнутых подмножеств множества $G$. + + Алгоритм вычисления системы замыканий на множестве $G$: + \begin{enumerate} + \item + Рассматриваем множество $G \in Z_{f_G}$. + \item + Последовательно перебираем все элементы $m \in M$ и вычисляем для них + $\psi(\{m\}) = \rho^{-1}(m)$. + \item + Вычисляем все новые пересечения множества $\psi(\{m\})$ с ранее + полученными множествами и добавляем новые множества к $Z_{f_G}$. + Аналогично вычисляется система замыканий на множестве $M$. + \end{enumerate} +\end{theorem} + + +\section{Алгоритмы} + +\input{tmp/algo.tex} + + +\section{Программная реализация} + +\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab2.py} + + +\section{Результаты тестирования} + +Результаты тестирования программы. + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{test1.png} + \caption{Эквивалентное замыкание и фактор-множество} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{test2.png} + \caption{Минимальные и максимальные элементы множества} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{test3.png} + \caption{Построение диаграммы Хассе} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{hasse.png} + \caption{Диаграмма Хассе} +\end{figure} + +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{test4.png} + \caption{Система замыканий и решётка концептов} +\end{figure} + +\conclusion + +В ходе выполнения данной лабораторной работы были изучены определения отношения +эквивалентности, фактор-множества, отношения порядка и диаграммы Хассе, +контекста и концепта. Были разработаны алгоритмы построения эквивалентного +замыкания бинарного отношения и системы представителей фактор-множества, +вычисления минимальных (максимальных) и наименьших (наибольших) элементов и +построения диаграммы Хассе, вычисления решетки концептов, а также были +произведена оценка сложности вычисления данных алгоритмов. Программная +реализация на языке Python с библиотекой numpy успешно прошла тестирование. + +\end{document} diff --git a/lab2/report/preamble.sty b/lab2/report/preamble.sty new file mode 100644 index 0000000..5c04d82 --- /dev/null +++ b/lab2/report/preamble.sty @@ -0,0 +1,54 @@ +\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{theorem}{Теорема} +\newtheorem{lemma}{Лемма} +\newtheorem*{lemma*}{Лемма} +\newtheorem{definition}{Определение} +\newtheorem*{example}{Пример}
\ No newline at end of file diff --git a/lab2/report/titlepage.tex b/lab2/report/titlepage.tex new file mode 100644 index 0000000..72a0fd6 --- /dev/null +++ b/lab2/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 diff --git a/lab2/report/tmp/algo.tex b/lab2/report/tmp/algo.tex new file mode 100644 index 0000000..fb8b5d8 --- /dev/null +++ b/lab2/report/tmp/algo.tex @@ -0,0 +1,280 @@ +\subsection{Построение эквивалентного замыкания} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Матрица бинарного отношения $A' = (a'_{ij})$ с построенным на +нем эквивалентным замыканием. + +\begin{enumerate} + \item + Построить рефлексивное замыкание на бинарном отношении с матрицей $A = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A_1 = + (a_{ij})$. + \item + Построить симметричное замыкание на бинарном отношении с матрицей $A_1 = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A_2 = + (a_{ij})$. + \item + Построить транзитивное замыкание на бинарном отношении с матрицей $A_2 = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A' = + (a'_{ij})$. + \item + Согласно пункту 4 леммы 1 о замыканиях бинарных отношений, построенное + замыкание на данном бинарном отношении, определяемым матрицей, является + эквивалентным. Далее вернуть полученную матрицу $A' = (a'_{ij})$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^4)$. + + +\subsection{Построение системы представителей фактор-множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Система представителей $T$ фактор-множества $A/\varepsilon$ +бинарного отношения $\varepsilon$ на множестве $A$. + +\begin{enumerate} + \item + Получить фактор-множество $A/\varepsilon$ бинарного отношения $\varepsilon$ + для множества $A$. Для этого нужно получить классы эквивалентности + $\varepsilon(a)$, которые являются срезами по элементам множества $A$. + Срезом по каждому элементу $a \in A$ является совокупность таких элементов + множества $A$, значения которых в строке матрицы, определяющей связи между + элементом $a$ и другими элементами множества $A$, равны единице. Для этого + проверим элементы $a_{ij}$ матрицы $A$, и если $a_{ij} = 1$, где $0 \leq i, + j \leq n - 1$, то добавить значение $j$ в список, определяющий срез по + элементу $i$. В результате полученная совокупность всех таких срезов, + являющихся классами эквивалентности $\{[a]: a \in A\}$, будет определять + фактор-множество $A/\varepsilon$ бинарного отношения $A$. + \item + Отсортировать фактор-множество по возрастанию количества элементов в классах + эквивалентности. + \item + Проходясь по каждому элементу $a$ каждого класса эквивалентности $[a]$ + проверять: если элемент $a$ класса эквивалентности не находится в системе + представителей - добавить элемент в систему представителей как представителя + класса эквивалентности $[a]$, иначе - пропустить элемент. + \item + Вернуть полученную систему представителей. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление минимального элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Список минимальных элементов $L$ упорядоченного множества $(A, +\leq)$. + +\begin{enumerate} + \item + Определяем пустой список $L$. + \item + Пройти по элементам $a_{ij}$ матрицы $A$ (где $0 \leq i, j \leq n - 1$), и + для каждой строки определять переменную $f$, которая будет изначально равна + \textbf{True}. Если $a_{ji} \neq 0$ и $i \neq j$, то переменная $f$ + становится равной \textbf{False} (это означает, что $i$-ый элемент множества + не является минимальным). Если после прохождения по значениям $i$-ой строки + матрицы значение $f$ осталось равным \textbf{True}, то $i$-ый элемент + множества является минимальным, и его надо добавить в список $L$. + \item + Вернуть список минимальных элементов $L$ упорядоченного множества $(A, + \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление максимального элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times n$. + +\textit{Выход}: Список максимальных элементов $L$ упорядоченного множества $(A, \leq)$. + +\begin{enumerate} + \item + Определяем пустой список $L$. + \item + Пройти по элементам $a_{ij}$ матрицы $A$ (где $0 \leq i, j \leq n - 1$), и + для каждой строки определять переменную $f$, которая будет изначально равна + \textbf{True}. Если $a_{ij} \neq 0$ и $i \neq j$, то переменная $f$ + становится равной \textbf{False} (это означает, что $i$-ый элемент множества + не является максимальным). Если после прохождения по значениям $i$-ой строки + матрицы значение $f$ осталось равным \textbf{True}, то $i$-ый элемент + множества является максимальным, и его надо добавить в список $L$. + \item + Вернуть список максимальных элементов $L$ упорядоченного множества $(A, + \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление наименьшего элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Наименьший элемент $a_{min}$ упорядоченного множества $(A, +\leq)$ или <<Ничего>>. + +\begin{enumerate} + \item + Получить список $L$ минимальных элементов упорядоченного множества $(A, + \leq)$ с помощью алгоритма 3.3. + \item + Руководствуясь \textbf{Леммой 2}, если длина $L$ не равна $1$, вернуть + <<Ничего>>, иначе - вернуть единственный элемент $a_{min} = l \in L$, + являющийся наименьшим элементом множества $A$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление наибольшего элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times n$. + +\textit{Выход}: Наибольший элемент $a_{max}$ упорядоченного множества $(A, \leq)$ или ''Ничего''. + +\begin{enumerate} + \item + Получить список $L$ максимальных элементов упорядоченного множества $(A, + \leq)$ с помощью алгоритма 3.4. + \item + Руководствуясь \textbf{Леммой 2}, если длина $L$ не равна $1$, вернуть + ''Ничего'', иначе - вернуть единственный элемент $a_{max} = l \in L$, + являющийся наибольшим элементом множества $A$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Построение диаграммы Хассе} + +\textit{Вход}: Матрица бинарного отношения порядка $A = (a_{ij})$ размерности $n +\times n$. + +\textit{Выход}: Список $H$ длиной $n$, характеризующий диаграмму Хассе: каждый +элемент в списке представляет собой три значения: элемент $a \in A$, значение +его уровня $l$ на диаграмме, список $V$ элементов множества $A$, находящихся на +уровне $l + 1$ и связанных с элементом $a$. + +\begin{enumerate} + \item + Учитывая, что матрице $A = (a_{ij})$ соответствует множество $\overline{A}$ + определяется список $L$, в котором будут храниться значения уровня $l$ для + каждого элемента $a \in \overline{A}$. Изначально присвоить всем элементам + $l \in L$ уровень $1$. Также определить счетчик уровней $p = 0$ и сдвиг по + элементам множества как $b = 0$. + \item + Получить список $L_{min}$ минимальных элементов множества $\overline{A}$ с + помощью алгоритма 3.3, отправив ему на вход матрицу бинарного отношения + порядка $A = (a_{ij})$ (при этом не учитывая первые $b$ элементов + множества). Увеличить значение $p$ на $1$. + \item + Если список $L_{min}$ пуст, перейти к шагу $5$. Иначе перейти к шагу $4$. + \item + Для каждого элемента $a$ в $L_{min}$ соответствующее ему значение списка $l + \in L$ сделать равным $p$. Прибавить к сдвигу $b$ значение, равное + количеству элементов списка $L_{min}$. После этого перейти к шагу $2$. + \item + Определить пустой список $V$. Проходясь по элементам списка $L$, где $0 \leq + k \leq n - 1$, определять для каждого значения $l_k$ пустой список $v_k$ + связанных с элементом $g_k$ элементов множества $G$. Определяя такой список, + далее брать срез $S$ по атрибутам для конкретного объекта $g_k$ (это + осуществляется следующим образом: необходимо предварительно транспонировать + матрицу $B = A^T = (a_{ij})^T = b_{ij}$, затем проверить элементы $b_{ij}$ + матрицы $B$, и если $b_{ij} = 1$, то добавить значение атрибута $m_j$ в + список, определяющий срез по объекту $g_i$. В результате получить список + срезов $S_G = \{s_i = [g]: g \in G\}$, откуда необходимо взять срез для + объекта $g_k$), и затем пройтись по каждому элементу $s_p$ в этом срезе: + если уровень $l \in L$ очередного элемента в срезе равен $l_p + 1$, то + добавить элемент $s_p$ в список $v_k$. После этого отсортировать список + $v_k$ и добавить его в $V$. + \item + Создать список $H$ и поместить в него в качестве элемента $h_i \in H$ тройку + значений: $a_i \in A$, $l_i \in L$, $v_i \in V$, где $0 \leq i \leq n - 1$. + После этого вернуть список $H$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^3 + n^2) = O(n^3)$. + + +\subsection{Построение системы замыканий} + +\textit{Вход}: Контекст $K = (G, M, \rho)$ с множеством объектов $G$, множеством +атрибутов $M$ и отношением $\rho \subset G \times M$, заданного матрицей $A = +(a_{ij})$ размерности $n \times k$ (где $n$ - количество объектов, $k$ - +количество атрибутов). + +\textit{Выход}: Система замыканий $Z_{f_G}$ на множестве $G$. + +\begin{enumerate} + \item + Определить список $Z_{f_G}$ и положить туда $G$. + \item + Получить срезы по атрибутам $m \in M$ с помощью способа, описанного в + алгоритме 3.2: необходимо предварительно транспонировать матрицу $B = A^T = + (a_{ij})^T = b_{ij}$, затем проверить элементы $b_{ij}$ матрицы $B$, и если + $b_{ij} = 1$, где $0 \leq i \leq k - 1$ и $0 \leq j \leq n - 1$, то добавить + значение объекта $g_j$ в список, определяющий срез по атрибуту $m_i$. В + результате получить список срезов $S_G = \{s_i = [g]: g \in G\}$, размер + которого будет $k$. + \item + Для каждого атрибута $m_i \in M$: определить список $T$, в который поместить + $s_i \in S_G$. Далее для каждого замыкания $z_j$ из системы замыканий + $Z_{f_G}$: получить пересечение множеств $s_i$ и $z_j$ и обозначить его как + $X = s_i \cap z_j$. Если $X$ не содержится в списке $T$: добавить $X$ в + список $T$ (всё это осуществляется при $0 \leq i \leq k - 1$). Если $T + \notin Z_{f_G}$, то положить $T$ в $Z_{f_G}$. + \item + Вернуть систему замыканий $Z_{f_G}$ на множестве $G$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2 + n \cdot k)$. + + +\subsection{Построение решетки концептов} + +\textit{Вход}: Контекст $K = (G, M, \rho)$ с множеством объектов $G$, множеством +атрибутов $M$ и отношением $\rho \subset G \times M$, заданного матрицей $A = +(a_{ij})$ размерности $n \times k$ (где $n$ - количество объектов, $k$ - +количество атрибутов). + +\textit{Выход}: Решетка концептов $(C(K), \leq)$. + +\begin{enumerate} + \item + Построить систему замыканий $Z_{f_G}$ с помощью алгоритма 3.8, отправив ему на + вход контекст $K = (G, M, \rho)$. + \item + Определить пустой список $(C(K), \leq)$. + \item + Построить список $P$ следующим образом: если $z_i = \emptyset$, то $P = M$, + иначе - получить среды по объектам $G$ с помощью способа, описанного в + алгоритме 3.2: проверить элементы $a_{rt}$ матрицы $A$, и если $a_{rt} = 1$, + где $0 \leq t \leq k - 1$ и $0 \leq r \leq n - 1$, то добавить значение + $m_t$ в список, определяющий срез по объекту $g_r$. В результате получить + список срезов $S_M = \{s_i = [m]: m \in M\}$, размер которого будет $n$. + Определить пустой список $Y$. Далее для каждого объекта в замыкании $z_i$: + добавить срез $s_i$, соответствующий конкретному объекту, в список $Y$. + После этого осуществить пересечение всех срезов $s$, находящихся в списке + $Y$, и поместить результат пересечения в список $P$. После построения $P$ + добавить пару значений $z_i$ и $P$ в качестве элемента в список $(C(K), + \leq)$. + \item + Проделать шаг 3 для всех элементов $Z_{f_G}$. После этого вернуть + построенную решетку концептов $(C(K), \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2 + n \cdot k + n^3) = O(n \cdot k + n^3)$.
\ No newline at end of file diff --git a/lab2/test1.txt b/lab2/test1.txt new file mode 100644 index 0000000..2328cf5 --- /dev/null +++ b/lab2/test1.txt @@ -0,0 +1,7 @@ +1 +5 +1 0 1 1 0 +0 1 0 0 1 +1 0 0 1 0 +0 1 0 0 1 +1 1 0 0 0
\ No newline at end of file diff --git a/lab2/test2.txt b/lab2/test2.txt new file mode 100644 index 0000000..a8af121 --- /dev/null +++ b/lab2/test2.txt @@ -0,0 +1,8 @@ +2 +3 4 12 24 48 72 +1 0 1 1 1 1 +0 1 1 1 1 1 +0 0 1 1 1 1 +0 0 0 1 1 1 +0 0 0 0 1 0 +0 0 0 0 0 1
\ No newline at end of file diff --git a/lab2/test3.txt b/lab2/test3.txt new file mode 100644 index 0000000..446f4d9 --- /dev/null +++ b/lab2/test3.txt @@ -0,0 +1,10 @@ +3 +1 2 3 5 6 10 15 30 +1 1 1 1 1 1 1 1 +0 1 0 0 1 1 0 1 +0 0 1 0 1 0 1 1 +0 0 0 1 0 1 1 1 +0 0 0 0 1 0 0 1 +0 0 0 0 0 1 0 1 +0 0 0 0 0 0 1 1 +0 0 0 0 0 0 0 1
\ No newline at end of file diff --git a/lab2/test4.txt b/lab2/test4.txt new file mode 100644 index 0000000..7ad6798 --- /dev/null +++ b/lab2/test4.txt @@ -0,0 +1,7 @@ +4 +1 2 3 4 +a b c d +1 0 1 0 +1 1 0 0 +0 1 0 1 +0 1 0 1
\ No newline at end of file diff --git a/lab3/tests.txt b/lab3/tests.txt new file mode 100644 index 0000000..480603c --- /dev/null +++ b/lab3/tests.txt @@ -0,0 +1,36 @@ +# множество +1, 2, 3, 4, 5 + +# таблица +1 2 3 2 4 +2 3 1 5 3 +3 1 2 2 1 +2 5 2 5 4 +4 2 1 4 3 + +# свойства операции +# не ассоциативность, не коммутативность + +# таблица +1 2 3 2 4 +2 2 1 5 3 +3 1 3 2 1 +2 5 2 4 4 +4 2 1 4 5 + +# свойства операции +# идемпотентность + +# множество +0, 1, 2 + +# таблица +0 0 0 +0 1 2 +0 2 1 + +0 1 2 +1 2 0 +2 0 1 + +# дистрибутивность diff --git a/lab4/test2.txt b/lab4/test2.txt new file mode 100644 index 0000000..f44a5bc --- /dev/null +++ b/lab4/test2.txt @@ -0,0 +1,11 @@ +нет +да +a b c +2 +1 0 1 +0 1 0 +1 0 1 +0 1 0 +1 1 1 +0 0 0 +нет
\ No newline at end of file diff --git a/lab4/test3.txt b/lab4/test3.txt new file mode 100644 index 0000000..b80b8ed --- /dev/null +++ b/lab4/test3.txt @@ -0,0 +1,8 @@ +нет +нет +да +1 2 3 +a b c +2 2 2 +1 3 3 +* 2 3
\ No newline at end of file diff --git a/lab5/test.txt b/lab5/test.txt new file mode 100644 index 0000000..e98b89a --- /dev/null +++ b/lab5/test.txt @@ -0,0 +1,5 @@ +a b +3 +ab ba +bbb b +aa a
\ No newline at end of file |