Вопросы, ответы на которые представляют собой большой список предметов (книги, теоремы, программное обеспечение, ...)
Со времени выхода книги Криса Окасаки «Чисто функциональные структуры данных» 1998 года я не видел слишком много новых интересных чисто функциональных структур данных; Я могу назвать только несколько: IntMap (также изобретен Окасаки в 1998 году, но не представлен в этой книге) Пальцевые деревья (и...
Этот вопрос (вдохновленный) / (позорно украденный) похож на вопрос в MathOverflow , но я ожидаю, что ответы здесь будут совсем другими. У всех нас есть любимые статьи в наших соответствующих областях теории. Время от времени каждый находит бумагу настолько поразительной (например, важной,...
Пол Эрдос говорил о «Книге», где Бог хранит самое элегантное доказательство каждой математической теоремы. Это даже вдохновило книгу (которая, я думаю, теперь в ее 4-м издании): Доказательства из Книги . Если бы у Бога была подобная книга для алгоритмов, какой алгоритм (ы), как вы думаете, был бы...
[ Хронология ] Этот вопрос имеет тот же дух, что и газеты должны читать все, и какие видео должны смотреть все . Он просит замечательных книг в различных областях теоретической информатики. Книги могут быть ориентированы на математику, но вы можете найти это замечательно для компьютерного ученого....
Википедия перечислены только две проблемы под «нерешенных проблем в области информатики» : P = NP? Существование односторонних функций Какие еще основные проблемы следует добавить в этот список? Правила: Только одна проблема в ответе Предоставьте краткое описание и любые соответствующие ссылки...
У Стэнфордского университета теперь есть канал на Youtube с бесплатным доступом к HD-видео с полным курсом по всем вопросам, от динамических систем до квантовой запутанности. Больше конференций и семинаров снимают на видео свои выступления. Какие видео онлайн, о которых вы думаете, все должны...
Факторинг и изоморфизм графов - это проблемы в NP, которые, как известно, не находятся в P и не являются NP-полными. Каковы некоторые другие (достаточно разные) естественные проблемы, которые разделяют это свойство? Искусственные примеры, полученные непосредственно из доказательства теоремы...
Там было несколько вопросов с той же схемой, что и этот: Какие документы должен прочитать каждый Какие книги должен прочитать каждый Каковы последние книги TCS, проекты которых доступны онлайн какие видео должны смотреть все Я не хотел публиковать еще один, но конспект лекций Джеффа Эриксона об...
Теоретическая информатика предоставила несколько примеров «цены абстракции». Два самых выдающихся из них - это устранение и сортировка по Гауссу. А именно: Известно, что исключение Гаусса является оптимальным для, скажем, вычисления определителя, если вы ограничиваете операции строками и столбцами...
После публикации « Что должны читать все книги» я заметил, что есть недавние книги, черновики которых доступны в Интернете. Например, в статье « Алгоритмы аппроксимации» вышеприведенного поста цитируется книга 2011 года (еще не опубликованная) под названием «Разработка алгоритмов аппроксимации» . Я...
Я хотел бы попросить помощи в составлении списка как можно большего количества конференций и семинаров, связанных с TCS. Моя главная мотивация для этого состоит в том, чтобы планировать возможное освещение в блоге более теоретических мест - поиск корреспондентов, посещающих эти мероприятия, которые...
Какая самая смешная опубликованная работа, связанная с TCS, вы знаете? Пожалуйста, включайте только те, которые предназначены для забавы. Работы, которые явно созданы для того, чтобы быть разумно юмористическими (а не, скажем, опубликованным сборником коротких анекдотов о теории сложности),...
Пожалуйста, перечислите примеры, где теорема из математики, которая обычно не считалась применимой в информатике, была впервые использована для доказательства результата в информатике. Лучшими примерами являются те, где связь не была очевидной, но как только она была обнаружена, это, безусловно,...
Я практикующий программист, и я пишу обзор алгебраических структур для личного исследования и пытаюсь привести примеры того, как эти структуры используются в теоретической информатике (и, в меньшей степени, в других областях компьютерных наук). , В рамках теории групп я встречал синтаксические...
Какие алгоритмы законной полезности просто слишком сложны для реализации? Позвольте мне прояснить: я не ищу алгоритмы, такие как текущий асимптотический алгоритм оптимального умножения матриц (Coppersmith-Winograd), который разумно реализовать, но имеет константу, которая делает его бесполезным на...
Исходя из более математического фона, я так и не научился писать код. Я начинаю докторскую диссертацию в TCS, и многие были удивлены тем, как мало я знал о программировании (и о компьютере в целом). Я могу писать алгоритмы в псевдокоде, но я не знаю языка программирования. Я могу себе представить,...
Обновлено ниже Мы все знаем о критической важности рецензирования. Это основная форма контроля качества и обратной связи по исследованиям. Однако, для исследователя ранней стадии (такого как я) иногда это может быть запутанной системой / процессом. Соответственно, есть несколько трактатов по...
РЕДАКТИРОВАТЬ НА 10/12/08: Я постараюсь изменить вопрос, чтобы он мог заинтересовать больше людей поделиться своим мнением. Нам нужен ваш вклад! Этот пост вдохновлен тем, что в МО: Примеры распространенных ложных убеждений в математике . Большие списки иногда генерируют огромное количество ответов,...
Часто, когда мы принимаем участие в конференциях TCS, мы замечаем некоторые мелкие детали, о которых мы хотим, чтобы организаторы конференции позаботились. И когда мы организуем конференции, мы уже забыли это. Отсюда вопрос: какие небольшие шаги мы могли бы легко предпринять для улучшения...
Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...