Что такое строка в математике

Лекция 1_10: Строки. Основные понятия и операции

Строки как тип информации очевидно появились в компьютерных задачах обработки текстов, причем среди таких текстов очень быстро появились компьютерные программы — тексты, написанные на специально созданном алгоритмическом языке. Формальный анализ текстов на таком языке значительно легче, чем на естественном. Но были и такие задачи, где вынужденно использовался естественный язык — его специально упрощали.

По мере того, как накапливались стандартные методы представления строковой информации и операции над ней, выяснялось, что объекты типа строк уже используются или должны использоваться во многих математических моделях.

Особо нужно упомянуть о математической генетике, где строка — одно из самых важных понятий.

В этой лекции мы формально определим, что такое строка, рассмотрим наиболее характерные действия со строками, а затем перечислим некоторые приложения строк.

Что такое строки, и зачем ими заниматься

Психологически удобно иметь в качестве основного примера строку текста, и подготовка к определениям начинается с фразы:

Строки — это произвольные последовательности, составленные из букв, причем любая буква может встречаться в последовательности любое число раз. Например, вот несколько строк над алфавитом строчных русских букв:

аааааааахахахааааа
пришелувиделпобедил
эта строка незаконная

Действительно, последний пример ошибочен. Почему?

Подстроку легко задать, указав ее позицию начальной буквы и длину (для подстроки обед это (14,4), если символы нумеруются от 1, и (13,4) при нумерации от 0).

Символьные строки, в которых алфавитом является множество возможных значений байта с какой-либо фиксированной кодировкой, широко используются в программировании. Посмотрим, как строки представляются в наиболее распространенных языках программирования и что с ними там можно делать.

Строки в языках программирования

В тексте программы переменные строки описываются очень просто:

Строковые константы заключаются в апострофы :

const
sOrg = ‘матмех СПбГУ’;

В исполняемой программе строка хранится в виде байтового массива, причем недоступный программисту начальный, нулевой, байт содержит длину самой строки.

В языке Си строки рассматриваются как последовательности байтов, записанных подряд. Строка заканчивается байтом с нулевым значением, поэтому байты с нулевым значением внутри строки не разрешены. Такой формат принято называть ASCIIZ ( ASCII + Z ero). Размещение строки в памяти оставляется на усмотрение самого програм­миста. В этом языке вычисление длины строки — это именно вычисление. Впрочем, в системе команд процессоров персональных компьютеров уже давно есть команда просмотра памяти до нахождения байта с нужным значением, так что функция, вычисляющая длину строки работает очень быстро.

В языке С++ тип строка уже есть, размещением строки занимается система.

Операции над строками

Перечислим те операции, которые мы уже рассмотрели, и добавим некоторые новые.

Сравнение строк

Наиболее распространено уже неоднократно встречавшееся нам лексикографическое сравнение строк, которое основывается на упорядочении букв алфавита, из которых формируются эти строки. Если сравнивать буквы по кодам ASCII (и так обычно и делается), то эффект может быть не очень приятным для нас. Часто мы можем видеть. что получается в алфавитных указателях современных книг: даже в русскоязычных книгах кириллица следует за латиницей, а перед латиницей расположены всевозможные служебные символы. Например, получится такой порядок «слов» (столбец за столбцом)

exe

Такой порядок, без сомнения, будет для нас неприятен.

А чего же мы хотели бы?

Лучше всего, если бы сначала шла кириллица, причем без разделения прописных и строчных букв, а специальные знаки могут и пропускаться, затем так же латиница, затем числа, затем в каком-нибуль порядке все знаки. Чтобы получилось как-нибудь так

exe

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

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

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

3

0:60

1:61

2:62

3:63

4:64

5:65

6:66

7:67

8:68

9:69

:

;

?

4

@

A:34

B:35

C:36

D:37

E:38

F:39

G:40

H:41

I:42

J:43

K:44

L:45

M:46

N:47

O:48

5

P:49

Q:50

R:51

S:52

T:53

U:54

V:55

W:56

X:57

Y:58

Z:59

[

\

]

^

_

После этого можно в желательном порядке расположить прочие знаки. Построенная таким образом таблица (очень скромного размера — 256 байтов) может использоваться в функции сравнения символов. Надо сравнивать не сами символы, а их ранги. Можно еще выделить особо нулевой ранг, делая символы с нулевым рангом невидимыми для сортировки.

Но конечно, этим усовершенствованием все проблемы не решаются. Например, часто неудобно лексикографическое сравнение строк, в которых содержатся числа. Если в телефонном справочнике строка «Школа 239» предшествует строке «Школа 45», а «аптека 4» стоит за «аптека 141», это может вызвать большие неудобства: человек ищет школы и аптеки по порядку номеров и может просто не найти нужный телефон. Мне, хотя я и знаю этот эффект, часто приходится страдать от него при поиске нужных файлов — как правило, они упорядочиваются лексикографически. Единственный известный мне пример учета чисел в строках — это программа Photoshop.

Задача о максимальной общей подпоследовательности

Сейчас мы рассмотрим одну экстремальную задачу, связанную со строками.

Идея метода состоит в том, что решение нужной нам задачи заменяется решением большого числа однотипных задач, которые решаются вместе, а в таком коллективном решении каждая задача использует результаты решения других задач. Посмотрим, как это выглядит в нашем случае.

Полученное соотношение можно использовать для очень простого вычисления всей таблицы, например, по строчкам, от меньших значений индексов к большим.

Например, при сопоставлении строк
bambambambam
и
maambamaamba
мы построим такую таблицу 12×12.
&nbsp bambambambam
m 001111111111
a 0 1 1122222222
a 011122233333
m 01 2 223334444
b 112 3 33444555
a 1223 4 4455566
m 12334 5 556667
a 1233455 6 6677
a 123345566677
m 12334556 7 778
b 123445667 8 88
a 1234556778 9 9

После того, как построена эта таблица, можно по ней найти и максимальную общую подпоследовательность. Соответствующие ей символы выделены на таблице красным цветом.

Экзаменационные вопросы

Источник

Что такое матрица

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

Определение матрицы

Матрица – это своего рода прямоугольная таблица, которая состоит из строк и столбцов, содержащих определенные элементы.

Применение матриц в математике

Матрицы используются для записи и решения систем линейных алгебраических уравнений или систем дифференциальных уравнений.

Элементы матрицы

Например, для матрицы выше:

Строки

Если все элементы строки матрицы равняются нулю, то такая строка называется нулевой (выделена зеленым).

В противном случае, строка является ненулевой (выделена красным).

Диагонали

Диагональ, проведенная от верхнего левого угла матрицы в нижний правый называется главной.

Если диагональ проведена из нижнего левого угла в верхний правый, она называется побочной.

Историческая справка

“Волшебный квадрат” – под таким названием матрицы впервые упоминались в Древнем Китае, а позднее и у арабских математиков.

В 1751 году швейцарский математик Габриэль Крамер опубликовал “правило Крамера”, используемое для решения систем линейных алгебраических уравнений (СЛАУ). Примерно в это же время появился “метод Гаусса” для решения СЛАУ путем последовательного исключения переменных (автор – Карл Фридрих Гаусс).

Существенный вклад в развитие теории матриц, также, внесли такие математики: Уильям Гамильтон, Артур Кэли, Карл Вейерштрасс, Фердинанд Фробениус и Мари Энмон Камиль Жордан. Сам же термин “матрица” в 1850 году был введен Джеймсом Сильвестром.

Источник

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Строки в математике

Последний раз редактировалось Mr. Dred 28.09.2011, 20:55, всего редактировалось 1 раз.

Заслуженный участник

Заслуженный участник

Заслуженный участник

Последний раз редактировалось Mr. Dred 28.09.2011, 21:16, всего редактировалось 1 раз.

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

где — интервал между -м и -м вхождением -ого символа
— удаленность знаковой цепи

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

Заслуженный участник

Заслуженный участник

Последний раз редактировалось Sonic86 28.09.2011, 21:28, всего редактировалось 3 раз(а).

Заслуженный участник

Последний раз редактировалось Mr. Dred 28.09.2011, 21:44, всего редактировалось 1 раз.

Если поконкретнее, то подход используется для вычисления характеристик строк
Например в биоинформатике и мат. лингвистике как основа для меры растояния между строками

Основная характеристика описана вот в этом сообщении

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

где — интервал между -м и -м вхождением -ого символа
— удаленность знаковой цепи

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

Основной проблемой, как мне кажется является не совсем понятная математическая природа интервалов, если в теории вероятности из смысла вероятности достаточно очевидно вытекают свойства последней и опрерации в вероятностном пространстве, то с интервалами дело обстоит значительно хуже.

Заслуженный участник

Последний раз редактировалось Sonic86 29.09.2011, 06:50, всего редактировалось 1 раз.

Гуглил, но в интернете по свободным магмам информации совсем мало, можете подсказать что-либо из литературы?

Заслуженный участник

Последний раз редактировалось arseniiv 29.09.2011, 21:26, всего редактировалось 1 раз.

Свободные магмы не должны ли быть более общими, чем надо чем свободные полугруппы? На самом деле, конкатенация ассоциативна, так что алгебра строк будет полугруппой. А если туда включена пустая строка, то ещё и моноидом, потому что пустая строка, прибавляй её справа или слева, даст ту же строку, к которой прибавляли. А магма никаких требований к операции своей не просит, так что слишком обща.

Давайте создадим тему, может, кто-то знает? Или хотя бы обсуждать там, какие обозначения были бы хорошими, а какие не очень.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Как легко понять знаки Σ и П с помощью программирования

Для тех, кто подзабыл матешу

Вот говорят, что если ты не закончил Физтех, ФПМ или Бауманку, тебе в программировании делать нечего. Почему так говорят? Потому что, дескать, ты не учил сложную математику, а в программировании без неё никуда.

Это всё чушь, конечно. Если вы плохо знаете математику, вы можете быть блестящим разработчиком. Вы вряд ли напишете драйверы для видеокарты, но вы запросто сделаете мобильное приложение или веб-сервис. А это — основные деньги в этой среде.

Но всё же, чтобы получить некоторое интеллектуальное превосходство, вот вам пара примеров из страшного мира математики. Пусть они покажут вам, что не все закорючки в математике — это ад и ужас. Вот две нестрашные закорючки.

Знак Σ — сумма

Когда математикам нужно сложить несколько чисел подряд, они иногда пишут так:

Σ (читается «сигма») — это знак алгебраической суммы, который означает, что нам нужно сложить все числа от нижнего до верхнего, а перед этим сделать с ними то, что написано после знака Σ.

На картинке выше написано следующее: «посчитать сумму всех чисел от 5 до 15, умноженных на два». То есть:

Давайте для закрепления ещё один пример. На картинке ниже будет сказано «Найди сумму квадратов чисел от 5 до 10». То есть «возьми все числа от 5 до 10, каждое из них возведи в квадрат, а результаты сложи».

Но мы с вами как программисты видим, что здесь есть повторяющиеся действия: мы много раз складываем числа, которые меняются по одному и тому же правилу. А раз мы знаем это правило и знаем, сколько раз надо его применить, то это легко превратить в цикл. Для наглядности мы показали, какие параметры в Σ за что отвечают в цикле:

Произведение П

С произведением в математике работает точно такое же правило, только мы не складываем все элементы, а перемножаем их друг на друга:

А если это перевести в цикл, то алгоритм получится почти такой же, что и в сложении:

Что дальше

Сумма и произведение — простые математические операции, пусть они и обозначаются страшными символами. Впереди нас ждут интегралы, дифференциалы, приращения и бесконечные ряды. С ними тоже всё не так сложно, как кажется на первый взгляд.

Источник

Математика для чайников. Матрицы и основные действия над ними

Определение матрицы

Матрица – это прямоугольная таблица элементов. Ну а если простым языком – таблица чисел.

Обычно матрицы обозначаются прописными латинскими буквами. Например, матрица A, матрица B и так далее. Матрицы могут быть разного размера: прямоугольные, квадратные, также есть матрицы-строки и матрицы-столбцы, называемые векторами. Размер матрицы определяется количеством строк и столбцов. Например, запишем прямоугольную матрицу размера m на n, где m – количество строк, а n – количество столбцов.

Что можно делать с матрицами? Складывать/вычитать, умножать на число, умножать между собой, транспонировать. Теперь обо всех этих основных операциях над матрицами по порядку.

Операции сложения и вычитания матриц

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

Вычитание выполняется по аналогии, только с противоположным знаком.

Умножение матрицы на число

На произвольное число можно умножить любую матрицу. Чтобы сделать это, нужно умножить на это число каждый ее элемент. Например, умножим матрицу A из первого примера на число 5:

Операция умножения матриц

И пример с реальными числами. Умножим матрицы:

Операция транспонирования матрицы

Транспонирование матрицы – это операция, когда соответствующие строки и столбцы меняются местами. Например, транспонируем матрицу A из первого примера:

Определитель матрицы

Определитель, о же детерминант – одно из основных понятий линейной алгебры. Когда-то люди придумали линейные уравнения, а за ними пришлось выдумать и определитель. В итоге, разбираться со всем этим предстоит вам, так что, последний рывок!

Определитель – это численная характеристика квадратной матрицы, которая нужна для решения многих задач.
Чтобы посчитать определитель самой простой квадратной матрицы, нужно вычислить разность произведений элементов главной и побочной диагоналей.

Определитель матрицы первого порядка, то есть состоящей из одного элемента, равен этому элементу.

А если матрица три на три? Тут уже посложнее, но справиться можно.

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

К счастью, вычислять определители матриц больших размеров на практике приходится редко.

Источник