Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/doclady.doc Дата изменения: Sun Sep 2 21:14:12 2012 Дата индексирования: Tue Feb 5 05:22:18 2013 Кодировка: koi8-r Поисковые слова: легирование

ТЕМЫ ДОКЛАДОВ


1) «Тройная дуэль» (куратор А. В. Хачатурян).
[Над темой начали работать
Михаил Святловский и Руслан Фадеев]
Задача придумана, по всей вероятности, Мартином Гарднером, во всяком
случае, благодаря ему стала популярной. Три человека, А, В и С, участвуют в
дуэли. Сначала бросается жребий, показывающий, в каком порядке они будут
стрелять. Вариантов шесть, поэтому удобно использовать игральную кость.
Далее в указанном порядке дуэлянты стреляют - каждый может стрелять в
любого из имеющихся на момент выстрела противников. Того, в кого попали,
уносят, и он более не стреляет. Побеждает тот, кто остаётся последним.
Известны вероятности попадания для игроков - они равны a, b и c
соответственно. Всякий дуэлянт, выбирая, в кого ему стрелять, действует
так, чтобы с большей вероятностью победить.

1. Какова вероятность победы каждого из них? Кто, вероятнее всего
победит, самый меткий, средний по меткости или наихудший стрелок?
2. Рассмотрите вариант, когда разрешается стрелять в воздух, то есть
пропускать ход.

2) «Симметрия в алгебре» (куратор Аня Кондакова).
[Над темой начали работать
Аркадий Душацкий и Дмитрий Лянге]
Сюжет о том, как симметрия упрощает жизнь, и что делать, если её нет в
условии. Предлагается изучить некоторый общий метод, который позволит
решить, например, систему [pic] или уравнение [pic].

3) «Раскрашивание графов» (куратор Юля Левицкая).


В 1852 английский географ Гутри предложил задачу: "Всякую ли карту можно
раскрасить четырьмя красками так, чтобы любые две области, имеющие общий
участок границы, были раскрашены в разные цвета?"


История этой задачи немного похожа на историю великой теоремы Ферма.

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

К. Аппелем и В. Хакеном. Это была первая крупная математическая теорема,
для доказательства которой был применён компьютер.


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


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

4) «Расчёт электрических цепей» (куратор Кир Скопцов).
[Над темой начали работать
Люба Маканина и Настя Сизова]
Постановка задачи: дан ориентированный граф без петель, но с незапрещёнными
кратными рёбрами, степень каждой его вершины не менее 2.

Каждое ребро снабжено двумя числовыми характеристиками: сопротивлением
ребра и вырабатываемой ребром ЭДС.

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


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

1) Почему данный метод работает?

2) Насколько он трудоёмок (грубо говоря, систему из какого числа уравнений
нужно решить для получения результата)?


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


5) «Коды сжатия данных» (куратор А. И. Артемьев).
Собираемся обсудить и реализовать несколько кодов.

1) Более эффективные коды для сжатия данных

2) Введение дополнительной информации в код,

чтобы можно было исправлять ошибки или пропущенные символы.

На занятии обсудили коды Хаффмана.

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

Пример изложен в: И. Л. Ерош, С. Л. Ерош «Арифметические коды с
исправлением многократных ошибок» www.mathnet.ru/ppi1923
Есть ещё одно понятное описание арифметического кодирования на

http://compression.ru/arctest/descript/arithm.htm


6) «Разбиение на пары» (куратор А. И. Артемьев).

Планируется 2 работы:

* Устойчивые разбиения;

* Образование максимального количества совместимых пар.



Представьте себя владельцем сайта знакомств. У вас есть клинты двух типов:

юноши и девушки - они хотят разбиться на пары и пожениться.

У каждого из них есть предпочтения:

* кто больше нравится, а кто меньше.

* насколько количественно ему нравится каждый партнер.


Задача - придумать хорошее разбиение. Можно по-разному определить, что
значит хорошее разбиение. Например: «Всем достался наилучший партнер из его
списка» А это если невозможно?

Как решить, что такое наилучшее из возможных разбиений?


Хотим придумать, что такое хорошо в такой задаче

и реализовать один из вариантов.


Вот несколько примеров, что такое хорошее разбиение.:

-- Устойчивые разбиения: никто не может улучшить своего положения,

найдя себе другого партнёра.

-- Суммарное число приемлемых пар максимально.

-- Суммарное счастье максимально.

-- Никто не обижен -- стараемся не допустить образования

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