НГУ

Форумы НГУ
Текущее время: Сб дек 16, 2017 6:33 am

Часовой пояс: UTC + 7 часов




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 13, 2012 8:56 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Pavel E. Alaev писал(а):
хороший вариант - рассматривать МТ на 2-мерной плоскости и с конечным (фиксированным) числом головок.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт мар 16, 2012 10:16 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Коба писал(а):
Сортировку, кстати, не обязательно делать пузырьковым методом. Это один из самых неоптимальных алгоритмов сортировки.

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс мар 18, 2012 9:11 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Pavel E. Alaev писал(а):
А вот в т.н. "быстрой сортировке" прямой доступ к памяти используется существенно, и вероятностная оценка ... превращается, кажется, в ...

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 20, 2012 6:44 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Не понял про прямой доступ в быстрой сортировке. Быструю сортировку возможно реализовать и на структурах с последовательным доступом (списки) с тем же быстродействием ( в среднем).

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 20, 2012 9:34 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
fenster писал(а):
Не понял про прямой доступ в быстрой сортировке. ...

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Ср мар 21, 2012 8:07 am 
Не в сети
Редкий гость

Зарегистрирован: Вт мар 20, 2012 8:22 am
Сообщения: 1
Коба писал(а):
P. S. Кстати, есть такая теорема: язык является регулярным (распознаётся конечным автоматом) тогда и только тогда, когда он распознаётся на недетерминированной МТ за линейное время. Вот про это я слышал лишь краем уха, хотелось бы где-нибудь прочитать подробнее.


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт май 18, 2012 9:55 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Собрав некоторую информацию, вернёмся теперь к вопросу о курсах теории алгоритмов и мат. логики.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 20, 2012 9:34 pm 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
На втором потоке МТ давались лекции 2-3 и семинара 3-4 на теории алгоритмов, не меньше. Если студент более-менее освоил доказательства, использующиеся на лекциях и хоть что-то делал на семинарах, то МТ он более-менее освоил.

Цитата:
Если <...> студенты с ними основательно разобрались

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн май 21, 2012 10:14 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
tom-anjelo писал(а):
Насколько "основательно" необходимо было разобраться с МТ, чтобы в курсе мат.логики не требовалось знакомить с ними заново, не могли бы уточнить?

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн май 21, 2012 10:26 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Когда я учился, у нас ещё не было теории алгоритмов на 1 курсе, но в курсе матлогики в 3-м семестре мы достаточно на них, так сказать, напрограммировались. Что вовсе не помешало семинаристам по теории программирования (4 курс, 1 поток) заставить нас решать все те же задачки по программированию на МТ заново (правда, с немного другим алфавитом).

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

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

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 22, 2012 12:56 am 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
Pavel E. Alaev писал(а):
Вы, наверно, сообщаете нам о том, как обстояло дело в Вашей группе. Если мы говорим про программы в целом, нужна информация о всех группах. Я в прошлом встречал довольно разнообразные ответы на вопрос "насколько хорошо вы изучили программы для МТ".

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

Pavel E. Alaev писал(а):
Разве моё предыдущее сообщение не содержало ответ на Ваш вопрос?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 22, 2012 1:09 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
fenster писал(а):
Кстати, лично мне написание программ для МТ ... видится занятным интеллектуальным упражнением (ну, как решение кроссвордов).

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 22, 2012 10:27 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Pavel E. Alaev писал(а):
Если бы существовала твёрдая уверенность, что в 1-м семестре две-три лекции и 2-3 семинара были посвящены МТ, и студенты с ними основательно разобрались и научились писать простенькие программы, ситуация бы изменилась.

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 22, 2012 11:35 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Pavel E. Alaev писал(а):
Кроме того, некоторое время назад на ММФ ещё регулярно переставляли лекторов с потока на поток, так что программу приходилось разрабатывать так, чтобы она годилась для любого курса ТА, который был в 1-м семестре. В этом случае ситуация с МТ становится ещё более живописной.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб май 26, 2012 9:36 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Коба писал(а):
Узнаёте, кто читал перед Вами ТА, подходите к лектору и в частной беседе выясняете, что именно им читалось и в каком объёме. После этого адаптируете свой курс под конкретный поток.

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

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

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

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

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3, 4  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: AlfredoExort, FloydEvops, GeorgeMaf, Georrequact, Henrybug и гости: 15


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB