WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 ||

3. Какой шифр лучше: вначале простая замена, потом диск Альберти или наоборот (С точки зрения математики здесь надо изучить группы подстановок.) Энигма – знаменитая немецкая шифровальная машина времён Второй мировой войны – сделана из композиции трёх дисков Альберти. Первый компьютер создан ради чтения шифра энигмы.

Среди нескольких вариантов расшифровки человек сразу отличает нормальный текст от «абракадабры». Интересно научить делать это компьютер.

Особенности криптографии как источника исследовательских тем:

• тема может уйти в историю, в программирование, в математику;

• есть ясная для школьника практическая мотивация (современная экономика держится на шифрованных электронных переводах денег, спам-фильтры и т.д.).

Математические идеи, которые понадобятся школьникам для работы:

• подстановки;

• вероятность;

• комбинаторика;

• сложность / оптимизация алгоритмов.

Материалы по криптографии можно найти на сайте http://cryptolymp.ru/ и в книжке: Зубов А.Ю. Олимпиады по криптографии и математике. М.: МЦНМО, 2006.

На пятнадцатом заседании семинара (16.03.2010) А.Б. Скопенков сделал доклад на тему «Летние конференции Турнира городов» (о них см.: сайт http://www.turgor.ru/lktg и книгу «Летние конференции Турнира городов. Избранные материалы». Выпуск 1. М.: МЦНМО, 2009).

Особенности летних конференций:

• отбор участников по итогам олимпиад высокого уровня;

• мотивировка: школьники приходят к теоремам естественным путём – решая задачи;

• проверка: жюри серьёзно читает письменные решения, возможна доработка решений по советам жюри;

• свобода: выбор из 5–6 задач, нерегламентированные занятия;

• продолжение темы после конференции – единичные случаи.

Набираются 50–80 человек после 9-го и 10-го классов. Длительность конференций около недели.

ПОЛИНОМ № 1/2010 mat hedu. r u/e- j our nal Задачи:

• учебные (не новые, но малоизвестные):

• классическая геометрия;

• комбинаторика;

• теория групп, теория чисел;

• комбинаторная геометрия;

• алгебра (реже).

Примеры задач.

1. Сложность суммирования (http://olympiads.mccme.ru/lktg/2003/summ.ru/index.htm).

За одну копейку автомат вычисляет сумму двух чисел. За какую минимальную сумму он вычислит:

1. x1 + x2 +... + x100;

2. x1 + x2 +... + x100 и x50 + x51 +... + x150;

3....

...

yi = ai1x1 + ai2 x2 +... + ainx, где i = 1,..., m n Результаты. Обозначим через L(m, n) наименьшую сумму, за которую автомат при любых коэффициентах aij гарантированно вычислит y1,..., ym. Тогда c1n2 c2n< L(n,n) <.

log2n log2n Левое неравенство строится из мощностных соображений, а правое – конструированием явной схемы.

2. Плетение корзинок (http://www.turgor.ru/lktg/2004/lines.ru/index.htm) Изобразим несколько прямых так, чтобы было видно – одна проходит над другой или под другой. Тогда некоторые картинки реализуются, а другие – нет.

Простейший пример нереализующейся картинки – с 4 прямыми.

Теорема 1. Существует бесконечное семейство нереализуемых картинок, все подкартинки каждой из которых реализуемы.

Изотопией назовём сдвиг прямых, при котором не возникают пересечения прямых по три и который не переносит прямую за «точку встречи» двух других.

Теорема 2. Реализуемость неинвариантна относительно изотопии (есть пример с 6 прямыми).

Вариант задачи. Даны горизонтальные и вертикальные прямые. Каждая точка встречи прямых описывается 0 (горизонтальная выше) или 1 (вертикальная выше).

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

Pages:     | 1 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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