Сборник материалов Иркутск, 19 апреля 2007 г. Иркутск 2007 г



жүктеу 385.4 Kb.
бет1/3
Дата17.06.2016
өлшемі385.4 Kb.
  1   2   3


Институт систем энергетики

им. Л.А. Мелентьева СО РАН


Компьютерная школа «Алиса»

XXII КОНФЕРЕНЦИЯ ПРОГРАММИСТОВ

Сборник материалов

Иркутск, 19 апреля 2007 г.

Иркутск - 2007 г.

УДК 681.142.2



Сборник материалов XXII конференции программистов. – Иркутск: ИСЭМ СО РАН, 2007. – 36 с.

ISBN 978-5-93908-065-1.



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

Главный редактор: Сташуль Т.В.

Редакторы: Мокрый И.В., Орехов А.Б., Розинов С.В., Трипутина В.В.




© Институт систем энергетики им. Л.А. Мелентьева СО РАН

ISBN 978-5-93908-065-1

Содержание
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Секция школьников
Хамисов О. Машина Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Боровский В. Арифметика в остаточных классах . . . . . . . . . . . . . . . . . . . . . . . 10

Кочетков И. О теории Мартина Гарднера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

Горнов А. Исследование качества алгоритмов поиска корня нелинейного

уравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Банщиков С. Автономный робот . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26


Секция студентов
Дудкин Б., Дудкин И. Бензиновая тепловая пушка . . . . . . . . . . . . . . . . . . . . . . 34

Предисловие
В настоящий сборник вошли статьи о наиболее интересных работах участников XXII конференции программистов. Конференция проводится ежегодно в середине апреля. Организатором конференции является компьютерная школа «Алиса», которая работает на базе Института Систем Энергетики им. Л.А. Мелентьева СО РАН с 1986 года. Согласно регламенту конференции, участником может быть любой школьник или студент очного отделения вуза. Несмотря на то, что большинство участников – бывшие и настоящие ученики «Алисы», конференция уже давно приобрела межрегиональный статус. В XXII конференции успешно выступили гости из г. Железногорска Красноярского края, их статья также включена в сборник. Редакторы по традиции оставляют без изменений стиль и авторские особенности текстов; каждая статья – это живой, оригинальный рассказ автора о выполненной работе.
Коллектив редакторов

Секция школьников

Машина Поста



Хамисов Олег.

Компьютерная школа «Алиса».

8 класс, школа № 24. Иркутск

«Внешний вид» машины Поста.

Машина Поста не существует в реальной жизни; это устройство представляет собой мысленную конструкцию, существующую лишь в нашем воображении и отражающую многие существенные черты вычислений на реальных компьютерах. Её создал в 1936 году американский математик Эмиль Л. Пост с целью изучения и уточнения одного из центральных понятий математики «алгоритм» [1,2]. В том же году была изобретена ещё одна подобная абстрактная машина – машина Тьюринга. Когда несколько лет спустя появились первые ЭВМ, оказалось, что основные принципиальные черты этих машин были предвосхищены в конструкциях Поста и Тьюринга.

Машина Поста состоит из бесконечной ленты, разделенной на клетки одинакового размера и каретки, которая обозревает одну из клеток ленты (см. рис. 1, на котором каретка изображена в виде вертикальной стрелочки).


Рис. 1.
Каждая клеточка может находиться в двух состояниях: пустая (рис. 2а) и заполненная (рис. 2б).








а б

Рис. 2.


Работа машины Поста заключается в движении каретки вдоль ленты, заполнении или опустошении клетки. Каретка может выполнять приведенные ниже команды:

  • Сдвиг каретки на клетку вправо (R или RIGHT)

  • Сдвиг каретки на клетку влево (L или LEFT)

  • Заполнение клетки (P или PUT)

  • Опустошение клетки (D или DELETE)

  • Передача управления [выбор: если клеточка, обозреваемая кареткой, заполнена, выполняется первая написанная команда, если нет – вторая] (I или IF)

  • Стоп (S или STOP)

Программой машины Поста называется непустой список команд машины Поста, обладающий двумя свойствами:

    1. на k-ом месте в списке стоит команда с номером k (k=1, 2, …);

    2. передача управления осуществляется на одну из команд в списке.

Любое число n в машине показывается заполненными клеточками в виде n+1 (для отличия пустой клеточки от нуля). Стоящие подряд заполненные клеточки называются массивом.
Возможности машины Поста:

  • Сложение натуральных чисел.

  • Умножение натуральных чисел.

  • Деление чисел (аналог команды div в Паскале).

  • Вычитание из большего натурального числа меньшего натурального числа.


Примеры программ:

Пример 1. Прибавление единицы (каретка справа от массива)

  1. L 2

  2. I 3 1

  3. R 4

  4. P 5

  5. S

Иллюстрация:

1: начальное состояние 3: сдвиг вправо на одну клеточку





2: поиск правого края массива 4: заполнение клеточки и остановка





Рис. 3.


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

Пример 2. Сложение двух чисел, находящихся на ленте на любом расстоянии (каретка между числами).

  1. R 2

  2. I 3 1

  3. D 4

  4. R 5

  5. I 6 10

  6. L 7

  7. I 8 6

  8. R 9

  9. P 1

  10. S

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














нет да


















Пример 3. Сложение нескольких чисел на расстоянии одной клеточки друг от друга (каретка стоит на крайнем слева массиве).

  1. R 2

  2. I 1 3

  3. R 4

  4. I 6 5

  5. S

  6. L 7

  7. P 8

  8. L 9

  9. I 8 10

  10. R 11

  11. D 12

  12. R 13

  13. D 1

Машина работает по следующей программе:

  1. находит правую границу левого массива,

  2. сдвигается вправо и делает «проверку окончания» (если элемент был последним, то делает остановку, если нет – продолжает работу)

  3. сдвигается влево и заполняет клеточку

  4. находит левую границу массива

  5. опустошает две крайние клеточки и начинает свою работу сначала









Нет да















Пример 4. Вычитание двух чисел, находящихся на ленте на любом расстоянии (правое число меньше левого, каретка между числами, или на первой клетке левого массива).

  1. I 3 2

  2. R 1

  3. D 4

  4. R 5

  5. I 7 6

  6. S

  7. L 8

  8. I 9 7

  9. D 1

Каретка подходит к правому массиву (вычитаемое), опустошает крайнюю слева клетку, смотрит, была ли эта клетка последней, если была, то останавливает программу, если нет, идет к левому массиву (уменьшаемое) стирает его крайнюю справа клетку и программа начинает работать сначала.















Нет да
















Литература

  1. Успенский В.А. Машина Поста. Популярные лекции по математике, № 64 – М.: Наука. 1988. – 96 с.

  2. Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике в 6–8 классах. /Под редакцией С.И. Швацбурда - М.: Просвещение. 1977. – с. 48-60.

Арифметика в остаточных классах
Боровский Виктор

11 класс, лицей ИГУ. Иркутск
Введение

Исчисление можно проводить разными методами. Позиционные системы счисления отличаются от непозиционных тем, что для кодирования чисел используется не сумма: A = a0*P0+a1*P1+…+an*Pn, где P-основание системы счисления, а другие различные способы.

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

Система остаточных классов (СОК) – это непозиционная система счисления, числа в которой представляются остатками от деления на выбранную систему оснований Р1, Р2,...,Рn и являются взаимно простыми числами. Операции сложения, вычитания и умножения над числами в СОК производятся независимо по каждому основанию без переносов между разрядами (основаниями). Диапазон представимых чисел от 0 до P = P1*P2*...*Pn.

Если задан ряд положительных взаимно простых чисел Р1, Р2,...,Рn, то целое положительное число A, представленное в виде набора наименьших положительных остатков (вычетов) от деления числа А на выбранные основания Р1, Р2,...,Рn, можно записать в виде А =(a1, a2, ... ,an), где аi =A(mod pi).
Операции сложения/вычитания в общем виде выглядят так:

Здесь B – базис, X,Y – исходные числа, а Z – их сумма. При сложении каждый остаток складывается с соответствующим, а затем берется остаток от суммы при делении на соответствующее число в базисе.

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

Если исходные числа А, В, их сумма А+В и их произведение А*В находятся в диапазоне [0,P), то результаты операций сложения А+В и умножения АВ могут быть однозначно представлены соответственно остатками gi и ri по тем же основаниям Рi, т.е.

А = (a1, a2,...,an), B = (b1, b2,...,bn)
А+В = (g1, g2,...,gn), АВ = (r1, r2,..., rn), где gi = ai+bi, ri = ai*bi.
Такие операции, как деление, сравнение и др., требующие информации о величине всего числа, в СОК выполняются по более сложным алгоритмам. И в этом заключается существенный недостаток данной системы счисления, сдерживающий ее широкое применение в качестве компьютерной арифметики. Однако сегодня даже в самых современных компьютерах при работе с большими и очень большими числами используют СОК, ибо только эта арифметика позволяет получать результаты вычислений в реальном времени. В таких случаях в качестве оснований СОК применяют величины, близкие к 2m (m – двоичная разрядность компьютера), например 2m –1-1, 2m-1, 2m –1+1 и т.д. Компьютер вычисляет результат по одному из модулей за один проход. Другие области применения СОК – помехоустойчивое кодирование, криптография и т.п.

Начиная с 1952 года, специалисты многих стран мира, включая и СССР, занимались проблемой повышения скорости выполнения “неудобных” операций в СОК [3]. Особую роль в решении данной проблемы сыграл Израиль Яковлевич Акушский [4]. Немалый вклад в эту область науки внесли также Д.И. Юдицкий, В.М. Амербаев, А.А. Коляда [1,2].


Цель работы

Целью данной работы было исследование возможности использования СОК для реальных вычислений. Для выполнения поставленной задачи необходимо было написать:



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

  • Позиционную арифметику, способную работать с длинными числами, так называемую «длинную арифметику».

  • Средства для перевода из СОК в «длинную арифметику» и обратно.

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

  • Оценка быстродействия отдельных частей и всей программы в целом.


Описание алгоритмов и программы

Программа может переводить числа из позиционной системы в систему СОК и обратно. Представление чисел в СОК было показано выше, в разделе «Введение». В теле программы число – это одномерный массив, содержащий в каждой своей ячейке остаток от деления на соответствующее основание. Основаниями в моей программе выбраны последовательные простые числа, начиная с 65521, и кончая 49117. Всего таких чисел 1500. Такие большие числа не случайны, ведь максимальным числом, используемым в программе, является произведение оснований, а большие остатки дают большую верхнюю границу.


Пример представления числа.

Возьмем некоторое число, например, 27 и систему оснований из 3,5 и 7. Остаток от деления на 3 равен 0, на 5 равен 2, на 7 равен 6. Отсюда 27=(0,2,6).

Затем над представленными таким образом числами можно производить различные действия: сложение, вычитание, умножение и проверять на равенство. Из-за сложности операций деления и сравнения потребовалось реализовать «длинную арифметику». Деление представляет собой, так сказать, «отложенную операцию». Т.е. в процессе вычислений число представляет собой дробь , где a и b – представленные в СОК числа. После конца вычислений они будут переведены во внутреннее представление «длинной арифметики», поделены, и результат будет получен.

Из-за представления чисел в виде дробей арифметические операции над числами претерпели незначительные изменения, выраженные в том, что теперь они представляют собой действия над дробями. Например, сложение: . Затем над числителем и знаменателем проводятся вычисления по отдельности, как над числами в СОК.

Преимущество системы остаточных классов в том, что при росте числа знаков само представление чисел растет намного медленнее, т.е. число остатков растет очень медленно. Так, например, для примерно 9 тысяч знаков требуется всего 1500 остатков. Каждый остаток – 2 байта. Всего 3000 байтов. Для представления в позиционной двоичной системе требуется 4096 байт. Экономия в 4096/3000 = 1,365 раз; при вычислениях это дает еще больший выигрыш; например, сложим два числа, представленными 3000 байтами, что потребует по 3000 операций сложения и проверки переноса, а также сколько-то самих переносов, всего – более 6000 операций; и это только сложение. А сколько займет умножение, даже и сказать трудно. И это без учета вспомогательных операций. А в системе остаточных классов то же сложение займет чуть больше 3000 операций (по 1500 сложений и взятий остатков). Экономия примерно в 2 раза. А при умножении данные показатели еще лучше, потому как на перемножение остатков требуется так же 3000 операций, а умножение в позиционной системе потребует множество сложений. По меньшей мере, одно, если, конечно, не на ноль умножать. В результате умножения на ноль потребуется обнулить больший объем памяти (4096 байт против 3000). А в общем, количество равно сумме всех цифр у какого-нибудь из чисел. Хорошо еще, если она будет меньшей из двух возможных. А если нет, то что делать? Сравнивать их тоже очень долго.

Отсюда видно, что СОК имеет много преимуществ. Но есть «неудобная» операция деления, которая требует знаний о величине числа. Её пришлось реализовать с помощью той самой «медленной» позиционной арифметики. Но она в процессе вычисления не используется, а откладывается до конца вычислений, поэтому потери времени минимальны.

Теперь о «длинной арифметике», реализованной в программе. В процессе написания было определено, что при малых длинах чисел она быстрее из-за хорошей оптимизации (используется не все 4096 байт, а только начальная часть), но с ростом длины чисел быстродействие быстро падает. Но при использовании изменяемой длины базы остатков действия в СОК даже при малых числах остаются более быстрыми.

Оптимизация в «длинной арифметике» ведется в основном благодаря тому, что в самом числе хранится информация о его длине. Благодаря этому свойству происходит меньше операций, потому что работа ведется на меньшем массиве данных. Похожая система применена в СОК. Но число остатков там для всех чисел одинаково и меняется только одновременно: либо увеличивается при повышении разрядности чисел, либо уменьшается, если не требуется столько оснований. Но процесс изменения количества долог и не может применяться часто. Поэтому приходится делать достаточный запас для того, чтобы избежать ошибок переполнения, которые достаточно трудно отследить по той причине, что при выходе за границы представления числа переходят через 0 в начало, ведь остатки и числа, ими заданные, повторяются циклически, длина этого цикла равна произведению всех оснований.

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

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

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

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


Выводы

В процессе написания работы мною были получены знания о том, что такое система остаточных классов (СОК), как с нею работать, и зачем она нужна. В процессе работы над программой я получил серьезную практику по программированию и узнал не только как пишется арифметика в СОК, но и «длинная» арифметика тоже. Также мною была написана программа, позволяющая быстро работать с длинными числами, и которую можно переделать, например, в программу обработки численных данных в реальном времени, а такие программы достаточно востребованы в настоящее время. Данная программа может решать реальные счетные задачи, но из-за того, что не были реализованы отрицательные числа и поддержка десятичных дробей, круг таких задач сейчас достаточно узок, однако, есть возможность расширения.


Литература

  1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах.- М.; Сов.Радио. 1968. - 439 с.

  2. Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. Алма-Ата: Наука. 1973. - 192 с.

  3. Синьков М.В., Губарени Н.М. Непозиционные представления многомерных числовых систем. Киев. - Наукова думка. 1977. - 149 с.

  4. Синьков М.В., Синькова Т.В., Федоренко А.В., Чапор А.А. Нетрадиционная система остаточных классов и ее основоположник И. Я. Акушский.- www.icfcst.kiev.ua,10.02.1999.


  1   2   3


©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет