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

Материал из Викиконспекты
< Участник:Shersh
Версия от 23:30, 25 февраля 2016; Shersh (обсуждение | вклад) (→‎Пересечение матроидов)
Перейти к: навигация, поиск

Тикеты нумеруются как "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. Пояснить подробней псевдокод
    5. Взять кортежи в тех и оформить красиво
  8. Алгоритм Мейна-Лоренца

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

0. Поиск подстроки в строке

Точный поиск

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

Нечёткий поиск

  1. Алгоритм Ландау-Вишкина (k несовпадений)
  2. Алгоритм Ландау-Вишкина (k различий)

3. Суффиксное дерево

  1. Суффиксный бор
  2. взяли Сжатое суффиксное дерево (2)
    1. Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
    2. Англоязычные термины
    3. Сделать список нормальный в доказательстве
    4. Отформатировать псевдокод в построении
    5. Свойства написать с маленькой буквы и перечислить через запятую
    6. Добавить псевдокод структуры Vertex перед построением
  3. Алгоритм Укконена
  4. Алгоритм МакКрейта
  5. Алгоритм Фарача (2)
    1. В конспекте полно опечаток - исправить
    2. Интервики на поразрядную сортировку
    3. Рисунки подписать в thumb
    4. Добавить недостатки и преимущества

4. Суффиксный массив

  1. Суффиксный массив
  2. Построение суффиксного массива с помощью стандартных методов сортировки
  3. Алгоритм цифровой сортировки суффиксов циклической строки
  4. Алгоритм Касаи и др. (3)
    1. Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
    2. "будем использовать промежуточный массив " — лучше написать "вспомогательный"
    3. Добавить фразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты
    4. Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP
    5. Надо сказать, в каком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1
    6. Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех
  5. Алгоритм Карккайнена-Сандерса
  6. взяли Алгоритм поиска подстроки в строке с помощью суффиксного массива (7)
    1. Отформатировать псевдокоды
    2. Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
    3. Исправить баги в Tex
    4. Оформить правильно источники информации

5. Задача о наименьшем общем предке

  1. Сведение задачи LCA к задаче RMQ
  2. Сведение задачи RMQ к задаче LCA (2)
    1. Задачу взять в Шаблон
    2. Кинуть интервики на дерево по неявному
    3. Чуть подробней написать алгоритм, более плавное введение сделать
    4. Пункт "Доказательство" тоже немного не к месту выглядит, заменить его на что-нибудь получше
    5. В сложности тоже сказать больше подробностей
  3. Метод двоичного подъема
  4. Решение RMQ с помощью разреженной таблицы
  5. взяли Алгоритм Фарака-Колтона и Бендера (2)
    1. Отформатировать псевдокод
    2. Увеличить дроби
  6. взяли Алгоритм Шибера-Вишкина (3)
    1. Англоязычные термины
    2. Интервики на LCA
    3. Чё ещё за подготовка?
    4. Почему-то в определении находится не определение, надо бы нормально переписать
    5. Лучше дать нормальное название обхода: pre-order, in-order или post-, если что-то из этого оно и есть
    6. Увеличить дроби
    7. Добавить См. также
    8. Добавить Категории
    9. Правильно оформить источники информации
  7. Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
  8. взяли Link-Cut Tree (5)
    1. Отформатировать псевдокоды
    2. Написать более понятное введение и пояснить подробней остальные смутные операции
    3. Список оформлен некрасиво в начале
    4. Категории
    5. Оформить правильно См. также и Источники информации

6. Матроиды

Основные факты теории матроидов

  1. Определение матроида
  2. Примеры матроидов
  3. Прямая сумма матроидов
  4. Теорема Радо-Эдмондса (жадный алгоритм)
  5. Теорема о базах
  6. Аксиоматизация матроида базами
  7. Теорема о циклах
  8. Аксиоматизация матроида циклами
  9. Ранговая функция, полумодулярность
  10. Двойственный матроид
  11. Оператор замыкания для матроидов
  12. Покрытия, закрытые множества
  13. Матроид Вамоса

Пересечение матроидов

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

Объединение матроидов

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

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

  • Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно
  1. fixed Классификация задач (1)
    1. Тех в нотацию Грэхема
    2. Оформить правильно англоязычные термины
    3. Добавить источники информации, см. также, категории
  2. !!! [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math] (8)
    1. Начать с простейших примеров, когда только d_i, потом усложнять
    2. Отформатировать псевдокод
    3. Оформить правильно источники информации
    4. Добавить категории
  3. Методы решения задач теории расписаний (3)
    1. Как-нибудь структурировать конспект, а то много всего рандомного написано
    2. Ссылки оформить как интервики
    3. Оставить только совсем мелки доказательства, на наборы задач кинуть ссылки или создать новые конспекты
    4. Добавить источники информации
  4. fixed Правило Лаулера (3)
    1. Задачу в шаблон
    2. Отформатировать псевдокод
    3. Заменить дефисы на тире
    4. Заменить знаки неравенств
    5. Добавить "информации" в источники
  5. [math]1 \mid \mid \sum U_{i}[/math] (1.5)
    1. Задачу в шаблон
    2. Отформатировать псевдокод
    3. Добавить категории
    4. Заменить литературу на источники информации
  6. fixed [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math] (4)
    1. Задачу в шаблон
    2. Рассмотреть более простые варианты задачи для начала
    3. Отформатировать псевдокод
    4. Добавить источники
  7. [math]1 \mid outtree \mid \sum w_i C_i[/math]
  8. [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math] (3)
    1. Более простой аналог задачи рассмотреть (только с U_i)
    2. Отформатировать псевдокод
    3. Заменить литературу на источники информации
  9. [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math] (7)
    1. Задачу в шаблон
    2. Отформатировать псевдокоды
    3. Более подробное и понятное описание, чтобы было понятно, как закодить
    4. Увеличить дроби
  10. fixed [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math] (1)
    1. Задачу в шаблон
    2. Заменить знаки неравенств
    3. Добавить источники информации
  11. [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math] (0.5)
    1. Увеличить дроби
    2. Оформить правильно источники информации
    3. Добавить категории
    4. Заменить знаки неравенств
  12. fixed [math]P \mid pmtn, r_i \mid L_{max}[/math] (0.5)
    1. Заменить знаки неравенств
    2. Добавить категории
  13. [math]Q \mid pmtn \mid C_{max}[/math] (2)
    1. Задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить знаки неравенств
    4. Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
  14. [math]Q \mid pmtn, r_{i} \mid L_{max}[/math] (0.5)
    1. Задачу в шаблон
    2. Заменить знаки неравенств
    3. Добавить информации в источники
  15. fixed [math]Q\mid\mid\sum{C_i}[/math] (1)
    1. Там получаются очень большие списки, если рассматривать их все для каждого станка, нужно написать, как лучше всего организовать очередь приоритетов
    2. Увеличить дроби
    3. Задачу в шаблон
    4. Оформить правильно Источники инфорации
  16. !!! [math]R2 \mid \mid C_{max}[/math] (5)
    1. Допилить
    2. Доказать корректность
    3. Задачу в шаблон
    4. Отформатировать псевдокод
    5. Добавить категории
  17. Flow shop (2)
    1. Таблички оформить как викитаблички, а не как код
    2. Битое примечание
    3. Отформатировать псевдокоды
    4. Добавить категории
  18. [math]F2 \mid \mid C_{max}[/math] (3)
    1. Задачу в шаблон
    2. Заменить знаки неравенств
    3. Отформатировать псевдокод
    4. Красивые картинки
  19. fixed [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math] (1)
    1. Ранее было доказано, что эта задача сводится к 1|p_ij=1|sumwiUi, поэтому надо просто выпилить отсюда значимую часть и перенести примером в Flow shop
  20. [math]O2 \mid \mid C_{max}[/math] (1)
    1. Заменить знаки неравенств
    2. Категории
    3. задачу в шаблон
    4. Отформатировать псевдокод
  21. [math]O \mid p_{ij} = 1 \mid \sum U_i[/math] (0.5)
    1. Категории
    2. Шаблон
    3. Знаки неравенств
  22. [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math] (1)
    1. Задачу в шаблон
    2. Знаки неравенств
    3. Источники информации
    4. Дефисы на тире
  23. !!! [math]J2\mid p_{ij} = 1\mid L_{max}[/math] (10)
    1. Доделать
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_4ому_терму&oldid=52210»