Что включает в себя исследования в области теоретической информатики?

Я пытаюсь понять, что связано с теоретическими компьютерными исследованиями. Что делают теоретические компьютерные ученые?

Я знаю, что значительное время затрачивается на преподавание, руководство аспирантами, подачу заявок на финансирование и выполнение обязанностей департамента. Отложив их в сторону, как вы проводите свое исследование? Какие основные виды деятельности вы обычно делаете? Я предполагаю, что вы читаете газеты, думаете, проводите встречи и пишете документы. Есть ли другие?

По темам

Есть разные типы вопросов, которые можно считать теоретической информатикой. Важное слово здесь - « теоретический » (поскольку у всех нас есть некоторое представление о том, с чем имеет дело информатика). Понимание слова теоретическое не так очевидно. Долгое время я понимал это как математическое, а не как «взлом». Я лучше учился у людей в лингвистике: теоретическийдля них явно не подразумевается математическое, но основано на теории, которая может быть несколько неформальной (хотя это может быть также и математическим), и представляет собой организованную совокупность знаний и концепций, которые структурируют понимание наблюдаемых явлений и, как мы надеемся, допускают некоторое дедуктивное и прогнозирующее использование полученных знаний. Это также уменьшает количество обучения и преподавания за счет уменьшения количества примитивных понятий, из которых можно вывести остальное.

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

Но я сомневаюсь, что есть четкие границы.

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

• одна область - это вычислимость , которая изучает, что можно вычислить и как это происходит в довольно абстрактном смысле: во многом то, что описано в ответе Суреша Венката.

• другая - это алгоритмическая система , которая находит эффективные средства для вычисления ответов на конкретные проблемы с конкретными ограничениями. Вычислимость является теоретическим контекстом для алгоритмики.

• семантика (из-за отсутствия лучшего названия) анализирует концептуальную организацию вычислительных задач и алгоритмов в понятиях более высокого уровня, чтобы разложить методы, которые оказались полезными и часто используются повторно, такие как концепция подпрограммы, структуры, модули, скрытие информации. Он включает в себя разработку математических инструментов, которые адекватно формализуют эти понятия, чтобы обеспечить рассуждение на высоком уровне (например, семантика Скотта). Это также касается того, как это выражается, то есть разделения и связи между синтаксисом и семантикой. Концепции языков программирования являются его частью (хотя языковой дизайн, вероятно, является практическим применением этих знаний). Сюда также может входить связь между теорией доказательств и теорией вычислений, а также современная роль систем типов.

• Еще одна тема, которая может развиться больше, чем до сих пор, - это связь между вычислениями и фундаментальной физикой. Например. Существует ли связь между пределами вычислений и свойствами физического мира, такими как физическая плотность информации или законы термодинамики. Квантовые вычисления могут немного улучшить наше вычислительное мастерство; можем ли мы надеяться на большее? Некоторые могут оспаривать, что это все еще TCS, хотя есть исследования TCS по гиперкомпьютерам .

Что касается конкретных мероприятий

Я пропускаю очевидные действия, требуемые академической жизнью. или научная жизнь в промышленности: преподавание, публикация, рецензирование статей, написание заявок на гранты, принятие академических обязанностей, управление людьми, консультирование студентов или политиков. Но даже тогда нет простого ответа на ваш вопрос. Здесь я просто делаю набросок нескольких аспектов, которые приходят на ум, но я уверен, что можно сказать гораздо больше. И я не уверен, что отвечаю вам. Некоторые из лучших ученых написали книги о своей работе, и это может дать вам подсказки о научной деятельности.

Теоретические исследования могут включать в себя множество вещей, в зависимости от ваших навыков и интересов, которые сильно различаются от ученого к ученому. Говорить об этом довольно сложно, поскольку каждый человек в большей степени воспринимает свою деятельность и интересы, чем другие. Для большинства исследований требуются широкие знания, поскольку интересные и действительно оригинальные результаты часто возникают из-за того, что что-то связано, или из-за переноса техники из одного (под) поля в другое, или из-за разных технических представлений об одной и той же проблеме. Поэтому важно учиться как можно глубже, и глубже. Помните, что, хотя у вас есть время и возможности для этого как студента или младшего преподавателя / ученого, оба будут сокращены позже из-за обязанностей и жизни в целом. Обучение тому, на чем вы не специализируетесь, может быть способом продолжать обучение.

Вид работы, которую выполняют люди, может сильно различаться, потому что люди, к счастью, очень разные, с большим разнообразием интересов и технических способностей, дополняя друг друга. Некоторые люди решают проблемы. Они смотрят на теоретические или практические вопросы, поднятые другими людьми или самими собой, и пытаются их решить, или приближаются к полному или частичному решению. Другие люди будут лучше структурировать существующие знания, связывать вещи, а затем находить новые вопросы. Оба необходимы.

Важно найти более простые доказательства технических результатов, или более простые представления теорий, или объединение концепций. Он обобщает результаты, уменьшает количество вещей, которые нужно изучить, подчеркивает основные идеи и, возможно, приносит новое понимание. Поскольку наше учебное время ограничено, прогресс возможен только тогда, когда мы объединяем знания.

Простым примером является изучение абстрактных семейств формальных языков. Когда теория языка впервые развилась, свойства замыкания при различных операциях были доказаны снова и снова для каждого семейства языков (обычный, контекстно-независимый, RE, ...) с применением специальных методов, зависящих от семейства. Затем оказалось, что эти свойства замыкания имели внутренние отношения независимо от рассматриваемых семейств, и они были изучены как таковые. Сегодня нам нужно проверить только несколько простых свойств замыкания для данного семейства, и мы получаем «бесплатно» целый набор других свойств.

Другим важным моментом является то, что нет такого четкого различия между теоретической, практической или экспериментальной работой, Хорошая теория может привести к внедрению систем, которые могут механизировать решение проблем. И для реализации такой системы потребуется хороший теоретик со смесью теоретической и практической работы, включая реализацию системы или проектирование языка. На ум приходит много примеров, таких как системы доказательства и / или синтеза программ, специализированный язык для синхронных параллельных систем, ограниченный алгоритмический язык, для которого можно систематически выводить вычислительную сложность. Мало того, что важно иметь возможность создавать такие практические системы, которые делают теоретические результаты более доступными и пригодными для использования, но для теоретика часто очень важно либо умело использовать эти системы, хотя бы для того, чтобы разгрузить менее творческие части его работать, или внести свой вклад в развитие и расширение этих систем.

Другой аспект заключается в возможности сравнить теоретические подходы путем практических экспериментов. Здесь проблема состоит в том, чтобы сравнить различные методы для достижения одной и той же цели. Сравнение реализаций часто бессмысленно, так как их эффективность часто зависит от языка программирования или навыков программирования разработчика. Но если все они могут быть выражены в общих теоретических рамках, то иногда можно сравнить их экспериментально в этих рамках. Здесь теория и практика поддерживают друг друга, как это часто бывает в науке. Чисто теоретический анализ не всегда легко достичь. Кроме того, экспериментальный анализ, если он хорошо проведен, может демонстрировать неожиданное поведение, которое может мотивировать лучший теоретический анализ.

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

Часто забывают две вещи: этику науки и объяснение людям. Оба необходимы, и трудно.

В каком-то смысле просмотр этого сайта даст вам ответы на некоторые вопросы теоретиков-компьютерщиков (на низком уровне). На очень высоком уровне теоретик-компьютерщик задает вопросы о математических основах вычислений:

• что мы можем вычислить?
• как мы можем вычислить это?
• Как быстро ?
• что происходит, когда у нас ограниченные ресурсы для вычислений?
• Каковы ограничения на то, что мы можем вычислить?

Начиная с этих вопросов, возникает множество других тем, затрагивающих области применения, математику, другие части информатики и так далее.

мне пришло в голову, что рассказы из первых рук могут быть полезны, но они кажутся немного редкими в CS (в отличие, например, от математики, биографических / мемуарных текстов и т. д.). Вот две ссылки на этот вопрос, которые могут быть полезны. они больше нацелены на студенческую жизнь аспирантов и ориентированы на КС, но большинство из них будут относиться к исследованиям на уровне профессоров (помимо преподавания, но также и для многих докторов наук). [и в некоторых отношениях профессора могут рассматриваться как постоянно / многократно пишущие множество «мини» диссертаций на соискание ученой степени (исследовательские работы) или, в некоторых случаях, «супер» диссертации (книги) о своей карьере). Есть также несколько достойных книг по тема, добавит некоторые, если вы укажете, что они будут приемлемым ответом на ваш вопрос.

• Как проводить исследования в MIT AI Lab "целой группой нынешних, бывших и почетных аспирантов MIT AI Lab" / Дэвид Чепмен, редактор

  Этот документ самонадеянно призван объяснить, как проводить исследования. Мы даем эвристику, которая может быть полезна при подборе определенных навыков, необходимых для исследования (чтение, письмо, программирование) и для понимания и наслаждения самим процессом (методология, выбор темы и советника, а также эмоциональные факторы).

• Как стать успешным аспирантом (в области компьютерных наук) Марк Дредзе (Университет Джона Хопкинса), Ханна М. Уоллах (Университет Массачусетса в Амхерсте)