Кортеж (информатика)

Кортеж — упорядоченный набор фиксированной длины.

В математикеПравить

Пусть даны множества $A_1,A_2,\dots <!--\; \dots \; -->,A_n$$A_{1},A_{2},\ldots ,A_{n}$ , не обязательно различные.

Тогда корте́ж длины n, упорядоченный набор длины n, упорядоченный n-набор или n-ка — упорядоченная последовательность из n элементов $x_1,x_2,\dots <!--\; \dots \; -->,x_n,$$x_{1},x_{2},\ldots ,x_{n},$  где $x_i\in <!--\; \in \; -->A_i$$x_{i}\in A_{i}$  для $1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->n.$$1\leqslant i\leqslant n.$  Кортеж обозначается перечислением координат в угловых или круглых скобках:

$⟨<!--\; ⟨\; -->x_1,x_2,\dots <!--\; \dots \; -->,x_n⟩<!--\; ⟩\; -->$$\langle x_{1},x_{2},\ldots ,x_{n}\rangle$ 

или

$(x_1,x_2,\dots <!--\; \dots \; -->,x_n).$$(x_{1},x_{2},\ldots ,x_{n}).$ 

Элемент $x_i$$x_{i}$  называется i-й координатой (проекцией, компонентой) кортежа $⟨<!--\; ⟨\; -->x_1,x_2,\dots <!--\; \dots \; -->,x_n⟩<!--\; ⟩\; -->.$$\langle x_{1},x_{2},\ldots ,x_{n}\rangle .$ 

Число n называют длиной или размерностью кортежа.

Два кортежа равны, если равны их длины и соответствующие элементы:

$⟨<!--\; ⟨\; -->a_1,\dots <!--\; \dots \; -->,a_n⟩<!--\; ⟩\; -->=⟨<!--\; ⟨\; -->b_1,\dots <!--\; \dots \; -->,b_n⟩<!--\; ⟩\; -->,$$\langle a_{1},\ldots ,a_{n}\rangle =\langle b_{1},\ldots ,b_{n}\rangle ,$  если $a_i=b_i,i=\stackrel{¯<!--\; ¯\; -->}{1,n}.$$a_{i}=b_{i},i={\overline {1,n}}.$ 

Пример кортежа — арифметический вектор.

Декартово произведение n множеств — множество всех кортежей длины n, координаты которых взяты из этих множеств:

$A_1\times <!--\; \times \; -->\dots <!--\; \dots \; -->\times <!--\; \times \; -->A_n=\{⟨<!--\; ⟨\; -->x_1,\dots <!--\; \dots \; -->,x_n⟩<!--\; ⟩\; -->\mid <!--\; \mid \; -->x_i\in <!--\; \in \; -->A_i,i=\stackrel{¯<!--\; ¯\; -->}{1,n}\}.$$A_{1}\times \ldots \times A_{n}=\{\langle x_{1},\ldots ,x_{n}\rangle \mid x_{i}\in A_{i},i={\overline {1,n}}\}.$ 

Кортежи длины 2, 3, 4, 5, … также носят названия «упорядоченная пара», «упорядоченная тройка», «упорядоченная четвёрка», «упорядоченная пятёрка» и т. д.

Определения в теории множествПравить

В рамках теории множеств кортежи можно индуктивно поставить в соответствие множествам, например, следующим образом:

• $⟨<!--\; ⟨\; -->⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->\mathrm{\varnothing <!--\; \varnothing \; -->},$$\langle \rangle \rightleftharpoons \emptyset ,$ 
• $⟨<!--\; ⟨\; -->x_1⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->x_1,$$\langle x_{1}\rangle \rightleftharpoons x_{1},$ 
• $⟨<!--\; ⟨\; -->x_1,x_2⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->\{\{x_1\},\{x_1,x_2\}\},$$\langle x_{1},x_{2}\rangle \rightleftharpoons \{\{x_{1}\},\{x_{1},x_{2}\}\},$ 
• $⟨<!--\; ⟨\; -->x_1,x_2,x_3⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->⟨<!--\; ⟨\; -->⟨<!--\; ⟨\; -->x_1,x_2⟩<!--\; ⟩\; -->,x_3⟩<!--\; ⟩\; -->,$$\langle x_{1},x_{2},x_{3}\rangle \rightleftharpoons \langle \langle x_{1},x_{2}\rangle ,x_{3}\rangle ,$ 
• $⟨<!--\; ⟨\; -->x_1,x_2,x_3,x_4⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->⟨<!--\; ⟨\; -->⟨<!--\; ⟨\; -->x_1,x_2,x_3⟩<!--\; ⟩\; -->,x_4⟩<!--\; ⟩\; -->,\dots <!--\; \dots \; -->$$\langle x_{1},x_{2},x_{3},x_{4}\rangle \rightleftharpoons \langle \langle x_{1},x_{2},x_{3}\rangle ,x_{4}\rangle ,\ldots$ 
• $⟨<!--\; ⟨\; -->x_1,\dots <!--\; \dots \; -->,x_n⟩<!--\; ⟩\; -->\rightleftharpoons <!--\; \rightleftharpoons \; -->⟨<!--\; ⟨\; -->⟨<!--\; ⟨\; -->x_1,\dots <!--\; \dots \; -->,x_{n-<!--\; -\; -->1}⟩<!--\; ⟩\; -->,x_n⟩<!--\; ⟩\; -->.$$\langle x_{1},\ldots ,x_{n}\rangle \rightleftharpoons \langle \langle x_{1},\ldots ,x_{n-1}\rangle ,x_{n}\rangle .$ 

Определение других объектов через кортежиПравить

Многие математические объекты формально определяются как кортежи. Например, ориентированный граф определяется как пара $⟨<!--\; ⟨\; -->V,E⟩<!--\; ⟩\; -->,$$\langle V,E\rangle ,$  где V — это множество вершин, а E — подмножество пар в $V\times <!--\; \times \; -->V,$$V\times V,$  соответствующих дугам графа. Точка в n-мерном пространстве действительных чисел определяется как кортеж длины n, составленный из элементов множества действительных чисел.

Ориентированный мультиграф со множеством вершин V, множеством дуг E и отношением инцидентности $P\subseteq <!--\; \subseteq \; -->V\times <!--\; \times \; -->E\times <!--\; \times \; -->V$$P\subseteq V\times E\times V$  может быть определён как упорядоченная тройка $⟨<!--\; ⟨\; -->V,E,P⟩<!--\; ⟩\; -->,$$\langle V,E,P\rangle ,$  причём $⟨<!--\; ⟨\; -->a,e,b⟩<!--\; ⟩\; -->\in <!--\; \in \; -->P$$\langle a,e,b\rangle \in P$  тогда и только тогда, когда дуга e выходит из вершины a и заходит в вершину b.

В программированииПравить

См. также: Тип-произведение

В некоторых языках программирования, например, Python или ML, кортеж как тип данных встроен в язык. Пример использования кортежа в языке Python:

a = (1, 3.14, 'cat')
print(a[0]) # Напечатать первый элемент кортежа

В языках программирования со статической типизацией кортеж отличается от списка тем, что элементы кортежа могут принадлежать разным типам и набор таких типов заранее определён типом кортежа, а значит, и размер кортежа также определён. С другой стороны, коллекции (списки, массивы) имеют ограничение по типу хранимых элементов, но не имеют ограничения на длину. Так, например, в языке Rust функция может вернуть несколько значений с помощью упаковки в кортеж:

fn div_with_remainder(a: i32, b: i32) -> (i32, i32, String) {
    let tmp = (a/b, a%b);
    (tmp.0, tmp.1, format!("{} + {}", tmp.0, tmp.1))
}

let (res, rem, repr) = div_with_remainder(5,2);

В функциональных языках некаррированные функции нескольких аргументов принимают параметры в виде одного аргумента, являющегося кортежем.

В языке C++ поддержка кортежей реализована как шаблон класса std::tuple (начиная с C++11) и в библиотеке Boost Tuple Library.

Кортеж является стандартным типом в платформе .NET начиная с версии 4.0.

В базах данныхПравить

В реляционных базах данных кортеж — это элемент отношения. Для N-арного отношения кортеж представляет собой упорядоченный набор из N значений, по одному значению для каждого атрибута отношения, то есть запись (строку) таблицы, если использовать наиболее популярное представление (графическую/физическую интерпретацию) отношения как таблицы.

ЛитератураПравить

• Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. — М.: ИНФРА-М, Новосибирск: Издательство НГТУ, 2002. — 280 с. — (Серия «Высшее образование»). ISBN 5-16-000957-4 (ИНФРА-М), ISBN 5-7782-0332-2 (НГТУ)
• Белоусов А. И., Ткачев С. Б. Дискретная математика: Учебник для вузов / Под редакцией В. С. Зарубина, А. П. Крищенко. — 3-е издание, стереотипное. — М.: Издательство МГТУ им. Н. Э. Баумана, 2004. — 744 с. — ISBN 5-7038-1769-2.
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е издание. — М.: Издательский дом «Вильямс», 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Н. Я. Виленкин. Популярная комбинаторика. — М.: Наука, 1975.
• Англо-русский словарь математических терминов / Под ред. П. С. Александрова. — 2-е, исправл. и дополн. изд.. — М.: Мир, 1994. — 416 с. — ISBN 5-03-002952-4.
• Karel Hrbacek, Thomas Jech. Introduction to Set Theory. — Third edition, revised and expanded. — 1999. — ISBN 0-8247-7915-0.

СсылкиПравить

• В глубь языка Python: 1.9. Кортежи