НГУ

Про такое я тоже читал. В смысле что лента уже не лента, потому что "квадратная". Насчёт числа головок не помню.

Сортировку, кстати, не обязательно делать пузырьковым методом. Это один из самых неоптимальных алгоритмов сортировки.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Здесь важно, насколько хорошей мерой сложности является 2-мерная МТ.

Стандартная оценка для сортировки натуральных чисел пузырьком равна , где n - число элементов массива. Она даётся в предположении, что числа в массиве не очень велики, и их сравнение и перестановка занимает 1 шаг. В общем случае, кроме n, можно рассматривать второй параметр m - максимум из элементов массива, тогда оценка превратится в .

Для многоленточной (но одномерной) МТ и 2-мерной получится то же самое, ничего не ухудшится. Если говорить про сортировку слиянием, там стандартная оценка , уточнённая , и снова переход к многоленточным или 2-мерным МТ ничего не ухудшает.

А вот в т.н. "быстрой сортировке" прямой доступ к памяти используется существенно, и вероятностная оценка вида превращается, кажется, в при переходе к многоленточной МТ и в для 2-мерной МТ, т.е. мы теряем одну степень.

Нет, я не прав. Если не использовать стандартную рекурсию, со стеком и т.п., а расставлять метки прямо в массиве, то и здесь можно обойтись без прямого доступа к памяти, и оценка для многоленточных МТ снова получится "правильная": .

Вообще, даже если алгоритм требует прямой доступ в памяти настолько существенно, что использование многоленточных МТ обязательно ухудшит оценку, прямой доступ возможен только при жёстких ограничениях на длину входной информации. Если её станет слишком много, придётся использовать что-то типа файлов или других внешних хранилищ, к которым доступ всё равно будет последовательным.

Если мы хотим провести максимально общий анализ алгоритма, нам нужно учесть этот факт, и многоленточные МТ могут оказаться подходящим инструментом. А уж скорость конкретной компьютерной реализации конкрентного алгоритма настолько зависит от технических деталей, включая то, какие именно константы присутствуют в O(...), что тут уже нужна другая математика.

Не понял про прямой доступ в быстрой сортировке. Быструю сортировку возможно реализовать и на структурах с последовательным доступом (списки) с тем же быстродействием ( в среднем).

_________________
АФ

Стандартный алгоритм использует рекурсию, а стандартная реализация рекурсии подразумевает, что сначала номера ячеек кладутся в стек в произвольном (вообще говоря) порядке, а потом извлекаются оттуда. Отсюда и прямой доступ к памяти.

Но в последнем посте я как раз поправился, и написал в точности то же самое, что и Вы.

Доказательство можно посмотреть в P. Odifreddi, Classical recursion theory, второй том, глава VIII.1 Small time and space bounds. Точнее, там доказывается, что язык регулярен тогда и только тогда, когда он распознаётся на детерминированной одноленточной МТ за линейное время.

Собрав некоторую информацию, вернёмся теперь к вопросу о курсах теории алгоритмов и мат. логики.

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

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

Если бы существовала твёрдая уверенность, что в 1-м семестре две-три лекции и 2-3 семинара были посвящены МТ, и студенты с ними основательно разобрались и научились писать простенькие программы, ситуация бы изменилась.

На втором потоке МТ давались лекции 2-3 и семинара 3-4 на теории алгоритмов, не меньше. Если студент более-менее освоил доказательства, использующиеся на лекциях и хоть что-то делал на семинарах, то МТ он более-менее освоил.


Насколько "основательно" необходимо было разобраться с МТ, чтобы в курсе мат.логики не требовалось знакомить с ними заново, не могли бы уточнить?

Разве моё предыдущее сообщение не содержало ответ на Ваш вопрос?

Вы, наверно, сообщаете нам о том, как обстояло дело в Вашей группе. Если мы говорим про программы в целом, нужна информация о всех группах. Я в прошлом встречал довольно разнообразные ответы на вопрос "насколько хорошо вы изучили программы для МТ".

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

Когда я учился, у нас ещё не было теории алгоритмов на 1 курсе, но в курсе матлогики в 3-м семестре мы достаточно на них, так сказать, напрограммировались. Что вовсе не помешало семинаристам по теории программирования (4 курс, 1 поток) заставить нас решать все те же задачки по программированию на МТ заново (правда, с немного другим алфавитом).

Это я просто к тому, что матлогикой и теорией алгоритмов МТ-зависимые курсы не исчерпываются.

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

_________________
АФ

Судя по сведениям от студентов, МТ проходились во всех группах и во всех группах студенты учились писать программы (опять же, речь о втором потоке). А вот дальнейшее уже на примере своей группы говорю, действительно: научились работать с МТ те и только те студенты, которые хотели научиться с ней работать


Если Вы про то, что студенты должны были научиться простенькие программы, то вопрос остаётся в силе: что подразумевается под словом "простенькие"? Написать сумму двух чисел в одинарной и бинарной системах или нечто сложнее?

Механик на вопрос, что такое мгновенная скорость частицы, может ответить, что она строго определяется как производная от функции координат, а математик знает, что площадь сложно устроенного множества на плоскости - его мера Лебега. Естественно было бы и специалисту по алгоритмам иметь ясное и чёткое определение того, что такое число шагов работы алгоритма.

Если же мы предлагаем в качестве ответа определение через МТ, то для его глубокого понимания, по-видимому, нужны какие-то минимальные навыки написания программ. Например, если мы захотим доказать, что какой-то класс машин эквивалентен МТ, нам нужно будет суметь промоделировать работу этих машин на МТ, и наоборот. Едва ли человек, написавший 2 программы для МТ, быстро справится с такой задачей.

Выскажусь как человек, читавший лекции по ТА на том потоке, на котором Павел сейчас читает матлогику.

1) На лекциях машины Тьюринга разбирались очень подробно. Доказывалось, что любая чрф вычислима на машине Тьюринга и наоборот, причём доказывалось предельно строго, все кодировки прописывались до мельчайших деталей. Также на лекциях выписывались на доске следующие программы: прибавление к двоичному числу единицы, вычитание из ненулевого двоичного числа единицы (с проверкой условия на то, что число ненулевое).

2) За группы 1121 и 1122 могу сказать, что машины Тьюринга они программировали минимум семинара 2. За остальные группы сказать, увы, не могу, семинары вёл не я.

3) Машина Тьюринга у нас была одноленточная, лента ограничена с левого конца. Все вычисления над числами производились в двоичной системе счисления. На семинарах разбирали функции типа суммы, умножения на 3 и т. п. Плюс стандартные функции над любым алфавитом: удаление символа со сдвигом влево, вставка символа в произвольной позиции, "переворачивание" слова, удвоение слова...

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Не понимаю, что тут "живописного".

Узнаёте, кто читал перед Вами ТА, подходите к лектору и в частной беседе выясняете, что именно им читалось и в каком объёме. После этого адаптируете свой курс под конкретный поток.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

В принципе, можно и так делать. Хотя если обобщать, то некоторым лекторам на 4-м курсе придётся каждый год собирать небольшое совещание, и утверждать на кафедре новую программу. Плюс за месяц до начала лекций его (вместе с семинаристами) могут ожидать разнообразные сюрпризы в виде внезапно исчезнувших кусков в прошлых курсах, без которых вообще всё придётся перестраивать.

Принципиально более удобен регулярный порядок, когда для прошлых курсов есть некоторый стандарт, все лектора его придерживаются, и на 4-м курсе можно быть уверенным, что на 1-м некоторые вещи точно были. Ситуация с МТ была живописна в том смысле, что такая регулярность отсутствовала. Но это я в основном говорю о том, что было в прошлом, в частности, о программе Л.Л.Максимовой.


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

Если говорить о (возможном) исключении МТ из курса логики, то у меня конструктивный вопрос: нельзя ли сделать так, чтобы МТ проходились на семинарах в обязательном порядке, независимо от вкусов семинаристов? У лекторов, кажется, есть такие полномочия.