Андрей Андреевич Бреслав

Раздел: 

11-1 класс.
2012/2013 учебный год
 
Второе полугодие
Урок 25.04.2013 
На следующем уроке будет дана СР по логике (по соответствующим задачам ЕГЭ)
ДЗ (к-во баллов за задание указано в скобках)

  • (1) gist.github.com/abreslav/5477507 — см. задание в комментарии
  • (1) Написать программу, которая по данным вещественному x и целому неотрицательному N вычисляет x^N, делая как можно меньшее количество умножений. Вывести ответ и количество умножений, которое понадобилось для его вычисления.
    Подсказка: x^5 = x*((x^2)^2)
  • (1) Написать программу, которая по данному x выводит список его простых делителей (с учетом кратности), делая как можно меньшее количество делений (div и mod). Вывести ответ и количество делений, которые пришлось сделать.
  • (2) На вход программе подается файл с текстом на руссом языке. Вывести разницу длинн самого длинного слова и следующего по длине, а также то из слов, следующих по длине за самым длинным, которое является первым в алфавитном порядке.
    Слово — последовательность русских букв (заглавных и строчных), с двух сторон ограниченная не-буквой (начало и конец текста то являются не-буквами).
    Пример: Мама мыла милу мылом. Ответ: 1, Мама
    Программа должна быть оптимальной по времени и памяти (просматривать текст можно лишь один раз, хранить весь текст в памяти нельзя).
    Чтобы проверить себя, найдите в Интернете текст романа В. О. Пелевина "Чапаев и Пустота" и запустите свою программу на этом тексте.

Примеры заданий для самоподготовки к СР:

  • Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

    (x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
    (y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1
    x1→y1 =1

  • Дано логическое выражение, зависящее от 5 логических переменных:
    z1 /\ ¬z2 /\ ¬z3 /\ ¬z4 /\ z5
    Сколько существует различных наборов значений переменных, при которых выражение ложно?
  • Дан фрагмент таблицы истинности выражения F: 

    x1 x2 x3 x4 x5 x6 F
    0 1 0 1 1 1 1
    1 0 1 0 1 1 0
    0 1 0 1 1 0 1

     
    Каким может быть выражение F?

Урок 18.04.2013
На уроке будет дана самостоятельная работа по задачам про Excell, кратчайшие пути в графе и чтение кода.
ДЗ: написать программу (на компьютере), снабдив ее всеми необходимыми комментариями.

  • (С4) На вход программе подаются данные о том, кто и в какое время в течение одного дня занимал какое место на автомобильной парковке.
    Определить, сколько времени (в минутах) стоянка была пуста и сколько времени все места были заняты.
    Если стоянка не была пуста, вывести минимальное количество занятых мест за день, если всегда были свободные места, вывести максимальное количество занятых мест за день. 
    Программа должна быть оптимальной как по времени, так и по памяти.

    Первым на вход программе подается число N. Далее следует N строк следующего вида:
    <Фамилия> <Время прибытия> <Время отъезда> <номер места>
    где
    <Фамилия> — строка, не содержащая пробелов
    <Время прибытия> и <Время отъезда> —  ровно две цифры, обозначающие час, двоеточие и ровно две цифры, обозначающие минуты (например 03:00). Время всегда округлено до четвертей часа, то есть возможны только записи вида 03:00, 03:15, 03:30, 03:45
    <номер места> — число от 1 до 100 включительно

    Гарантируется, что данные корректны (никто не занимал два места одновременно и никакое место одновременно не занимало более одной машины).

    Пример ввода
    Петров 12:00 14:45 3
    Сидоров 12:15 15:00 4

    Вывод
    Стоянка была пуста: 1260 мин
    Максимальное количество занятых мест: 2

Урок 11.04.2013
ДЗ (сдать решение на листочке)

  • (Задача заменена, старая версия ниже) 

    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит
    куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход
    игрок может добавить в кучу 2 камня или увеличить количество камней
    в куче в 3 раза. Например, имея кучу из 15 камней, за один ход можно
    получить кучу из 17 или 45 камней. У каждого игрока, чтобы делать ходы, 
    есть неограниченное количество камней.
    Игра завершается в тот момент, когда количество камней в куче становится
    не менее 63. Победителем считается игрок, сделавший последний ход, то есть
    первым получивший кучу, в которой будет 63 или больше камней. 
    Вначальный момент в куче было S камней, 1 ≤ S ≤ 62. 
    Будем говорить, что игрок имеет выигрышную стратегию, если он
    может выиграть при любых ходах противника. Описать стратегию
    игрока – значит описать, какой ход он должен сделать в любой
    ситуации, которая ему может встретиться при различной игре
    противника. 
    Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 
    1. а) Укажите все такие значения числа S, при которых Петя может
    выиграть в один ход. Обоснуйте, что найдены все нужные значения S, 
    и укажите выигрывающий ход для каждого указанного значения S. 
    б) Укажите такое значение S, при котором Петя не может выиграть за
    один ход, но при любом ходе Пети Ваня может выиграть своим первым
    ходом. Опишите выигрышную стратегию Вани. 
    2. Укажите два таких значения S, при которых у Пети есть выигрышная
    стратегия, причём
    – Петя не может выиграть за один ход, и
    – Петя может выиграть своим вторым ходом, независимо от того, как
    будет ходитьВаня. 
    Для каждого указанного значения S опишите выигрышную стратегию
    Пети. 
    3. Укажите значение S, при котором: 
     – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым
    или вторым ходом при любой игре Пети, и
     – у Вани нет стратегии, которая позволит ему гарантированно выиграть
    первым ходом. 
    Для указанного значения S опишите выигрышную стратегию Вани. 
    Постройте дерево всех партий, возможных при этой выигрышной
    стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева
    указывайте, кто делает ход, в узлах – количество камней в куче.

    Старая версия задачи (если Вы уже сделали ее, можете не делать новую, хотя новая полезнее для подготовки к ЕГЭ).

    Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка стоит в точке (5, 2). Ход состоит в том, что игрок перемещает фишку из точки (x, y) одним из трех способов

    • (x + 3, y)
    • (x, y + 3)
    • (x, y + 4)

Выигрывает игрок, после хода которого расстояние от фишки до точки (0, 0) становится не менее 13 (расстояние — это длина вектора, то есть вещественное число).
Какой из игроков (тот, кто делает первый ход или тот, кто делает второй ход) выигрывает при безошибочной игре. Ответ обоснуйте.

  • У исполнителя Калькулятор два вида команд
    • Прибавить 1 (увеличивает число на экране на 1)
    • Умножить на 2 (умножает число на экране на 2)

Сейчас на экране калькулятора число 1. Сколько существует последовательностей команд, в результате которых получится число 20?
Урок 21.03.2013

  • ДЗ, оценка равна сумме набранных баллов 
    • (1 балл) Дан текстовый файл, в каждой строке которого записан абсолютный путь к некоторому файлу или каталогу, в формате Windows. При этом пути к каталогам оканчиваются на "\"
      По абсолютному пути к каталогу определить, сколько у этого каталога непосредственных потомков
      Пример:
          C:\a\
          C:\
          С:\b\text.txt
          C:\b\c\
      Ответ:
          C:\ - 2
          C:\a\ - 0
          C:\b\ - 2
    • (2 балла) Дан путь, содержащий обозначения "." и "..". Построить по нему абсолютный путь или сообщить, что это невозможно
      Пример
          C:\a\..\a\b\.\c\..\.. -> C:\a
          C:\a\b -> C:\a\b
          C:\a\..\.. -> ошибка
    • (2 балла) Даны абсолютные пути к каталогам A и Б. Построить относительный путь к Б из А.
      Пример
          C:\a\b\c\
          C:\d
      Ответ: ../../../d
    • (3 балла) Дана маска и имя файла, проверить, соответствует ли имя маске.
      Примеры

      • abc abc -> Yes
      • abd abc -> No
      • ? x -> Yes
      • ?? x -> No
      • * x -> Yes
      • ?* x -> Yes
      • foo.* foo.bar -> Yes
      • *.bar foo.bar -> Yes
      • foo.?? foo.bar -> No 

Урок 14.03.2013

  • ДЗ
    • (3) Дана строка, проверить, является ли она корректным IP-адресом
      Примеры:
      192.168.0.1 — да
      270.0.0.1 — нет
      192..1 — нет
    • (4) Дана строка, проверить, является ли она корректной маской подсети (то есть корректным IP-адресом, который состоит из n страших единиц и 32-n младших нулей)
      Примеры:
      255.0.0.0 — да
      255.128.0.0 — да
      255.64.0.1 — нет
      255.0.0.1 — нет
    • (5) Даны два IP-адреса и маска подсети, проверить, относятся ли эти адреса к одной подсети
      Примеры:
      192.168.0.1, 192.168.0.15, 255.255.255.0 — да
      192.168.0.1, 192.168.0.15, 255.255.255.255 — нет
  • На следущем уроке будет самостоятельная работа. Темы
    • Системы счисления
    • Информация
    • Кодирование
    • IP-адреса

Урок 28.02.2013 — Кодировки текста

  • Задание на 3
    Дан файл с разнородными переводами строк (CR, CR LF, LF), преобразовать все переводы строк к CR LF
    Заметим, что если в файле встречается последовательность CR LF, то ее менять не нужно, то есть она превращается в один перевод строки, а если, например, LF CR, то это два перевода строки и в выходной файл должно быть записано CR LF CR LF
    Для справки: код символа CR $0D, а LF $0A
    Файлы для самопроверки
  • Задание на 4
    Дан файл с русским алфавитом в кодировке А, файл с тем же алфавитом в кодировке B и русский текст в кодировке A, создать файл с тем же текстом в кодировке B
    Архив с заданием
  • Задание на 5
    Дан файл с русским текстом в кодировке UTF-8 перекодировать его в CP1251
    Файл для самопроверки
  • На следующем уроке будет дана самостоятельная работа по материалам ЕГЭ. Темы
    • Системы счисления
    • Информация
    • Кодирование

 
Урок 21.02.2013 — Формула Шеннона и LZ
Необязательное задание

  • (3) Вычислить количество информации в файле
    • используя глобальную встречаемость символов
    • используя встречаемость символов к данному моменту
  • (4/5) Реализовать LZ-алгоритм

Урок 14.02.2013 — Алгоритм Хаффмана

  • (4) Построить код Хаффмана для данного файла вывести таблицу кодов на экран (символ — кодовое слово из нулей и единиц)
  • (5) Заархивировать файл этим кодом. Форма архива — с предыдущего урока. Для самопроверки используйте разархиватор decode.exe
    • Архив должен называться 'in.huff' и лежать в той же директории, что и программа, выходной файл называется 'out.decompressed.txt'
    • В качестве примеров текстов используйте kd.txt и lt1_txt.zip (второй файл нужно предварительно распаковать).

Урок 07.02.2013 — Префиксные коды

  • Формат архива
    • 4 байта — длина текста в байтах, то есть сколько байт должно быть в разархивированном файле
    • 1 байт — длина кодовой таблицы L, если значение этого байта 0, таблица имеет длину 256
    • L записей вида
      • 1 байт — значение символа (для вывода в разархивированный файл)
      • 1 байт — длина кодового слова W в битах
      • 3 байта — кодовое слово, учитываются младшие W битов. Например, если W = 13, то первый из трех байт учитывается целиком, а из второго учитываются пять младших битов.
    • Остальное — Код для символов исходного файла (от младших битов к старшим)
  • Задание на 3
    • Прочитать из файла кодовую таблицу, вывести ее на экран в форме
      • символ — длина — кодовое слово (из нулей и единиц)
    • Zip-архив с файлом для самопроверки, сверьте ответ с кем-нибудь из товарищей
  • Задание на 4
    • Заархивировать текст, используя таблицу из данного файла (выходной файл должен иметь описанный выше формат)
    • Файлы с таблицами можно взять из задания на 5: в одном из них текст 'Hello, world!', в другом вот этот текст.
    • Еще один файл для самопроверки, исходный текст для него.
    • Чтобы проверить себя, можно также использовать программу decode.exe
      • Архив должен называться 'in.huff' и лежать в той же директории, что и программа, выходной файл называется 'out.decompressed.txt'
  • Задание на 5

Урок 31.01.2013 — Аглоритм RLE

  • Для сжатия ч/б картинок будем использовать следующий формат архива:
    • (Два младших бита в байте будем называть служебными)
    • Если два младших бита очередного байта равны 00, то остальные биты означают длину цитаты, то есть сколько байт, следующих за данным, нужно скопировать из архива в выходной файл.
      • Пример.
        Пусть в архиве подряд идут такие байты: 16, 18, 0, 130, 240
        Первый из них — 16 (000100 00) — является служебным, два младших нуля обозначают, что это цитата, остальные шесть битов составляют длину цитаты, в данном случае число 4, значит следующие 4 байта (18, 0, 130, 240) нужно скопировать в выходной файл как есть.
    • Если два младших бита очередного байта равны 01, 10 или 11, то следующий (второй) бит этого байта хранит значение цвета (0 или 1), а остальные 5 битов хранят младшие разряды количества повторений (в байтах). При этом от значения служебных битов зависит, сколько дополнительных байтов занято под полную длину:
      • 01 — дополнительных байтов нет, то есть длина записана пятью битами. То есть байт 17 (00010 0 01) обозначает, что в выходной файл нужно записать два байта, состоящие из всех нулей.
      • 10 — один дополнительный байт хранит старшие биты длины. То есть последовательность из двух байт 22, 1 (00010 1 10 00000001) обозначает 34 (00000001 00010) байта, состоящие из всех единиц.
      • 11 — два дополнительных байта (аналогично предыдущему).
  • Задание на 3
  • Задание на 4-5 (в зависимости от качества выполнения)
    • Написать архиватор для описанного выше формата.

Урок 24.01.2013 — Представление изображений

  • Задание на 3
    • Дан двоичный файл следующего формата
      Первые 32 бита: целое число W, обозначающее ширину картинки
      Следующие 32 бита: целое число H, обозначающее высоту картинки
      Следующие W * H битов: каждый бит обозначает цвет оной точки (0 — черный, 1 — белый)
      Точки располагаются по строкам: (0, 0), (1, 0), (2, 0)... От младших битов к старшим.
      Вывести изображение на экран. Использовать процедуру PutPixel(x, y, color)
      Файл для самопроверки
  • Задание на 4
    • Загрузить изображение с помощью LoadPicture и вывести на экран (см. раздел справки “Стандартные модули/Модуль GraphABC/Рисунки”)
      Сохранить изображение в формате описанном в задании на 3, причем считать черными точки со средней яркостью <= 127, остальные — белыми.
      Пример:
    • Входное изображение Выходное
  • Задание на 5
    • Написать преобразование цветного изображения в трехбитную цветовую кодировку:
      в начале файла идут ширина и высота, а затем
      каждые три бита означают присутствие и отсутствие соответствующих компонент RGB.
      Если яркость компоненты в исходном изображении более 127, она присутствует, иначе — отсутствует.
      Реализовать запись и чтение таких файлов.
      Пример:
    • Входное изображение ?Выходное?

Урок 10.01.2013 — Битовое представление данных

  • На следующем уроке (24.01.2013) будет самостоятельная работа. Вопросы для подготовки:
    • Представление чиселв  двоичной системе счисления
    • Двоичный дополнительный код (представление отрицательных чисел)
    • Битовые операции: and, or, xor, not
    • Сдвиги: shl, shr
    • Как выразить операции умножения и деления с остатком через битовые операции?
    • Как прочитать значение данного бита в числе?
    • Как написать данное значение в i-тый бит числа?
    • Чему равен результат данной операции (8 бит со знаком): 12 and 3 = ?, 12 or 3 = ?, 12 xor 5 = ?, not 29 = ?, 13 shl 7 = ?, 17 shr 4 = ?, -2 shr 3 = ?
  • Домашнее задание
    • (3) Закрашенная фигура описана числом, в котором младший бит обозначает круг, следующий бит — квадрат (если установлены оба бита — квадрат со скругленными углами (RoundRect), если оба не установлены — буква “А”), следующие три бита — цвет заливки: красный, зеленый, синий (если установлено более одного бита цвета, соответствующие цвета комбинируются опрацией OR, если все биты цвета нулевые — цвет черный).
      Нарисовать на экране фигуры, соответствующие числам от 0 до 31 включительно, расположить из в 8 строк по четыре фигуры в каждой.
    • (4) Граф задан N+1 числом типа Integer: числом вершин N от 0 до 31 включительно и матрицей смежности, закодированной в виде N чисел, в каждом из которых i-тый по старшенству бит соответствует i-тому столбцу матрицы (младший бит соответствует столбцу номер 0, и так далее). По этим N+1 числу создайте файл в формате dot, отображающий данный граф.
    • (5) Дан файл (произвольного размера N), содержащий текст, в котором использовано не более 16 различных символов (включая пробелы, переводы строк и пр.).
      Напишите две программы: архиватор, который по данному файлу создает ”сжатый” файл вдвое меньшего размера (N/2 + C, C — небольшая константа), и разархиватор, который по сжатому файлу восстанавливает исходный файл.
      Входной файл желательно просматривать ровно один раз и не загружать целиком в оперативную память.

Первое полугодие

  • Урок 13.12.2012 — Преобразования логических схем
    • Задача 1. Дана логическая схема, выделить в ней компоненты (слабой) связности, каждая компонента должна быть обведена прямоугольником (сипользуйте конструкцию subgraph cluster_i {})
       
    • Исходный граф Результат

       
    • Задача 2. Дана логическая схема с одним выходом. Вывести аналогичную ей булеву формулу
       
    • Входная схема Формула
      ((!1) & (1 | 0))
    • Задача 3. Дана логическая схема, где вместо входных значений (1 и 0) указаны переменные. Преобразовать эту схему так, чтобы в ней не было гейтов ИЛИ (|), и при этом вычисляемая функция не изменилась
       
    • Вход Выход
    •  
  • Урок 29.11.2012 — Булевы схемы
    • Задание на 3
      Дан граф в формате dot
      Проверить, что он удовлетворяет следующим требованиям к булевым схемам:
      1) вершины помечены только операциями 0, 1, &, |, !
      2) 0 и 1 имеют 0 входящих ребер, & и | — по два входящих ребра, ! — одно входящее ребро
      Вывести этот граф, пометив вершины, не удовлетворяющие требованиям, красным цветом
    • Задание на 4
      Дана правильная логическая схема в формате dot
      Вывести ее, пометив ребра вычисленными значениями, и добавив выходные вершины со значениями результатов
      Пример:
    • Задание на 5
      Выполнить одно из двух следующих заданий:
      а) Дан граф логической схемы в формате dot. Если в нем есть цикл, выделить его красным цветом
      б) Дана логическая схема в формате dot, вычислить таблицу ее значений для всех возможных входов
  • Урок 15.11.2012 — группа 1 (А-К) — Алгоритм Флойда-Уоршалла
    • (на 3) Прочитать из файла граф с весами на ребрах.
      Веса задаются как метки в формате .dot (3 -> 5 [label="7"])
      Веса могут быть отрицательными.
      Построить матицу смежности этого графа, где в ячейках записаны веса ребер.
      Отсутстве ребра обозначается нулем.
    • (на 4) Записать в вершины длины кратчайших путей из данной
    • (на 5) Выделить цветом кратчайший путь между данной парой вершин
    • Примеры:
Исходный граф На 4 На 5: из вершины 10 в 14

 

  • Урок 08.11.2012 — Чтение графа из файла
    • Задание: прочитать ориентированный граф из файла в формате .dot.
      Не забудте учесть: цепочки вершин (1 -> 2 -> 3), кратные ребра
      Не обязательно учитывать: имена, не являющиеся числами, атрибуты вершин и ребер, подграфы

      • (на 3) Построить матрицу смежности этого графа
      • (на 4) Вывести  в формате .dot тот же граф, но сделать вершины, из которых не выходит ни одного ребра, прямоугольными
      • (на 5) Дополнить граф до транзитивного и вывести результат в формате .dot
  • Урок 11.09.2012 — GraphViz

 

 
Задания для 10-1 класса
 
 

  • Урок 03.05.2012 — Поиск пути на графе
    • Регулярный граф задан в текстовом файле матрицей символов (array[1..N, 1..M] of Char)
    • В матрице ровно один раз встречается символ '1' и ровно один раз встречается символ '2'
    • Также в матрице встречаются символы '0', обозначающие стенки
    • Задача: узнать, есть ли путь из клетки '1' в клетку '2', не проходящий через клетки '0'
      • Ходить из данной клетки можно вправо, влево, вверх и вниз, по диагонали ходить нельзя
    • Необходимо написать обход графа (в глубину) двумя способами:
      • Рекурсивно
      • Без рекурсии, с явным использованием стека
    • Ответом является фраза "Путь есть" или "Пути нет"
  • Урок 12.03.2012 — Динамическое программирование
    • Путь на матрице с минимальной суммой
    • Наибольшая возрастающая подпоследовательность
    • Редакционное расстояние (расстояние Левенштейна)
    • Для справки см. материалы прошлых лет: Урок 1, Урок 2
  • Урок 27.02.2012
  • Урок 06.02.2012
    • Определение:
      • Двоичное дерево поиска (ДДП) — двоичное дерево, в котором для каждой вершины V выполняется следующее:
        • значения во всех вершинах в левом поддереве V меньше значения V
        • значения во всех вершинах в правом поддереве V больше или равны значению V
    • Задачи про двоичные деревья поиска
      • add(t, x) — добавление элемента в ДДП
      • check(t) : Boolean — проверить, является ли данное дерево ДДП
      • monkeySort(a) — отсортировать массив а следующим способом: построить из его элементов ДДП, а затем записать все его элементы обратно в массив, в порядке возрастания
      • buildFromSorted(a) : PTree — дан отсортированный массив а, построить из его элементов сбалансированное ДДП
      • get(t, i) : PTree — вернуть указатель на i-тый по порядку элемент в ДДП (nil, если такого нет)
      • del(t, x) : Boolean — удалить значение x из ДДП, вернуть true, если значение в дереве было, и false если не было. 
      • delGreater(t, x) — удалить из ДДП все вершины со значением большим или равным x
      • prev(t, x) : PTree — вернуть указательно на элемент ДДП, стоящий по порядку прямо перед x. Вернуть nil, если такого элемента нет
      • printRange(t, a, b) — распечатать в порядке возрастания все элементы ДДП, имеющие значения в диапазоне от a до b. Следите за тем, чтобы не обходить ненужные части дерева.
      • longestGap(t) : Integer — какова самоя большая разность подряд идущих элементов ДДП?
      • pullUp(t, x) — поднять вершину со значением x на один уровень вверх. Разрешается добавить в дерево ссылки на родительские вершины.
      • toSortedList(t) : PList — построить из всех элементов ДДП список, уопрядоченный по возрастанию
  • Урок 30.01.2012
    • Задачи про двоичные деревья
      • count(t) — количество вершин в дереве
      • height(t) — высота дерева
      • leafCount(t) — количество листьев в дереве (лист — вершина, у которой нет детей)
      • sum(t) — сумма значений во всех вершинах дерева
      • find(t, x) : Boolean — есть ли в дереве вершина со значением x
      • printLevel(t, k) — распечатать все вершины на глубине k (в строчку или в столбик)
      • leftmostLeaf(t) : PTree — вернуть указатель на самый левый лист в дереве
      • delLeaves(t) — удалить все листья
      • delDeeperThan(t, k) — удалить все вершины на глубине больше k
      • delSingleParents(t) — удалить все вершины, у которых ровно один ребенок
      • allDiffferent(t) — все ли элементы дерева различны
      • equal(t1, t2) — одинаковы ли два дерева
  • Урок 23.01.2012
    • Задачи в классе и на дом
      • checkSorted(l) — отсортирован ли список по возрастанию?
      • checkAllEqual(l) — все ли элементы списка равны между собой?
      • checkAllDifferent(l) — все ли элементы списка различны?
      • indexOf(l, x) — на каком по счету месте в списке l стоит число x. -1, если x в списке не встречается
      • cut(l, i, n) — удалить из списка n элементов, начиная с i-го
      • insToSorted(l, x) — список l отсортирован по неубыванию. Вставить число x в этот список так, чтобы он остался отсортированным по неубыванию
      • delAll(l, x) — удалить все вхождения числа x в список
      • insAfter(l, x, y) — вставить x после первого вхождения y в список l
      • lpos(l, m) — поиск подсписка. Для l = (1, 2, 3, 4), m = (2, 3), ответ 2 — в l, с которого начинается вхождение m
      • palindrom(l) — является ли список палиндромом?
      • longestAsc(l) — длина самого длинного возрастающего отрезка списка. Для списка (2 1 3 5 1 6) ответ 3 (отрезок 1 3 5)
  • Урок 12.12.2011
    • ДЗ
      • Задание на 3
        • Построить график времени работы пузырьковой сортировки от размера входного массива
        • На графике должно быть не менее 100 точек
        • Максимальный размер входного массива должен быть не менее 100 000 элементов
      • Задание на 4
        • Построить график времени работы сортировки слиянием (MergeSort) от размера входного массива
          • для массивов чисел
          • для массивов строк не длиннее 30 символов (слов из текста романа "Анна Каренина")
      • Задание на 5
        • Построить график времени работы быстрой сортировки 
          • выбирая первый элемент в качестве барьерного
          • выбирая случайный элемент в качестве барьерного
  • Урок 05.12.2011
    • Для проверки задания по подсчету различных слов в романе Л. Н. Толстого "Анна Каренина", выведите на экран следующие показатели
      • Total forms — общее количество форм слов, порожденных из полного словаря
      • Word count — сколько слов (включая повторы) обнаружено в тексте романа "Анна Каренина"
      • Different words — сколько различных слов обнаружено
      • Not found — сколько слов не найдено в словаре (включая повторы)
    • Необходимо также предявить текстовый файл со словами, которые не найдены в словаре
       
  • Урок 21.11.2011
    • Для проверки задания "Оглавление для массива аффиксов" выведите
      • Affix count: Общее количество аффиксов в базе
      • Key count: Общее количество ключей в базе аффиксов
      • Absent keys: Ключи, не встречающиеся в базе
    • Для проверки задания "Построение словаря всех форма слов" выведите
      • Word count: Количество слов в исходном словаре
      • Form count: Количество получившихся форм слов (повторения исключать не нужно)
      • Longest word: Длину самого длинного слова в исходном словаре и само это слово
      • Longest form: Длину самого длинного слова в словаре всех форм и само это слово
      • Max keys: Самое большое количество ключей у слова в исходном словаре
    • Для проверки задания "Определение начальной формы слова" выведите
      • Record count: Количество записей в полученном файле
        • FileSize(f)
      • File size: Размер полученного файла в БАЙТАХ
        • FileSize(f) * SizeOf(тип записи)
    • ДЗ
      • Построить файл всех форм по полному словарю
      • Найти количество различных слов в данном варианте текста романа Л. Н. Толстого "Анна Каренина"
        • Различные слова определяются по следующем принципу: для каждого слова из текста по словарю находится его начальная форма, если слово с такой начальной формой еще не встречалось, счетчик увеличивается на единицу
        • Все слова, которые не удалось найти в словаре, необходимо записать в отдельный файл
        • Отдельно необходим записать (на бумагу) их количество

 

  • Урок 14.11.2011
    • Построение оглавления для массива аффиксов
      • Дан файл аффиксов
      • Аффиксы в нем сгруппированы по ключу (латинская буква после SFX)
      • Запишите все аффиксы из этого файла в массив
      • Создайте второй массив, индексами в котором являются латинские буквы, а значениями — место в первом массиве, где встречается первый аффикс с такой буквой
      • Используя построенный массив, реализуйте поиск всех аффиксов, подходящих для словарной строки (см. ниже)
    • Построение словаря всех форм слов по данному словарю small.dic
      • Для каждой словарной строки из словаря подберите все подходящие аффиксы
      • Напишите программу, применяющую все подходящие аффиксы ко всем словам и определяющую максимальную длину получившегося слова
    • Определение начальной формы слова по построенному словарю всех форм
      • Начальные формы слов и формы слов, полученные в результате применения всех подходящих аффиксов, запишите в файл записей следующего формата:
        • форма слова
        • номер записи в том же файле, в которой содержится начальная форма этого слова
      • Используя полученный файл, напишите программу, по данному слову определяющую, от каких начальных форм оно могло быть образовано
        • ВНИМАНИЕ: таких начальных форм может быть несколько
        • Например, слово "лечу" может быть как формой глагола "лечить", так и формой глагола "лететь"

 

  • Урок 07.11.2011
    • Определения: 
      • Формат аффиксной строки: SFX ключ суффикс_удалчить суффикс_добавить шаблон_строки
        • ключ — заглавная латинская буква
        • суффикс_удалить — одна или несколько строчных русских букв, или 0 (ноль), если имеется в виду пустая строка
        • суффикс_добавить — одна или несколько строчных русских букв, или 0 (ноль), если имеется в виду пустая строка
        • шаблон сроки — см. определение от 31.10.2011
        • Примеры
          • SFX G я е [^и]я
          • SFX K 0 м о
          • SFX L сть ла [^ч].сть
      • Формат словарной строки: слово/ключи
        • слово — одна русская буква (заглавная или строчная) или более 
        • ключи — одна заглавная латинская буква или более
        • Примеры
          • епитимья/G
          • упасть/LRY
      • Аффикс A подходит для словарной строки S, если и только если
        • ключ, указанный в A указан и в S
        • И
        • слово в S удовлетворяет шаблону строки, указанному в A
    • Задание
      • Оценки
        • Сдача 10.11.2011 — 5
        • 14.11.2011 — 4
        • Позже — 3
      1. Дана аффиксная строка, написать функцию ParseAffix(const s : String; var affix : TAffix) : Boolean (false — ошбика)
        • Создать текстовый файл с примерами всех видов правильных и неправильных аффиксных строк
        • Для каждой строки из файла вывести представление, где каждый элемент записи TAffix взят в круглые скобки или ERROR, если форма неправильный
      2. Дана словарная строка S и аффиксная строка A
        • Если A подходит S, удалить и добавить в S суффиксы, согласно указаниям в аффиксной строке
        • Если нет, вывести "NO MATCH"
        • Примеры
          • S = епитимья/G, A = SFX G я е [^и]я, Результат: епитимье
          • S = упасть/LRY, A = SFX L сть ла [^ч].сть, Результат: упала
          • S = упасть/LRY, A = SFX K 0 м о, Результат: NO MATCH
      3. Порождение всех словоформ
        • Дано
        • Найти в словаре словарную строку, соответствующую S
        • Для всех аффиксов из базы, подходящих этой строке
          • применить аффикс к S и вывести результат

 
 

  •  

 
Крестики-нолики 
Библиотека DelphiGraph

Комментарии