- Общие вопросы информатики/алгоритмики
- А. В. Анисимов.
Преобразователи Черча-Россера и разрешимые свойства обработки деревьев (доклад).
Институт систем информатики Сибирского отделения АН СССР.
(
)
- A. V. Anisimov.
Group languages.
(Оригинал на русском языке не доступен. / «Кибернетика», №4, Стр. 18-24, июль-август, 1971 г.)
Cybernetics, Springer, 1971.
(
)
- A. V. Anisimov.
Some algorithmic problems for groups and context-free languages.
(Оригинал на русском языке не доступен. / «Кибернетика», №2, Стр. 4-11, март-апрель, 1972 г.)
Cybernetics, Springer, 1972.
(
)
- Л. Д. Беклемишев, Ю. В. Матиясевич (организаторы).
Традиционная новогодняя сессия МИАН-ПОМИ, «Логика и теоретическая информатика» (доклады).
Математический институт им. В. А. Стеклова РАН,
16–18 декабря 2009 г., г. Москва.
(
)
- J. Bentley.
Programming Pearls, Second Edition.
Addison-Wesley, Inc., 2000.
(
)
- Н. К. Верещагин, А. Шень. Вычислимые функции. Издание второе, исправленное. Москва, МЦМНО, 2002. (zipped pdf, 0.9 Mb)
- Э. А. Гирш. Фрагменты конспектов лекций по информатике (черновики). Санкт-Петербургский государственный университет. Математико-механического факультет, поток математиков, 1 курс. 2002/03 уч. г.
- Э. А. Гирш. Фрагменты конспектов лекций по информатике (черновики). Санкт-Петербургский государственный университет. Математико-механического факультет, поток информатики, 1 курс. 2003/04 уч. г.
- Э. А. Гирш. Фрагменты конспектов лекций по информатике (черновики). Санкт-Петербургский государственный университет. Математико-механического факультет, поток информатики, 1 курс. 2005/06 уч. г.
- Э. А. Гирш. Фрагменты конспектов лекций по информатике (черновики). Санкт-Петербургский государственный университет. Математико-механического факультет, поток информатики, 1 курс. 2005/06 уч. г.
- Человек и Пароход. Книги и курсы по CS и смежным областям. WordPress.com.
- А. М. Шур. Комбинаторика слов (учебное пособие). Уральский государственный университет, 2003 г.
- D. Gusfield.
Algorithms on Strings, Trees, and Sequences. 2007.
Computer Science and Computational Biology Cambridge University Press, 1997.
(
, постраничный просмотр)
- Leonid A. Levin.
Fundamentals of Computing.
(
html
),
(
)
- M. Lothaire.
Combinatorics on Words.
Encyclopedia of Mathematics, Vol. 17, Addison-Wesley, 1983.
(
)
- M. Lothaire et al.
Algebraic Combinatorics on Words.
Cambridge University Press, 2002. ISBN: 0521812208
(
)
- I. Lysenok, A. Miasnikov, and A. Ushakov
Quadratic Equations in the Grigorchuk Group.
/ Groups Geom. Dyn., Vol. 10, Issue 1, pp: 201–239, 2016.
arXiv:1304.5579
(
)
- M. Lothaire et al.
Applied Algebraic Combinatorics on Words.
Cambridge University Press, 2005. ISBN: 0521812208
(
)
- Ю. И. Манин.
Ренормализация и теория вычислимости.
Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН,
25 мая 2009 г. 13:00, г. Санкт-Петербург, ПОМИ
(
)
- Yuri I. Manin.
Renormalization and computation I: motivation and background.
arXiv:0904.4921, 2009.
(
)
- Yuri I. Manin.
Renormalization and Computation II: Time Cut-off and the Halting Problem.
arXiv:0908.3430, 2009.
(
)
- И. А. Михайлова.
Об индексах избегаемости палиндромов.
/ Матем. заметки, 93:4 (2013), Стр. 634-636, 2013.
(
)
- Лаборатория комбинаторных и геометрических структур.
Комбинаторика и дискретная геометрия в МФТИ.
/ МФТИ, 2021.
(
, см. также
,
,
)
- А. В. Анисимов.
Преобразователи Черча-Россера и разрешимые свойства обработки деревьев (доклад).
Институт систем информатики Сибирского отделения АН СССР.
(
- Теория сложности вычислений
- Н. К. Верещагин.
Коммуникационная сложность (спецкурс).
Computer Science клуб при ПОМИ РАН, 2009 г., г. Санкт-Петербург.
(
)
- Н. К. Верещагин.
Конспект лекций о сложности вычислений в среднем (спецкурс).
Московский государственный университет. Механико-математический факультет.
2009 г.
(
)
- Э. А. Гирш. Введение в структурную теорию сложности (спецкурс). Санкт-Петербургский государственный университет. Математико-механический факультет. 2002, 2004, 2006 гг.
- Э. А. Гирш. Структурная теория сложности (спецкурс). Санкт-Петербургский государственный университет. Математико-механического факультет. 2003, 2005 гг.
- Э. А. Гирш. Сложностная криптография (спецкурс). Санкт-Петербургский государственный университет. Математико-механического факультет. 2007, 2008 гг.
- Э. А. Гирш. Эффективные алгоритмы (спецкурс). Санкт-Петербургский государственный университет. Математико-механического факультет. 2001 г.
- Э. А. Гирш. Эффективные алгоритмы (спецкурс). Санкт-Петербургский государственный университет. Математико-механического факультет. 2003/2004 уч. г.
- Э. А. Гирш. Теория сложности доказательств (лекции). Санкт-Петербургский Computer Science клуб. 2010 г.
- А. С. Куликов.
Схемная сложность явно заданных булевых функций.
Диссертация на соискание ученой степени д.ф-м.н.
Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН, Санкт-Петербург,
2016, 143 стр.
(
)
- С. С. Марченков, В. Л. Матросов.
Сложность алгоритмов и вычислений.
Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет., том 16, ВИНИТИ, М., 1979, 103–149.
(
, 3.2 Mb)
- В. В. Подольский, А. Е. Ромащенко.
Введение в коммуникационную сложность (конспект лекций).
Мехмат МГУ, весенний семестр, 2012.
(
)
- А. А. Разборов.
Теория сложности вычислений (курс лекций).
Летняя школа «Современная математика», июль 2011, г. Дубна.
(
)
- А. Станкевич. Теория сложности. Викиконспекты НИУ ИТМО «Современная математика», июль 2011, г. Дубна. ( html )
- S. Arora, B. Barak.
Computational Complexity: A Modern Approach.
Cambridge University Press, 2009.
(A draft is available at
)
- R. O'Donnell.
A history of the PCP Theorem.
(
)
- N. D. Jones.
Computability and Complexity from a Programming Perspective, 2007.
A revised version of the book published by the MIT Press, 1997, p. 485.
(
, 1.9 Mb)
- J. Katz.
Notes on Complexity Theory.
2011.
(
)
- D. Moshkovitz. Probabilistically Checkable Proofs and Hardness of Approximation. (Course notes) 2011. ( html )
- Н. К. Верещагин.
Коммуникационная сложность (спецкурс).
Computer Science клуб при ПОМИ РАН, 2009 г., г. Санкт-Петербург.
(
- Теория колмогоровской сложности
- В. А. Успенский, Н. К. Верещагин, А. Шень.
Колмогоровская сложность.
412 с.
(
, 1.9 Mb)
- В. В. Вьюгин.
Колмогоровская сложность и алгоритмическая случайность.
2012, МФТИ, г. Москва, 132 с.
(
)
- Paul M.B. Vitanyi.
Logical depth for reversible Turing machines
with an application to the rate of decrease in logical depth for general Turing machines.
2019.
(
)
- Ю. И. Манин.
Сложность как энергия: применение к закону Ципфа.
Конференция «Столетие И.М. Гельфанда», 22-24 июля, 2009, г. Москва.
(
)
- Yuri I. Manin.
Complexity vs Energy: Theory of Computation and Theoretical Physics.
arXiv:1302.6695, 27 Feb, 2013.
(
)
- Yuri I. Manin and M. Marcolli.
M. Kolmogorov Complexity and the Asymptotic Bound for Error-correcting Codes.
arXiv:1203.0653, (Submitted on 3 Mar 2012 (v1), last revised 17 Dec 2012 (this version, v2)).
(
)
- Ю. И. Манин.
Коды, исправляющие ошибки, и фазовые переходы.
Математическая лаборатория имени П.Л.Чебышева, 24 мая, 2012, г. Санкт-Петербург.
(
)
- В. И. Арнольд.
Сложности конечных последовательностей нулей и единиц.
«Заседания Московского математического общества», 22 ноября, 2005, МГУ, г. Москва.
(
)
- В. И. Арнольд. Сложности конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств. Научно-популярная лекция в фонде «Династия», 13 мая, 2006, г. Москва. ( )
- А. И. Гарбер.
Графы линейных операторов.
Геометрия, топология и математическая физика - I.
Сборник статей. «К 70-летию со дня рождения академика С. П. Новикова»,
Тр. МИАН, 263, МАИК "Наука/Интерпериодика", М., 2008, 64-71.
(
)
- O. N. Karpenkov.
On examples of difference operators for {0, 1}-valued functions over finite sets.
Funct. Anal. and Other Math. 2006. V. 1, N 2. pp. 175-180.
(
)
- В. А. Успенский, Н. К. Верещагин, А. Шень.
Колмогоровская сложность.
412 с.
(