Что значит сетка в математике
Как легко понять знаки Σ и П с помощью программирования
Для тех, кто подзабыл матешу
Вот говорят, что если ты не закончил Физтех, ФПМ или Бауманку, тебе в программировании делать нечего. Почему так говорят? Потому что, дескать, ты не учил сложную математику, а в программировании без неё никуда.
Это всё чушь, конечно. Если вы плохо знаете математику, вы можете быть блестящим разработчиком. Вы вряд ли напишете драйверы для видеокарты, но вы запросто сделаете мобильное приложение или веб-сервис. А это — основные деньги в этой среде.
Но всё же, чтобы получить некоторое интеллектуальное превосходство, вот вам пара примеров из страшного мира математики. Пусть они покажут вам, что не все закорючки в математике — это ад и ужас. Вот две нестрашные закорючки.
Знак Σ — сумма
Когда математикам нужно сложить несколько чисел подряд, они иногда пишут так:
Σ (читается «сигма») — это знак алгебраической суммы, который означает, что нам нужно сложить все числа от нижнего до верхнего, а перед этим сделать с ними то, что написано после знака Σ.
На картинке выше написано следующее: «посчитать сумму всех чисел от 5 до 15, умноженных на два». То есть:
Давайте для закрепления ещё один пример. На картинке ниже будет сказано «Найди сумму квадратов чисел от 5 до 10». То есть «возьми все числа от 5 до 10, каждое из них возведи в квадрат, а результаты сложи».
Но мы с вами как программисты видим, что здесь есть повторяющиеся действия: мы много раз складываем числа, которые меняются по одному и тому же правилу. А раз мы знаем это правило и знаем, сколько раз надо его применить, то это легко превратить в цикл. Для наглядности мы показали, какие параметры в Σ за что отвечают в цикле:
Произведение П
С произведением в математике работает точно такое же правило, только мы не складываем все элементы, а перемножаем их друг на друга:
А если это перевести в цикл, то алгоритм получится почти такой же, что и в сложении:
Что дальше
Сумма и произведение — простые математические операции, пусть они и обозначаются страшными символами. Впереди нас ждут интегралы, дифференциалы, приращения и бесконечные ряды. С ними тоже всё не так сложно, как кажется на первый взгляд.
Значение слова «сетка»
1. То же, что сеть (в 1 знач.); небольшая сеть. Если с вечера рыба идет в сетку, значит утром будет улов. Никандров, Седой Каспий.
2. Приспособление различного назначения из перекрещивающихся нитей, веревок, проволоки и т. п. Пружинная сетка кровати. Волейбольная сетка. □ Однажды во время представления она сорвалась с воздушного турника и, пролетев мимо сетки, упала на песок манежа. Куприн, Allez! Никогда он не пользовался сеткой, чтобы защитить свое лицо от пчел. М. Пришвин, Заполярный мед. Вратарь бросается в воздух, но даже этот искусный бросок не спасает положения. Мяч в сетке. Кетлинская, Дни нашей жизни.
3. Разг. Сумка для ношения продуктов, мелких вещей, сплетенная из веревок, шнурков и т. п. Филипыч нес в сетке сапоги, а я плелся сзади со старым мешком на плече. И. А. Козлов, В крымском подполье.
4. Разг. Рубашка из ткани редкого плетения, редкой вязки. Погода здесь изменилась, стало очень жарко, так что пришлось фуфайку заменить сеткой. Чехов, Письмо М. П. Чеховой, 26 июня 1904.
5. перен.; чего. То же, что сеть (в 3 знач.). Месяц смотрит сквозь сетку ветвей. И. Никитин, В темной чаще замолк соловей. На скулах — тонкая сетка багровых жилок. М. Горький, Жизнь Клима Самгина. Сквозь сетку дождя видны плоские, точно подрезанные сверху горы. Соколов-Микитов, У Новой Земли.
6. Спец. Расписание, шкала, схема. — Завтра представишь мне списки завербованных с разбивкой по специальностям и по тарифной сетке. Крымов, Инженер.
7. Анат. Второй отдел желудка жвачных животных.
Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека
Сетка (в топологии) — однородная ячеистая система.
Сетка (численные методы) — дискретное множество точек, на котором задаётся разностная задача при численном моделировании некоторой исходной непрерывной задачи.
Сетка — деревня, Венёвский район, Тульская область, Россия
Сетка — созвездие Южного полушария.
Сетка — второй отдел сложного желудка жвачных животных.
Сетка — часть электронной лампы
Сетка (спортивная) — разделяет игроков разных команд (при некоторых играх в мяч), см. волейбол, футбольные ворота и пр.
Сетка (шаблон) — так называют графическую заготовку, ячейки которой заполняются позже, например: сетка программ теле- или радиовещания.
Сетка (ткань) — материал, применяемый в производстве одежды.
Сетка-авоська — вид хозяйственной сумки.
мяча в различных играх (спорт.).
Мяч полетел в сетку. Играть у сетки (в теннисе — играть, стараясь перехватить мяч около самой сетки, через к-рую он летит). 3. То же, что растр (тип.). Клише сеткой. 4. Решетчатый электрод электронной лампы (радио). 5. Разлиновка клетками. Географическая с. (линии, обозначающие долготы и широты в их взаимном пересечении). 6. Разграфленный лист с размеченными и заполненными для какой-н. надобности делениями. || Расписание, шкала, схема (спец.). Тарифная с.
Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека
се́тка
2. приспособление в виде сетчатого плетения на раме
3. перекрёстное переплетение нитей, веревок и т. п.
4. плетёная сумка ◆ Парни не спеша приближались, неся вдвоем сетку, в которой что-то подозрительно позвякивало.
5. разг. рубашка из ткани редкого плетения, редкой вязки
6. спец. расписание, шкала, схема
7. система из определённым образом перекрещивающихся линий, служащих ориентирами
8. техн. управляющий электрод в радиолампе ◆ Таким образом, подавая различное напряжение на сетку, можно управлять силой анодного тока лампы.
Фразеологизмы и устойчивые сочетания
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я обязательно научусь отличать широко распространённые слова от узкоспециальных.
Насколько понятно значение слова гукнуть (глагол), гукнул:
Разряды и классы чисел
Числа и цифры
Числа — это единицы счета. С помощью чисел можно сосчитать количество предметов и определить различные величины.
Для записи чисел используются специальные знаки — цифры. Всего их десять: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0.
Натуральные числа — это числа, которые мы используем при счете. Вот они: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
От количества цифр в числе зависит его название.
Число, которое состоит из одного знака, называется однозначным. Наименьшее однозначное — 1, наибольшее — 9.
Число, которое состоит из двух знаков цифр, называется двузначным. Наименьшее двузначное — 10, наибольшее — 99.
Числа, которые записаны с помощью двух, трех, четырех и более цифр, называются двузначными, трехзначными, четырехзначными или многозначными. Наименьшее трехзначное — 100, наибольшее — 999.
Каждая цифра в записи многозначного числа занимает определенное место — позицию.
Классы чисел
Цифры в записи многозначных чисел разбивают справа налево на группы по три цифры в каждой. Эти группы называют классами. В каждом классе цифры справа налево обозначают единицы, десятки и сотни этого класса.
Названия классов многозначных чисел справа налево:
Чтобы читать запись многозначного числа было удобно, между классами оставляют небольшой пробел. Например, чтобы прочитать число 125911723296, удобно сначала выделить в нем классы:
А теперь прочитаем число единиц каждого класса слева направо:
Разряды чисел
От позиции, на которой стоит цифра в записи числа, зависит ее значение. Например:
Можно сформулировать иначе и сказать, что в заданном числе 1 123 цифра 3 располагается в разряде единиц, 2 в разряде десятков, 1 в разряде сотен, а 1 служит значением разряда тысяч.
Проясним, что такое разряд в математике. Разряд — это позиция или место расположения цифры в записи натурального числа.
У каждого разряда есть свое название. Слева всегда живут старшие разряды, а справа — младшие. Чтобы быстрее запомнить, можно использовать таблицу.
Количество разрядов всегда соответствует количеству знаков в числе. В этой таблице есть названия всех разрядов для числа, которое состоит из 15 знаков. У следующих разрядов также есть названия, но они используются крайне редко.
Низший (младший) разряд многозначного натурального числа — разряд единиц.
Высший (старший) разряд многозначного натурального числа — разряд, соответствующий крайней левой цифре в заданном числе.
Разрядные единицы обозначают так:
Каждые три разряда, следующие друг за другом, составляют класс. Первые три разряда: единицы десятки и сотни — образуют класс единиц (первый класс). Следующие три разряда: единицы тысяч, десятки тысяч и сотни тысяч — образуют класс тысяч (второй класс). Третий класс будут составлять единицы, десятки и тысячи миллионов и так далее.
Чтобы легче понимать математику — записывайтесь на наши курсы по математике!
Потренируемся
Пример 1. Записать цифрами число, в котором содержится:
Все разрядные единицы, кроме простых единиц, называют составными единицами. Каждые десять единиц любого разряда составляют одну единицу следующего более высокого разряда:
Чтобы узнать, сколько в числе заключается всех единиц какого-либо разряда, нужно отбросить все цифры, обозначающие единицы низших разрядов и прочитать число, которое выражено оставшимися цифрами.
Пример 2. Сколько сотен содержится в числе 6284?
В числе 6284 на третьем месте в классе единиц стоит цифра 2, значит, в числе есть две сотни.
Следующая цифра слева — 6, означает тысячи. Так как в каждой тысяче содержится 10 сотен то, в 6 тысячах их заключается 60.
Значит, в данном числе содержится 62 сотни.
Цифра 0 в любом разряде означает отсутствие единиц в данном разряде.
Проще говоря, цифра 0 в разряде десятков означает отсутствие десятков, в разряде сотен — отсутствие сотен и т. д. В том разряде, где стоит 0, при чтении числа ничего не произносится:
Чтобы проще освоить эту тему, можно распечатать таблицу классов и разрядов для учащихся 4 класса и обращаться к ней, если возникнут сложности.
Что нужно знать про арифметику с плавающей запятой
В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).
Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.
1. Основы
Множество целых чисел бесконечно, но мы всегда можем подобрать такое число бит, чтобы представить любое целое число, возникающее при решении конкретной задачи. Множество действительных чисел не только бесконечно, но еще и непрерывно, поэтому, сколько бы мы не взяли бит, мы неизбежно столкнемся с числами, которые не имеют точного представления. Числа с плавающей запятой — один из возможных способов предсталения действительных чисел, который является компромиссом между точностью и диапазоном принимаемых значений.
Число с плавающей запятой состоит из набора отдельных разрядов, условно разделенных на знак, экспоненту порядок и мантиссу. Порядок и мантисса — целые числа, которые вместе со знаком дают представление числа с плавающей запятой в следующем виде:
Математически это записывается так:
Основание определяет систему счисления разрядов. Математически доказано, что числа с плавающей запятой с базой B=2 (двоичное представление) наиболее устойчивы к ошибкам округления, поэтому на практике встречаются только базы 2 и, реже, 10. Для дальнейшего изложения будем всегда полагать B=2, и формула числа с плавающей запятой будет иметь вид:
Что такое мантисса и порядок? Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа. Допустим наша мантисса состоит из трех бит (|M|=3). Возьмем, например, число «5», которое в двоичной системе будет равно 1012. Старший бит соответствует 2 2 =4, средний (который у нас равен нулю) 2 1 =2, а младший 2 0 =1. Порядок – это степень базы (двойки) старшего разряда. В нашем случае E=2. Такие числа удобно записывать в так называемом «научном» стандартном виде, например «1.01e+2». Сразу видно, что мантисса состоит из трех знаков, а порядок равен двум.
Допустим мы хотим получить дробное число, используя те же 3 бита мантиссы. Мы можем это сделать, если возьмем, скажем, E=1. Тогда наше число будет равно
2 = 10 (в двоичной системе) = 1.000e+1 = 0.100e+2 = 0.010e+3. (E=1, E=2, E=3 соответственно)
Обратите внимание, что одно и то же число имеет несколько представлений. Это не удобно для оборудования, т.к. нужно учитывать множественность представлния при сравнении чисел и при выполнении над ними арифметических операций. Кроме того, это не экономично, поскольку число представлений — конечное, а повторения уменьшают множество чисел, которые вообще могут быть представлены. Поэтому уже в самых первых машинах начали использовать трюк, делая первый бит мантиссы всегда положительным. Такое предаставление назвали нормализованным.
Это экономит один бит, так как неявную единицу не нужно хранить в памяти, и обеспечивает уникальность представления числа. В нашем примере «2» имеет единственное нормализованное представление («1.000e+1»), а мантисса хранится в памяти как «000», т.к. старшая единица подразумевается неявно. Но в нормализованном представлении чисел возникает новая проблема — в такой форме невозможно представить ноль.
Строго говоря, нормализованное число имеет следующий вид:
Качество решения задач во многом зависит от выбора представления чисел с плавающей запятой. Мы плавно подошли к проблеме стандартизации такого представления.
2. Немного истории
В 60-е и 70-е годы не было единого стандарта представления чисел с плавающей запятой, способов округления, арифметических операций. В результате программы были крайне не портабельны. Но еще большей проблемой было то, что у разных компьютеров были свои «странности» и их нужно было знать и учитывать в программе. Например, разница двух не равных чисел возвращала ноль. В результате выражения «X=Y» и «X-Y=0» вступали в противоречие. Умельцы обходили эту проблему очень хитрыми трюками, например, делали присваивание «X=(X-X)+X» перед операциями умножения и деления, чтобы избежать проблем.
Инициатива создать единый стандарт для представления чисел с плавающей запятой подозрительно совпала с попытками в 1976 году компанией Intel разработать «лучшую» арифметику для новых сопроцессоров к 8086 и i432. За разработку взялись ученые киты в этой области, проф. Джон Палмер и Уильям Кэхэн. Последний в своем интервью высказал мнение, что серьезность, с которой Intel разрабатывала свою арифметику, заставила другие компании объединиться и начать процесс стандартизации.
Все были настроены серьезно, ведь очень выгодно продвинуть свою архитектуру и сделать ее стандартной. Свои предложения представили компании DEC, National Superconductor, Zilog, Motorola. Производители мейнфреймов Cray и IBM наблюдали со стороны. Компания Intel, разумеется, тоже представила свою новую арифметику. Авторами предложенной спецификации стали Уильям Кэхэн, Джероми Кунен и Гарольд Стоун и их предложение сразу прозвали «K-C-S».
Практически сразу же были отброшены все предложения, кроме двух: VAX от DEC и «K-C-S» от Intel. Спецификация VAX была значительно проще, уже была реализована в компьютерах PDP-11, и было понятно, как на ней получить максимальную производительность. С другой стороны в «K-C-S» содержалось много полезной функциональности, такой как «специальные» и «денормализованные» числа (подробности ниже).
В «K-C-S» все арифметические алгоритмы заданы строго и требуется, чтобы в реализации результат с ними совпадал. Это позволяет выводить строгие выкладки в рамках этой спецификации. Если раньше математик решал задачу численными методами и доказывал свойства решения, не было никакой гарантии, что эти свойства сохранятся в программе. Строгость арифметики «K-C-S» сделала возможным доказательство теорем, опираясь на арифметику с плавающей запятой.
Компания DEC сделала все, чтобы ее спецификацию сделали стандартом. Она даже заручилась поддержкой некоторых авторитетных ученых в том, что арифметика «K-C-S» в принципе не может достигнуть такой же производительности, как у DEC. Ирония в том, что Intel знала, как сделать свою спецификацию такой же производительной, но эти хитрости были коммерческой тайной. Если бы Intel не уступила и не открыла часть секретов, она бы не смогла сдержать натиск DEC.
Подробнее о баталиях при стандартизации смотрите в интервью профессора Кэхэна, а мы рассмотрим, как выглядит представление чисел с плавающей запятой сейчас.
3. Представление чисел с плавающей запятой сегодня
Разработчики «K-C-S» победили и теперь их детище воплотилось в стандарт IEEE754. Числа с плавающей запятой в нем представлены в виде знака (s), мантиссы (M) и порядка (E) следующим образом:
Замечание. В новом стандарте IEE754-2008 кроме чисел с основанием 2 присутствуют числа с основанием 10, так называемые десятичные (decimal) числа с плавающей запятой.
Чтобы не загромождать читателя чрезмерной информацией, которую можно найти в Википедии, рассмотрим только один тип данных, с одинарной точностью (float). Числа с половинной, двойной и расширенной точностью обладают теми же особенностями, но имеют другой диапазон порядка и мантиссы. В числах одинарной точности (float/single) порядок состоит из 8 бит, а мантисса – из 23. Эффективный порядок определяется как E-127. Например, число 0,15625 будет записано в памяти как
Рисунок взят из Википедии
3.1 Специальные числа: ноль, бесконечность и неопределенность
Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=Emax+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.
Вернемся к примеру. Наш Emin=-1. Введем новое значение порядка, E=-2, при котором числа являются денормализованными. В результате получаем новое представление чисел:
Интервал от 0 до 0,5 заполняют денормализованные числа, что дает возможность не проваливаться в 0 рассмотренных выше примерах (0,5-0,25 и 1,5-1,25). Это сделало представление более устойчиво к ошибкам округления для чисел, близких к нулю.
Но роскошь использования денормализованного представления чисел в процессоре не дается бесплатно. Из-за того, что такие числа нужно обрабатывать по-другому во всех арифметических операциях, трудно сделать работу в такой арифметике эффективной. Это накладывает дополнительные сложности при реализации АЛУ в процессоре. И хоть денормализованные числа очень полезны, они не являются панацеей и за округлением до нуля все равно нужно следить. Поэтому эта функциональность стала камнем преткновения при разработке стандарта и встретила самое сильное сопротивление.
3.4 Очередность чисел в IEEE754
Одна из удивительных особенностей представления чисел в формате IEEE754 состоит в том, что порядок и мантисса расположены друг за другом таким образом, что вместе образуют последовательность целых чисел
4.2 Неассоциативность арифметических операций
В арифметике с плавающей запятой правило (a*b)*c = a*(b*c) не выполняется для любых арифметических операций. Например,
Допустим у нас есть программа суммирования чисел.
Некоторые компиляторы по умолчанию могут переписать код для использования нескольких АЛУ одновременно (будем считать, что n делится на 2):
Так как операции суммирования не ассоциативны, эти две программы могут выдать различный результат.
4.3 Числовые константы
Помните, что не все десятичные числа имеют двоичное представление с плавающей запятой. Например, число «0,2» будет представлено как «0,200000003» в одинарной точности. Соответственно, «0,2 + 0,2 ≈ 0,4». Абсолютная погрешность в отдельном
случае может и не высока, но если использовать такую константу в цикле, можем получить накопленную погрешность.
4.4 Выбор минимума из двух значений
4.5 Сравнение чисел
Очень распространенная ошибка при работе с float-ами возникает при проверке на равенство. Например,
Ошибка здесь, во-первых, в том, что 0,2 не имеет точного двоичного представления, а во-вторых 0,2 – это константа двойной точности, а переменная fValue – одинарной, и никакой гарантии о поведении этого сравнения нет.
Лучший, но все равно ошибочный способ, это сравнивать разницу с допустимой абсолютной погрешностью:
Недостаток такого подхода в том, что погрешность представления числа увеличивается с ростом самого этого числа. Так, если программа ожидает «10000», то приведенное равенство не будет выполняться для ближайшего соседнего числа (10000,000977). Это особенно актуально, если в программе имеется преобразование из одинарной точности в двойную.
Выбрать правильную процедуру сравнения сложно и заинтересованных читателей я отсылаю к статье Брюса Доусона. В ней предлагается сравнивать числа с плавающей запятой преобразованием к целочисленной переменной. Это — лучший, хотя и не портабельный способ:
5. Проверка полноты поддержки IEE754
Думаете, что если процессоры полностью соответствуют стандарту IEEE754, то любая программа, использующая стандартные типы данных (такие как float/double в Си), будет выдавать один и тот же результат на разных компьютерах? Ошибаетесь. На портабельность и соответствие стандарту влияет компилятор и опции оптимизации. Уильям Кэхэн написал программу на Си (есть версия и для Фортрана), которая позволяет проверить удовлетворяет ли связка «архитектура+компилятор+опции» IEEE754. Называется она «Floating point paranoia» и ее исходные тексты доступны для скачивания. Аналогичная программа доступна для GPU. Так, например, компилятор Intel (icc) по умолчанию использует «расслабленную» модель IEEE754, и в результате не все тесты выполняются. Опция «-fp-model precise» позволяет компилировать программу с точным соответствием стандарту. В компиляторе GCC есть опция «-ffast-math», использование которой приводит к несоответствию IEEE754.
Заключение
Напоследок поучительная история. Когда я работал над тестовым проектом на GPU, у меня была последовательная и параллельная версия одной программы. Сравнив время выполнения, я был очень обрадован, так как получил ускорение в 300 раз. Но позже оказалось, что вычисления на GPU «разваливались» и обращались в NaN, а работа с ними в GPU была быстрее, чем с обычными числами. Интересно было другое — одна и та же программа на эмуляторе GPU (на CPU) выдавала корректный результат, а на самом GPU – нет. Позже оказалось, что проблема была в том, что этот GPU не поддерживал полностью стандарт IEEE754 и прямой подход не сработал.
Сейчас арифметика с плавающей запятой почти совершенна. Практически всегда наивный подход сработает, и программа, не учитывающая все ее особенности, выдаст правильный результат, а описанные подводные камни касаются только экзотических случаев. Но нужно всегда оставаться бдительным: в таком вопросе как компьютерная математика легко наступить на грабли.