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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

В математике[править | править вики-текст]

Пусть даны множества A_1, A_2, \ldots, A_n, не обязательно различные.

Тогда корте́ж длины n[1][2], упорядоченный набор длины n[1], упорядоченный n-набор[2] или n-ка[1][3] — упорядоченная последовательность из n элементов x_1, x_2, \ldots, x_n, где x_i\in A_i для 1 \leqslant i \leqslant n. Кортеж обозначается перечислением координат в угловых или круглых скобках[1]:

\langle x_1, x_2, \ldots, x_n\rangle

или

(x_1, x_2, \ldots, x_n).

Элемент x_i называется iкоординатой[1][4] (проекцией[2], компонентой[2][4]) кортежа \langle x_1, x_2, \ldots, x_n\rangle.

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

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

\langle a_1,\ldots,a_n\rangle = \langle b_1,\ldots,b_n\rangle, если a_i=b_i, i=\overline{1,n}.

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

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

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, … также носят названия «упорядоченная пара», «упорядоченная тройка», «упорядоченная четвёрка», «упорядоченная пятёрка» и т. д.[2]

Определения в теории множеств[править | править вики-текст]

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

  • \langle\rangle\rightleftharpoons\emptyset,
  • \langle x_1\rangle\rightleftharpoons x_1,
  • \langle x_1,x_2\rangle\rightleftharpoons \{\{x_1\},\{x_1,x_2\}\},
  • \langle x_1,x_2,x_3\rangle\rightleftharpoons \langle\langle x_1,x_2\rangle,x_3\rangle,
  • \langle x_1,x_2,x_3,x_4\rangle\rightleftharpoons \langle\langle x_1,x_2,x_3\rangle,x_4\rangle, \ldots
  • \langle x_1,\ldots,x_n\rangle\rightleftharpoons \langle\langle x_1,\ldots,x_{n-1}\rangle,x_n\rangle.

Определение других объектов через кортежи[править | править вики-текст]

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

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

В программировании[править | править вики-текст]

В некоторых языках программирования, например, Python или ML, кортеж — особый тип данных. В языке Python кортеж (англ. tuple) отличается от списка тем, что элементы кортежа нельзя изменять.

a = (1, 2, 3, 2)
print a[1]
a[1] = 5 #Ошибка

Эта программа на Python 2.7, использующая кортеж a, выведет ошибку в 3-й строке: TypeError: 'tuple' object does not support item assignment.

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

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

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

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

В базах данных[править | править вики-текст]

В реляционных базах данных кортеж — это элемент отношения. Для 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.

Ссылки[править | править вики-текст]