Темы исследовательских работ к вопросу 3 icon

Темы исследовательских работ к вопросу 3


Смотрите также:
Методические материалы вопросы для повторения и контрольных работ > Вопросы проблемного...
Методические материалы вопросы для повторения и контрольных работ > Вопросы проблемного...
Темы выпускных квалификационных работ министерство образования и науки российской федерации...
Темы: «Сказка ложь, да в ней намек». Окно в мир литературы и живописи...
Методические указания по выполнению курсовых работ для студентов экономических специальностей...
Темы курсовых работ министерство образования и науки российской федерации государственное...
Примерные темы исследовательских работ для 9 класса...
Программа элективного курса «Пища глазами химика»...
Примерные темы учебно-исследовательских работ для выбора учащимися 6-8 классов на 2011-2012...
Конкурс исследовательских работ старшеклассников «Человек и война. Цена Победы»...
Конкурс исследовательских работ старшеклассников «Человек и война. Цена Победы»...
Методические рекомендации Подготовка исследовательских краеведческих работ Обучающимися в рамках...



Загрузка...
скачать

-

Т е м а л е к ц и и: Системы счисления и их применение


В о п р ос ы :

  1. Исторические сведения.

  2. Однозначность записи в позиционной системе счисления.

  3. Признаки делимости.

  4. р-адические числа.

  5. Системы счисления и игры.



В о п р о с 1. Исторические сведения.


Темы исследовательских работ к вопросу 3

  1. Исторический экскурс по зарождению и развитию позиционной системы счисления, а также алгоритмов арифметических операций в таких системах [1 – 2].



P. S. Сама по себе эта тема необъятна. Вследствие чего необходимо разделить её не отдельные проекты. Принцип деления может быть построен территориальном делении. Например, Вавилон, Древний Египет, Южная Америка, Китай, Индия, страны ислама, Европа, Русь. Или – во времени: до новой эры, средние века, эпоха возрождения, XIX – XX века.


Литература к первому вопросу:

  1. Выгодский М. Я. Арифметика и алгебра в древнем мире. М.: Наука, 1987. – 368 с. [§I.2. Нумерация (Древний Египет). С. 15 – 17; §II.3 – 5 (Вавилон). С.89 – 99; С. 15 – 17; §III.3 – 7 (Древняя Греция). С.241 – 265].

  2. История математики М., т. 1 – 3, 1970 – 1972

  3. Энциклопедия для детей. Т11. Математика. М.: Аванта+,2002. – 688 с. [Ст. Старинные записи системы чисел. С. 12 – 19; ст. Позиционная система счисления. М.120 – 124; ст. Название больших чисел. С. 125 – 128]

  4. Депман И. Я. История арифметики. М.: Учпедгиз, 1959.

  5. Веленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики: Арифметика, алгебра, геометрия: книга для учащихся 10 – 11 классов общеобразовательных учреждений. М.: Просвещение, 1996. – 320 с. [§I.1. Системы счисления. С. 8 – 12]

  6. Фомин С. В. Системы счисления. М.: Наука, 1980. – 48 с. (ППЛМ. Вып.40)



В о п р о с 2. Однозначность записи в позиционной системе счисления.


Теорема 2.1. Для любых натуральных чисел и существуют единственные числа и {0, 1, 2, … , } такие, что

.


Доказательство основано на методе мат. индукции (см. Глава 1. Целые числа. §2. Иррациональность других квадратных корней. С. 18 – 19 из [1]).


Примет 2.1.Уравновешенная система счисления (Глава 1. Числа и комбинаторика
§ 1.1. Позиционные системы счисления. С. 6 – 8 из [3]). Рассмотрим обычную троичную систему счисления. Заменив в ней цифру 2 на число , получим систему счисления, в которой цифрами являются , 0, 1. Таким образом можно потупить с любой системой счисления, в которой основание натуральное число. Такие системы называют уравновешенными.

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

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


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


Примет 2.2. Факториальная система счисления ( задача № 1.15 из [2]. C. 10). Любое неотрицательное целое число п представимо единственным образом в виде:

,

где

Основатель теории множеств Георг Кантор (1845 – 1918, родился в Санкт-Петербурге) предложил рассматривать системы счисления со смешанными основаниями. Запись в таких системах счисления выглядит так:



Здесь основания, цифры, , расшифровывается следующим образом:



Частным случаем таких систем является факториальная, которая получается при , .

Системы со смешанным основанием всем известны из повседневной жизни. Например, 1 неделя, 2 дня, 3 часа, 4 минуты, 56 секунд, 789 миллисекунд в указанной выше записи примет вид:




Примет 2.3. Биномиальная система счисления ( задача № 2.84 из [2]. C. 25). Любое неотрицательное целое число п представимо единственным образом в виде:

,

где числа x, y, z – целые числа такие, что y z


Примет 2.4. Фибоначчиева система счисления (задача № 3.132 из [2]. C. 44). Любое неотрицательное целое число п не превосходящее т-го члена последовательности Фибоначчи представимо единственным образом в виде:

,

где все числа равны 0 или 1.


Замечание 2.2.

  1. Числа Фибоначчи определяются посредством возвратного уравнения



с начальными условиями и .

  1. В фибоначчиевой системе счисления числа могут быть записаны не однозначно, так например, число имеет две формы записи в фибоначчиевой системе счисления 110 и 1000. Если договориться, что не ставить две единицы рядом, то тогда имеет место однозначная запись чисел. Вспомните, что представление чисел десятичными дробями также имеет неоднозначную запись, и посредством договоренности мы решаем проблему об однозначной записи числа. Вследствие чего необходимо доказывать единственность записи числа в данной системе счисления (аналог теоремы 2.1)


Примет 2.5. Система счисления в остатках (китайская теорема об остатках из [2]. C. 82). Формулировка китайской теоремы об остатках: : , и :

,

и .


Примет 2.6. Мнимочетверичная система счисления (Задача 26 к §4.3 на ст.220 из [3]) Можно в качестве основания позиционной системы счисления выбирать даже комплексные числа, например, при выборе основания получается мнимочетверичная система счисления, в качестве цифр в ней используются 0, 1, 2, 3, и запись

.

Имеет место равенство:



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

Темы исследовательских работ к вопросу 2

    1. Разработка алгоритмов арифметических операций в соответствующих системах счисления.

Замечание 2.2. Необходимо доказывать единственность записи числа в каждой системе счисления (аналог теоремы 2.1)

    1. Разработка алгоритмов быстрого умножения [3; Глава III. §3.11. Быстрое умножение. С. 191 – 196].

    2. Обоснование известных алгоритмов арифметических операций [4; Глава: Числа. Про умножение. Математика допетровской Руси. Про деление. С. 32 – 42]


Литература к вопросу 2:

  1. Шафаревич И. Р. Избранные главы алгебры: учебное пособие для школьников. М.: Журнал «Математическое образование», 2000. – 380 с. (Для 7 – 11 классов).

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (Для старшеклассников).

  3. Гашков С. Б. Современная элементарная алгебра в задачах и решениях. М.: МЦНМО, 2006. – 328 с. (Для старшеклассников).

  4. Савин А. П. Я познаю мир: Математика: Дет. энцикл./ Авр.-сост. А. П. Савин и др.- М.: ООО "Издательство АСТ": ООО "Издательство Астрель", 2002. – 475 с. (для младших школьников

В о п р о с 3. Признаки делимости


Теорема 3.1. (Блез Паскаль 1623 – 1662). Пусть натуральные числа п и т записаны в виде:

,

Здесь – остаток от деления на натуральное числа р, тогда числа п и т имеют одинаковые остатки от деления на р. [1; Глава I. Натуральные числа. 2. Признаки делимости. С. 13 – 17]


Темы исследовательских работ к вопросу 3

  1. Признаки делимости. [1], [2]

  2. Обоснование алгоритмов арифметических вычислений (алгорифмов) [2]


Литература к вопросу 3:

  1. Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики: Арифметика, алгебра, геометрия: книга для учащихся 10 – 11 классов общеобразовательных учреждений. М.: Просвещение: АО «Учеб. лит.», 1996. – 320 с.

  2. Воробьев Н. Н. 1) Признаки делимости. М.: Наука, 1980. – 96 с. (ППЛМ. Вып.39)



В о п р о с 4. р-адические числа


Любое вещественное число можно записать в виде десятичной дроби вида:

. (*)

Десятичная запись числа r представляет собой сокращенную запись суммы:



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

Предлагается построить аналогичные алгоритмы с р-адическими числами, то есть числами вида:



Здесь р – простое число, 0, 1, 2, … , . Сокращенная запись этой суммы записывают в виде:



Обратите внимание, что у этого числа нет знака минус – все числа имеют одинаковый знак. К тому же после запятой они имеют конечное число знаков, но перед запятой они могут иметь бесконечное число знаков. Арифметические операции над такими числами определяются естественным образом – поразрядно. При переполнении разряда соответствующее количество единиц переноситься в старший разряд. р-адические числа образуют поле [1; Глава I. р-адические числа, с. 9 – 36]. Любое рациональное число можно записать в виде р-адического числа. Целое неотрицательное число, записанное в р-ичной системе счисления, является р-адическим числом. Запись отрицательных целых и дробных чисел вызывает небольшие затруднения, которые нетрудно преодолеть, используя корни уравнений: и .

В качестве примера, найдем форму записи числа в р-адической форме. В р-адической записи уравнение имеет вид





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

, ,

,

Первые уравнений имеют решение , . Так как цифры могут принимать только значения из множества {0, 1, 2, … , }, то уравнение



имеет такой корень, чтобы остаток от деления числа на р имел остаток нуль, а единственным таким числом из множества {0, 1, 2, … , } является , то есть корень . В итоге сумма , вследствие чего разряд заполнен полностью единица переходит в следующий разряд, а в данном разряде останется цифра 0 (соответствует 10 в десятеричной системе счисления). Так как единица перешла из разряда, определяемого нулевой степенью числа р, то -ое уравнение принимает вид: . Как и в предыдущем случае корень . Аналогичным образом находятся остальные цифры, причем для всех . Следовательно



или в сокращенной записи при




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





получаем, что цифры , . Уравнение имеет корень , так как цифра выбирается из множества {0, 1, 2, … , 6} и при этом произведение должно иметь остаток 1 при делении на 7, а единственным возможным числом их этого множества является число . Так единица переходит в следующий разряд, то цифра определяется из уравнения . Аналогично, как и выше получаем, что цифра () и при этом единица переходит в следующий разряд. Остальные цифры также равны 3 и определяются из уравнений , . Следовательно число в р-адической записи имеет вид



Темы исследовательских работ к вопросу 3

  1. Обоснование алгоритмов арифметических операций над р-адическими числами [1], [2]


Литература к вопросу 4:

  1. Коблиц Н. р-адические числа, р-адический анализ и дзета-функции. М.: Мир, 1977. – 192 с. (Глава I. р-адические числа, с. 9 – 36)

  2. Дынкин Е. Б., Успенский В. А. Математические беседы. Москва · Ижевск: РХД, 2002. – 260 с.



В о п р о с 5. Системы счисления и игры


Пример 5.1. (Игра «Ним»). Имеется три кучки камней. Двое играющих по очереди берут камни из этих кучек, причем за один ход можно брать любое количество камней, но только из одной кучки. Выигрывает тот, кто забирает последний камень.

Выигрышная стратегия в этой игре формулируется с использованием двоичной системы счисления. Построение выигрышной стратегии легко увидеть из конкретного примера. В первой кучке – 7 камней, во второй – 21 камень, в третей – 41. Представим числа 7, 21 и 11 в двоичной системе счисления 7 = (1001)2 , 21 = (10101)2 , 41 = (101001)2 . Запишем эти двоичные представления в столбик так, чтобы одноименные разряды оказались в одном столбце, а нижней строке укажем четность количество единиц (Рис. 1). Выигрышная стратегия игрока X состоит в том, чтобы после каждого его хода оставался хотя бы один столбец с нечетным числом единиц, так как при последнем ходе остается один камень вследствие чего все столбцы не содержат ни одной единицы, то есть нуль единиц – четное число, кроме последнего. Осталось доказать, что игрок Y не сможет перехватить инициативу. Начинающий (первый) игрок может взять камни из третьей кучки (нижняя строка) так, что в каждом столбце будет четное число единиц (см. рис. 2). При этом в третьей кучке осталось 28 камней, но такая ситуация для начинающего не выгодна. Поэтому начинающий игрок берет, столько камней, чтобы столбцы с нечетным количеством единиц сохранились. Например, один камень из первой кучки (см. рис. 3)




Рис. 1 Рис. 2 Рис. 3


Несмотря на это второй игрок может сделать так, чтобы во всех случаях в каждом столбце стало четное число единиц – для первого случая (см. рис. 4) берет 4 камня из второй кучки, для второго (см. рис. 5) – 12 камней из третьей кучки.




Рис. 4 Рис. 5


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


^ Пример 5.2. (Игра «Цзяньшицзы»). Имеется две кучки камней. Двое играющих по очереди берут камни из этих кучек, причем за один ход можно брать любое количество камней из одной кучки или поровну из обеих. Выигрывает тот игрок, после хода которого не остается ни одного камня.

Рассмотрим последовательность пар чисел (1; 2), (3; 5), (4; 7), (6; 10), (8; 13), (9; 15), (11; 18). Числа в парах соответствуют количеству камней в кучках. В этой последовательности пар каждое наименьшее число пары является минимальным числом среди не появившимся в предыдущих парах. Алгоритм построения второго числа пары остается под вопросом. Если число камней в кучках соответствует одному из значений пар, то начинающий (первый) игрок проигрывает. В этом нетрудно убедиться: при любом ходе первого игрока второй переводить ситуацию к числу камней в кучках соответствует одному из предыдущих членов нашей последовательности. В итоге второй игрок приведет игру за конечное число ходов к количеству камней соответствующей паре (1; 2). Покажите, что первый игрок таким образом поступить не сможет.

Перед нами возникает два последовательных вопроса. Первый вопрос: «Можно ли эту последовательность продолжить бесконечно с сохранением такой же выигрышной стратегией для второго игрока?» Ели – да, то мы должны дать ответ на второй вопрос: «Можно ли любой набор камней не соответствующий ни одному члену построенной последовательности за один ход перевести к одному из членов этой последовательности и наоборот, нельзя ли за один ход из числа камней соответствующих одному из членов этой последовательности получить один из членов этой же последовательности?». Проще говоря, можно ли построить выигрышную стратегию в этой игре методом выигрышных позиций? Ответ положительный на оба вопроса.

С той целью воспользуемся фибоначчиевой системой счисления – запишем каждое число пары в этой системе (см. ниже)

(1; 2) = ,

(3; 5) = ,

(4; 7) = ,

(6; 10) = ,

(8; 13) = ,

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

      1. Любое натуральное число входит только в одну пару.

      2. [3; § 4. Числа Фибоначчи и геометрия, пп. 15 – 17. С.106 – 111]. (Это свойство дает возможность дать другой способ построения больших чисел пары: к наименьшему числу пары надо прибавить номер её последовательности, т.е.

Ответом на второй вопрос следующий алгоритм. Пусть вначале игры число камней в кучках определяется числами и и пусть . Если пара (,) совпадет с одной из пар нашей последовательности, то первый игрок своим ходом никак не сможет пучить пару из этой же последовательности в силу свойств 1) и 2). Если числа и равны, то в нашей последовательности существует только одна пара, у которой одно из чисел будет совпадать с числом , то понятно как первый игрок переводит игру к одной из пар построенной последовательности. Дальнейшие случаи будут понятней, если мы их разберем на конкретных примерах. Выпишем еще несколько членов нашей последовательности:

, , , .

Пусть (,) = (12, 19). Рассмотрим разность = 19 – 12 = 7. В силу свойства 2) седьмой член последовательности имеет такую же разность 19 – 12 = 7 и пара с таким свойством определяется однозначно. Отсюда получает, что из каждой кучки надо взять по одному камню. Получим пару . Для любой пары вида (, ) первому игроку необходимо брать при условии, что  11. В случае, когда  11 и = 7 надо поступать, так как разобрано в следующем частном случае. Опробуйте этот алгоритм для (,) = (74, 119).

Теперь алгоритм становиться ясным и понятно как поступать в любом другом случае.

Пусть (,) = (9, 16). Среди первых шести членов последовательности ищем пару с наименьшим числом равным меньшему числу данной пары (,) = (9, 16), то есть 9. Это пара . Разность задает количество камней, которое надо брать из большей кучки.


Замечание 5.1.

  1. Аналитически каждый член последовательности, рассмотренный в примере 5.2, описывается формулой (,) [3; § 4. Числа Фибоначчи и геометрия, п. 18. С. 111 – 113]. Здесь п – натуральное число, – «золотое сечение » или число Фидия, а [а] – целую часть числа а. Такая формула не должна особо удивить тех, кто знаком с формулой Бине: (см. замечание 2.2.). Здесь .

  2. В примере 5.1 фибоначчиева система счисления нами использовалась только при получении второй компоненты пары, но в силу свойства 2) мы можем обойтись и без неё. Фибоначчиева система счисления применялась в этом примере с той целью , чтобы выяснить следующий вопрос: «Можно ли построить аналогичный алгоритм поиска выигрышной позиции как в примере 5.1?». Если – да, то можно ли игру «цзяньшицзы» обобщить на большее число куч?


Темы исследовательских работ к вопросу 4

  1. Системы счисления и игры [1; 3. Алгоритм Евклида и основная теорема арифметики. 3.4. Числа Фибоначчи. Задачи № 3.158 – 159. С. 49 и 5. Числа, дроби, системы счисления. 5.3. Двоичная и точная системы счисления. С. 92 – 99] (9 – 11 классы)

  2. Обобщение игры «цзяньшицзы» на п кучек камней


Литература к вопросу 5:

  1. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (Для старшеклассников).

  2. Воробьев Н. Н. Числа Фибоначчи. Издание 4-ое, дополненное. М.: Наука, 1978. – 140 с. (ППЛМ. Вып. 6)




Скачать 131,16 Kb.
оставить комментарий
Дата22.09.2011
Размер131,16 Kb.
ТипЛитература, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх