Материал из ProgSchool

Уважаемые ученики 10 класса. Чтобы быть в курсе событий, рекомендую подписаться на изменения этой страницы: http://www.progschool.ru/w/index.php?title=Study/School117_20112012_Lessons&feed=atom&action=history

Условия

Количество баллов

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

Исходим из того, что в день можно получить 0, 1 либо 2 балла. Причём бывают задачи, являющиеся частью других задач. То есть можно решить часть задачи на 1 балл, а можно всю задачу на 2 балла, но нельзя за всё это получить 3 балла.

Баллы суммируются. Количество баллов напрямую влияет на оценку.

• 28 баллов и больше - пятёрка,
• от 14 до 27 баллов - четвёрка,
• от 7 до 14 баллов - тройка,
• 6 баллов и меньше - двойка.

То есть, чтобы получить пятёрку, нужно либо на каждом уроке решать двубальную задачу, либо решать задачи дома. Чтобы получить четвёрку нужно на каждом уроке решать однобальную задачу.

Если вы пропускаете уроки, то нужно решать задачи дома. Считайте это своим домашним заданием. Выходит так, что те, кто не пропускают занятий и на каждом уроке решают двубальную задачу, освобождаются от домашних заданий :)

Также напоминаю, что есть серьёзный бонус в виде скоропечатания. Тот, кто овладеет слепым методом печати на клавиатуре и будет быстро печатать, может заработать до 4х дополнительных баллов.

Если кому-то интересно, то можно почитать о том,

• почему я ввёл рейтинг
• по какому принципу баллы распределяются по оценкам
• можно ли взять баллов в долг

Ограничения

Важные ограничения:

1. Ученик первого уровня не может получить пять до тех пор, пока не перейдёт на второй. Исключение составляют те, кто учится в классе первый год.
2. За неделю можно получить не более 6 баллов. Это сделано, чтобы ограничить лавинную сдачу задач в конце семестра. В последние 4 недели семестра это ограничение будет соблюдаться очень строго.
3. Ограничения могут дополняться на основе прецедентов, но не позднее, чем за школьную четверть до конца семестра. Т.е. о последних ограничениях я могу сообщить на первом занятии после осенних или весенних каникул.

Порядок сдачи работ

Сданной считается работа, отправленная мне по почте.

Оформление программ

Задачи не принимаются, если содержат дурнопахнущий код.

Основные критерии:

• Стандарт кодирования, аккуратность оформления кода.
• Взаимоотношения между методами, организация данных внутри класса.
• Взаимоотношения между классами, организация данных программы между разными классами.
• Размер методов, запутанность.
• Явная неэффективность алгоритмов.

Порядок такой:

1. Я проверяю задачу.
2. Высказываю пожелания.
3. Пожелания надо исправить.

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

Стандарт кодирования:

• Оформление скобок и отcтупов должно быть выполнено в следующем стиле:

if ()
{
    something;
}
else
{
    something else;
}

• Размер таба = 4 пробела.
• Правила именования пакетов, классов, методов и переменных приведены здесь: http://www.oracle.com/technetwork/java/codeconventions-135099.html.
• Те же правила относятся к интерфейсам, но следует дополнять их префиксом _I_.
• Название класса совпадает с именем java-файла.
• Пункты сверху могут уточняться и дополняться на основе прецедентов.
• Что не оговаривается выше, строго требоваться не будет, но прочие пожелания к оформлению кода изложены здесь. Кому интересно - можете почитать.

Что говорит о запутанности:

• Сложно разобраться в методе:
  • Желательно, чтобы метод был не более 20-30 строк. (Минимальный размер не ограничен, если надо, то можно делать методы длиной в одну строку. Так часто бывает)
  • Метод должен оперировать сущностями одного уровня. Т.е. если он оперирует несколькими матрицами, то он не должен опускаться до уровня конкретных элементов.
  • Большое количество уровней вложенности внутрь циклов и условных операторов.
  • Неоправданно много точек выхода из метода.
• Много чего ещё, но об этом я напишу, когда придёт время.

Клавиатура

• 300 знаков в минуту и больше - четыре балла
• от 250 до 299 - три балла,
• от 180 до 249 - два балла,
• от 120 до 179 - один балл,
• от 70 до 119 - ноль баллов,
• от 50 до 69 - минус один балл,
• менее 50 - минус два балла.

Второй семестр (11 января - 31 мая)

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

Впрочем, кто-то может и не осилить заморскую речь. Поэтому предлагаю по 2 балла за перевод на русский каждой из этих статей.

Уровень 1

Решаем задачи с acmp: 131, 233, 550, 504, 297, 336, 449, 66, 534.

Уровень 2

Решаем задачи с acmp сложностью не менее 35%. Решаем задачи на тему "Сортировка и последовательности". Те, кто решил 7 задач на "Сортировки и последовательности", переходят на тему "Разбор строк"

Далее "Двумерные массивы", "Рекурсия, перебор".

Конец второго семестра

Напоминаем, что до конца года осталось совсем немного времени. Последнее занятие второго семестра состоится 23 мая. Так что постарайтесь, если хотите получить хорошую оценку.

Первый семестр (1 сентября - 31 декабря)

Лекции

В начале некоторых уроков будет даваться теоретическй материал. Буду стараться, чтобы это занимало от 20 до 40 минут. Посторонними делами заниматься в это время будет нельзя, чтобы не отвлекать меня и других, а также, чтобы свести к минимуму повторения в индивидуальном порядке. Поэтому, если вы считаете, что всё знаете или можете изучить самостоятельно, то приходите ко второму уроку, чтобы не мешать.

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

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

Расписание лекций

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

Лекции открытые. Могут приходить все желающие. Начало — 8:30, продолжительность — 20-40 минут.

Те, кто может свободно выбирать между вторником и средой, выбирайте среду.

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

Уровень 1

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

Основная масса ребят получила следующие задачи (все по 2 балла):

• Статистика
• Пилообразная последовательность
• Годовой баланс
• Дороги
• Издевательство
• Светофорчики

Ещё была серия задач про матрицы.

Уровень 2

Метод Гаусса

Решение системы линейных алгебраических уравнений методом Гаусса (7 + 3*k)

• Работающий алгоритм на хороших случаях - 2 балла.
• Разбор случаев несовместных систем и систем с бесконечным числом решений - ещё 2 балла.
• Выбор главного элемента по столбцу - 1 балл.
• Красиво оформленный код, к которому у меня не будет замечаний - ещё 2 балла (разумеется, программа, которая ничего не умеет делать, не сможет получить 2 балла по этому пункту).
• Есть страница с тестами. Нужно придумать неправильное решение, которое проходит все эти тесты, а также предъявить пример, на котором бы решение работало неверно. Решение должно быть нетривиальным, т.е. это не должно быть просто узнавание предъявленных случаев и вывод заготовленного ответа. За каждое неверное решение, выявляющее неполноту существующих тестов, и дополнение в виде тестов, закрывающих эту прореху, можно получить по 3 балла.

Материалы по теме:

• http://www.uchites.ru/files/nummethod_book_chapter1-1.pdf
• http://referats.5-ka.ru/49/28103/1.html
• Study/Cycles/Gauss/Tests
• http://acmp.ru/index.asp?main=task&id_task=198

Примеры:

3
1 0 2 5
0 0 2 5
0 -1 2 10

0 -5 2.5

Также можно тестировать свои решения тут: Acmp-198

Вычисление определителя квадратной матрицы методом Гаусса (2)

В дополнение к решению СЛАУ можно получить 2 балла. Важно: обратите внимание на слово "квадратной". Значит, из файла считывается квадратная матрица.

Общий код алгоритма Гаусса для решения СЛАУ и вычисления определителя (2)

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

Я бы попробовал сделать так:

• алгоритм обрабатывает матрицу MxN, приводя её к диагональному виду, пока не упрётся куда-нибудь (в нули или в одну из сторон); на выход выдаёт полученную матрицу. Это общая часть программы.
• полученную матрицу каждая часть по-своему обрабатывает.
  • Модуль решения СЛАУ интересуется столбцом сводных членов и диагональю, получая ответ x_i = a[i][n+1]/a[i][i].
  • Модуль вычисления определителя перемножает диагональные элементы и получает ответ.

Вычисление обратной матрицы методом Гаусса (2)

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

Без предыдущей задачи ставить баллы за эту не интересно. Но можно не вычислять определитель, решив лишь предыдущую задачу и эту.

Оформление вывода задач (9)

Создать модуль, который:

• легко бы внедрялся во все ваши программы, которые обычно требуют файлового или консольного ввода и вывода. (2 балла, обязательное условие)
• позволял бы настраивать способ ввода и вывода (ещё 2 балла):
  • ввод из файла
  • ввод со стандартного входа.
  • вывод в файл,
  • вывод на стандартный выход,
• дополнительные требования к выводу:
  • в HTML файл (1 балл),
  • на любые комбинации (1 балл),

Дополнительное требование к параметрам командной строки. При выполнении всех предыдущих требований параметров становится довольно много. Было бы хорошо, если бы они были устроены привычным для пользователя консольных команд способом (опции -i, -o и т.п.), а также продокументированы при вызове команды с опциией -h или --help. Это стоит ещё 3 баллов.

RSA

Алгоритм быстрого возведения в степень (2)

Даны три числа: A, B, C. Надо найти остаток от деления на C числа A^B

Материалы: статья в Википедии

Прикрутить алгоритм быстрого возведения в степень к BigInteger. (2)

Материалы: документация по BigInteger

Проверить эффективность и правильность своей программы можете на следующем примере: http://projecteuler.net/problem=48

Универсальный алгоритм возведения в степень для Integer и BigInteger. (2)

Бонус задача для тех, кто понимает, о чём речь.

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

Решение ax = by + 1 в целых числах. (4)

Нужно решить уравнение в целых числах, где x и y - неизвестные.

Шифрование и дешифрование строки текста методом RSA. (6)

Нужно аккуратно объединить решения предыдущих задач. Добавить преобразование текста в подходящие для обработки числа.

Для определённости поставим задачу так:

• Исполняемый файл работает в одном из трёх режимов:
  • На вход подаётся открый ключ и строка текста. Надо получить число, являющееся зашифрованной строкой.
  • На вход подаётся секретный ключ и число. Надо получить из числа исходную строку.
  • Пусть даны 2 простых числа p и q - сомножители числа n, а также e - показатель степени, входящий в открытый ключ. Нужно сгенерировать секретный ключ.
• Режимы переключаются аргументом командной строки.
• Справка по аргументам выдаётся при запуске с аргументом --help, -h, либо при запуске программы без аргументов.