Course 1:

Design of Efficient String Algorithms
Эффективные алгоритмы для работы со строками

Directors:
Prof. E. A. Hirsch (PDMI) and Prof. Dr. E. W. Mayr (TU Munich)

Assistants:
Alexander Kulikov (PDMI) and Johannes Krugel (TU Munich)

March 18 — 24, 2012, St. Petersburg, Russia

Описание курса:

Курс посвящен построению и анализу эффективных алгоритмов для работы со строками.
Алгоритмы на строках — интереснейшая область computer science на стыке теории и практики: известно много элегантных и нетривиальных строковых алгоритмов, имеющих в том числе и большое прикладное значение (для поисковых систем, вычислительной биологии и т.д.).

В курсе будут рассмотрены алгоритмы и структуры данных, позволяющие эффективно решать задачи, возникающие повсеместно в практических приложениях, например, проверка вхождения одного или нескольких паттернов в текст или нахождение оптимального выравнивания последовательностей.
Планируется подробно изучить суффиксные деревья и суффиксные массивы, преобразование Барроуза-Уилера, FM-индекс и другие.
Чтобы составить общее впечатление о курсе, можно посмотреть страницу предыдущей версии курса; в этом году, однако, будут существенные изменения.

Предварительная программа:

• Knuth-Morris-Pratt, Boyer-Moore [Gusfield chapter 2]
• Aho-Corasick [Gusfield chapter 3]
• Edit distance and sequence alignment [Gusfield chapters 10+11]
• Edit distance: bit parallel algorithm [Myers 1999]
• Suffix trees: data structure and construction [Gusfield chapters 5+6]
• Suffix trees: applications [Gusfield chapters 7+9]
• Suffix trees: construction in secondary memory [Barsky et al. 2010]
• Suffix arrays: efficient construction [Kärkkäinen, Sanders 2006]
• Enhanced suffix arrays [Abouelhoda et al. 2004]
• Burrows-Wheeler transform [Burrows, Wheeler 1994]
• Compressed suffix arrays: FM-index [Ferragina, Manzini 2000]
• q-gram indexes and space saving methods [Behm et al. 2009]
• Approximate text indexing (hybrid) [Navarro, Baeza-Yates 2000]

Другой курс этой же школы:

В рамках JASS-2012 будет также проводиться курс "Usability Engineering & Ubiquitous Computing on mobile devices", который может быть интересен кому-то из Ваших коллег.

Предыдущие курсы JASS по теоретической информатике:

(С презентациями и фотографиями участников!)

• Propositional Proof Complexity (2009),
• Trees - The Ubiquitous Structure in Computer Science and Mathematics (2008),
• Polynomials: Their Power and How to Use Them (2007),
• Proofs and Computers (2006),
• Algorithms for IT Security (2005),
• Complexity Analysis of String Algorithms (2004),
• Graph Algorithms (2003).

Информация для российских участников:

Студенты, специализирующиеся в области информатики, математики или программирования, приглашаются принять участие в 8-й русско-немецкой школе JASS
в курсе "Design of Efficient String Algorithms". Необходимым условием является начальная подготовка в области информатики и дискретной математики, позволяющая строить алгоритмы и анализировать их сложность. Участие в школе дает возможность заниматься изучением современной теоретической информатики под руководством действующих ученых, практиковаться в общении на английском языке, знакомиться и общаться с немецкими студентами.

Желающим принять участие в курсе необходимо отправить заявку Эдуарду Алексеевичу Гиршу по адресу hirsch "at" pdmi.ras.ru (и убедиться в том, что она дошла! если в течение суток ответа не получено — значит, не дошла), указав в ней следующие сведения:

• Фамилия, имя, отчество.
  
• ВУЗ, курс, группа, кафедра.
  
• E-mail(ы).
  
• Контактный телефон.
  
• ФИО научного руководителя (если есть) и название(-я) курсовых работ.
  
• Список прослушанных вами курсов по математике и информатике (указать, где Вы эти курсы слушали).
  
• Область научных интересов.
  
• Список публикаций (если есть).
  

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

Рабочий язык школы: английский

Приём заявок окончен.

Окончательный состав участников будет определён 29 февраля 2012 г.

Даты школы: 18—24 марта 2012 г.

Контакты: Все вопросы задавайте по электронной почте hirsch "at" pdmi.ras.ru