Участник:Shersh/Тикеты к 4ому терму

Материал из Викиконспекты
< Участник:Shersh
Версия от 18:30, 22 января 2015; Shersh (обсуждение | вклад) (→‎2. Поиск подстроки в строке (проверяется))
Перейти к: навигация, поиск

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

Помним про добавление англоязычных терминов в конспекты.

1. Основные определения. Простые комбинаторные свойства слов

  1. Основные определения, связанные со строками
  2. Период и бордер, их связь
  3. !!! Слово Фибоначчи (7)
    1. Убрать лишние пункты
    2. Англоязычные термины
    3. Все переменные в Tex
    4. Исправить знаки неравенств
    5. Правильно оформить См. также и Источники информации
    6. Написать, почему строка Фибоначчи будет (2, 4) исключением
    7. Можно написать про исключения отдельный конспект даже, если там много информации наберётся
  4. !!! Слово Туэ-Морса (7)
    1. Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
    2. Англоязычные термины
    3. Правильно оформить См. также и Источники информации
    4. Доказать разные прикольные факты про строку Туэ-Морса (+3 за факт)
  5. Декомпозиция Линдона
  6. Алгоритм Ландау-Шмидта
  7. !!! Алгоритм Крочемора (5)
    1. Пояснить наивную реализацию в начале
    2. Доказать первую лемму
    3. Удалить Лоренца из источников
    4. Пояснить подробней псевдокод

2. Поиск подстроки в строке (проверяется)

0. Поиск подстроки в строке (1)
  1. Взять обозначения перед псевдокодом в \mathtt
  2. Придумать более удачный способ нумерации списка
  1. Наивный алгоритм поиска подстроки в строке (0.5)
    1. Задачу взять в Шаблон:Задача
    2. Заменить литературу на источники информации
    3. Сделать подпункты уровнем меньше
    4. Убрать среднее O во времени работы
  2. !!! Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа (5)
    1. Добавить подробное объяснение примера строки, на которой плохо работает такое хеширование
    2. Отформатировать псевдокод
    3. Добавить См. также
    4. Оформить правильно Источники информации
    5. Взять хэш в \mathrm
  3. Поиск наибольшей общей подстроки двух строк с использованием хеширования (0.5)
    1. Задачу взять в шаблон
    2. Переменные взять в Tex
    3. Отформатировать псевдокод
    4. Оформить правильно См. также и Источники информации
  4. Префикс-функция
  5. Алгоритм Кнута-Морриса-Пратта
  6. Алгоритм Бойера-Мура (4)
    1. Добавить понятную табличку примера с пояснением каждого шага
    2. and в Tex заменить на знак конъюнкции
    3. Добавить пояснений в формальные определения
    4. Ссылки заменить на источники информации
  7. Алгоритм Колусси
  8. Z-функция (1)
    1. Пункт определение не нужен, заменить на шаблон и дать формальное определение
    2. Оформить красиво доказательство эффективного алгоритма
    3. Добавить См. также
    4. Длинные обозначения после псевдокода взять в \mathtt
  9. !!! Автомат для поиска образца в тексте (10)
    1. Дописать до нормальной статьи о суффиксном автомате (если это оно и есть), см. список предлагаемых тем
  10. !!! Бор (8)
    1. Больше ссылок
    2. Кое-где надо подправить tex
    3. Нарисовать нормальные картинки
    4. Построение оформить эстетично по шагам
    5. Добавить ссылки на суффиксный бор, провести связь с суффиксным деревом
    6. Добавить информацию про использование дерева для хранения переходов
    7. Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
    8. Добавить см. также, оформить правильно источники информации
  11. !!! Алгоритм Ахо-Корасик (8)
    1. Написать асимптотику нормально
    2. Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
    3. Красивые картинки
    4. Отформатировать псевдокод
    5. Источники заменить на источники информации
    6. Отформатировать раздел с масками
  12. Алгоритм Ландау-Вишкина (k несовпадений)

3. Суффиксное дерево (проверяется)

  1. Суффиксный бор
  2. Сжатое суффиксное дерево
  3. взяли Алгоритм Укконена
    1. Дописать нормальный псевдокод
    2. Сделать понятное и нормальное описание
    3. Подстроку переписать как [math] s[i..j] [/math]
    4. Константы и переменные взять в tex
    5. Пробелы перед скобками в тексте
    6. Интервики на леммы
    7. В Cм. также добавить два других алгоритма построения суффиксных деревьев
    8. Добавить ссылок в источники, оформить нормально

4. Суффиксный массив (проверяется)

  1. Суффиксный массив
  2. Построение суффиксного массива с помощью стандартных методов сортировки
  3. !!! Алгоритм цифровой сортировки суффиксов циклической строки
    1. Добавить ссылку на цифровую сортировку куда-нибудь в конспект
    2. Заменить картинку таблицы на теховскую таблицу
    3. Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
    4. Возможно придётся чуточку переписать описание алгоритма
  4. взяли Алгоритм Касаи и др.
    1. Добавить псевдокод
    2. Заменить Источники на Источники информации
    3. Исправить знаки неравенств
    4. Переход в последней теореме оформить на отдельной строке, чтобы пояснение не путалось в формуле
  5. Алгоритм Карккайнена-Сандерса
  6. !!! Алгоритм поиска подстроки в строке с помощью суффиксного массива
    1. Отформатировать псевдокоды
    2. Разобраться в алгоритмах и написать нормальное описание: там встречаются баги

5. Задача о наименьшем общем предке (проверяется)

  1. fixed Метод двоичного подъема
    1. Поправить ужасный псевдокод
  2. Сведение задачи LCA к задаче RMQ
  3. Решение RMQ с помощью разреженной таблицы
  4. !!! Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
    1. Добавить оптимизацию по памяти
    2. Написать псевдокод
    3. Добавить сведение задачи RMQ к задаче +/-1 RMQ
  5. Алгоритм Шибера-Вишкина
  6. Сведение задачи RMQ к задаче LCA

6. Матроиды (проверяются)

  1. fixed Определение матроида
    1. Англоязычные термины
    2. Поправить источники информации
    3. Заменить тире на Шаблон:---
  2. fixed Примеры матроидов
    1. Англоязычные термины
    2. Добавить ссылок, см. также
    3. Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)
    4. Длинные слова взять в \mathrm
    5. Добавить интервики
    6. Добавить примеры матроидов из дз как определения
    7. Добавить примеры матроидов отсюда (ещё про бинарные) с доказательствами (может набраться на [math] 10 [/math] баллов в итоге, если всё сделать очень хорошо)
  3. fixed Прямая сумма матроидов
    1. Добавить в определение слова "прямая сумма"
    2. Добавить ссылки, см. также, интервики
    3. Пример разложения в прямую сумму (можно из дз)
  4. fixed Теорема Радо-Эдмондса (жадный алгоритм)
    1. Объединить со следующим конспектом
    2. Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна
    3. Ссылки, tex
  5. взяли Жадный алгоритм поиска базы минимального веса
    1. Добавить разных ссылок
    2. Мутное описание алгоритма
    3. Криво написана асимптотика
    4. Больше интервики
  6. !!! Теорема о базах
    1. Англоязычные термины
    2. Добавить ссылок, см. также
    3. Поправить tex
    4. Обернуть семейство в \mathcal
    5. Добавить сильную теорему баз (base exchange) — см. Chandra Chekuri
  7. Аксиоматизация матроида базами
    1. Больше ссылок
  8. fixed Теорема о циклах
    1. Поправить tex
    2. Заменить Ccl на \mathfrak{C}
    3. Добавить ссылок
    4. Англоязычные термины
  9. Аксиоматизация матроида циклами
  10. Ранговая функция, полумодулярность
    1. tex
    2. Ссылки
    3. Англоязычные термины
  11. fixed Двойственный матроид
    1. Множество через фигурные скобки написать в определении
    2. Англоязычные термины к определениям
    3. Маркированный и нумерованный списки смотрятся ужасно вместе
    4. Тире заменить на шаблон
    5. Добавить ссылок и интервики
    6. Расписать неочевидный переход про единственность цикла в расширенной базе
  12. fixed Оператор замыкания для матроидов
    1. Тире
    2. Больше ссылок

7.Пересечение матроидов (проверяется)

  1. !!! Пересечение матроидов, определение, примеры
    1. Ссылки
    2. tex
    3. Ещё примеров
    4. Больше общих описаний
    5. Пример, когда пересечение матроидов не является матроидом
    6. Доказательство матроидности уже приведённых примеров
  2. !!! Лемма о паросочетании в графе замен
    1. Док-во по индукции оформить красиво
    2. Исправить док-во: неверный переход
    3. Заменить xor на треугольник
  3. fixed Лемма о единственном паросочетании в графе замен
    1. Константы в tex
    2. Убрать сокращения
    3. Добавить интервики
  4. !!! Граф замен для двух матроидов
    1. Нарисовать нормальную картинку
    2. Добавить информацию про граф замен для одного матроида
    3. Исправить ссылки в соответствующих конспектах
    4. Создать новый конспект, в него сделать перенаправление из текущего
  5. Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
    1. Картинки плывут — разместить нормально
    2. Заменить обозначение графа замен на принятое
    3. Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
  6. !!! Алгоритм построения базы в пересечении матроидов
    1. Матроиды записать через угловые скобки
    2. Заменить тире на шаблон
    3. Добавить категории
    4. Отформатировать псевдокод
    5. Мелкие правки в tex
    6. Перерисовать картинку
    7. Помёрджить со следующим конспектом
  7. Теорема Эдмондса-Лоулера
    1. Добавить категории
    2. Заменить знак симметрической разности, а так же другие мелкие правки в tex
    3. Картинки кривовато расположены — поправить
    4. Исправить ошибки в док-ве

8. Объединение матроидов (проверяется)

  1. !!! Объединение матроидов, проверка множества на независимость
    1. Добавить формальное определение
    2. Структурировать конспект, а не оставлять просто набором тезисов
    3. Добавить категории
    4. Добавить ссылок
    5. Избавиться от сокращений
    6. Добавить содержательный примеры
    7. Заменить тире на Шаблон:---
    8. Помёрджить со следующим конспектом
  2. Объединение матроидов, доказательство того, что объединение является матроидом
    1. Добавить категории
    2. Добавить интервики
  3. !!! Алгоритм построения базы в объединении матроидов
    1. В определение само определение выделить жирным
    2. Тире заменить на Шаблон:---
    3. Добавить категории
    4. Добавить псевдокод
    5. Написать более подробное описание алгоритма поиска базы в объединении

9. Теория расписаний (проверяется)

  1. Классификация задач
  2. Методы решения задач теории расписаний
  3. Правило Лаулера
  4. Flow shop
  5. [math]1 \mid \mid \sum U_{i}[/math]
  6. [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math]
  7. [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math]
  8. [math]1 \mid outtree \mid \sum w_i C_i[/math]
  9. [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math]
  10. [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math]
  11. [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]
  12. [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math]
  13. [math]P \mid pmtn, r_i \mid L_{max}[/math]
  14. [math]Q \mid pmtn \mid C_{max}[/math]
  15. [math]Q \mid pmtn, r_{i} \mid L_{max}[/math]
  16. [math]Q\mid\mid\sum{C_i}[/math]
  17. [math]R2 \mid \mid C_{max}[/math]
  18. [math]F2 \mid \mid C_{max}[/math]
  19. [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math]
  20. [math]O2 \mid \mid C_{max}[/math]
  21. [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
  22. [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math]
  23. [math]J2\mid p_{ij} = 1\mid L_{max}[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_4ому_терму&oldid=44766»