Добро пожаловать! Войти Зарегистрироваться

Расширенный

пятая лабораторная...

Написал raster@wa 
пятая лабораторная...
28 September 2006 23:11
может подскажете, что такое натурализация числа с ЛОГАРИФМИЧЕСКОЙ СЛОЖНОСТЬЮ??.. буду очень благодарна...
zzz
Re: пятая лабораторная...
29 September 2006 16:04
raster@wa писал(а):

> может подскажете, что такое натурализация числа с
> ЛОГАРИФМИЧЕСКОЙ СЛОЖНОСТЬЮ??.. буду очень благодарна...

Сложность алгоритма натурализации должна быть O(log n), где n -- объективная характеристика входного сообщения.
Re: пятая лабораторная...
29 September 2006 19:07
согласно лекции, в основании логарифма стоит система счисления.. а множеству каких чисел принадлежит число n?Не подскажете, где я могу взять дополнительную информацию по логарифмической сложности??
zzz
Re: пятая лабораторная...
29 September 2006 20:08
raster@wa писал(а):

> согласно лекции, в основании логарифма стоит система
> счисления.. а множеству каких чисел принадлежит число n?

Чтобы самостоятельно догадаться, вспомните, что сложение в натуральной с/с имеет линейную сложность!

> Не подскажете, где я могу взять дополнительную информацию по
> логарифмической сложности??

Cложение в столбик имеет логарифмическую сложность. Почему и отчего?
Re: пятая лабораторная...
29 September 2006 20:08
у меня проблема, я просто не могу понять, что есть логарифмическая сложность: операция или абстрактное понятие?? или может еще что-то. ..и для чего она нужна..
Кстати, большое спасибо за тот самый черный пакет!!со спокойной душой на физкультуру..
Re: пятая лабораторная...
29 September 2006 20:08
появилась идея.. может мне нужно отнимать по 1,для того, чтобы перевести.. ну и после каждого раза писать палочку..я хоть в правильном направлении мыслю??
zzz
Re: пятая лабораторная...
29 September 2006 21:09
raster@wa писал(а):

> у меня проблема, я просто не могу понять, что есть
> логарифмическая сложность: операция или абстрактное понятие??

класс трудо-(ресурсоёмкости) алгоритмов.

> или может еще что-то. ..и для чего она нужна..

Перечитайте сложностную таблицу в лекции, возьмите приведённый там пример c log n, постройте сравнительную таблицу n и log n для n = 1, 2, 4, 8, 16, 32, ... , 1024, постройте графики на одном поле, почувствуйте разницу!

Нужна для сравнения алгоритмов, выбора наилучшего. Важнейшая характеристика алгоритма.
Re: пятая лабораторная...
29 September 2006 21:09
знаете, я сейчас перерою все в интернете, воставлю эту таблицу, начерчу эти графики, хотя я уже поняла, что время выполнения у программ разное...но все-таки добьюсь того, что пойму это!!в крайнем случае.. ждите меня еще..правда на все перечисленное потребуется время.. одним днем я не ограничусь..но я пойму как делать задачу!!smiling smiley)))
zzz
Re: пятая лабораторная...
29 September 2006 21:09
raster@wa писал(а):

> появилась идея.. может мне нужно отнимать по 1,для того, чтобы
> перевести.. ну и после каждого раза писать палочку..я хоть в
> правильном направлении мыслю??

В данном случае характерная величина входного сообщения -- число единиц в значении числа линейно зависит от самого его значения.
Re: пятая лабораторная...
30 September 2006 00:12
спасибо, вы мне очень помогли.. на самом деле, алгоритм теперь понятен.. осталось только правильно оформить и продумать детали..я после последнего своего сообщения долго сидела и думала.. ошибку в своих рассуждений осознала почти сразу.. ну где-то минут через 30..)))еще раз спасибо..
Re: пятая лабораторная...
30 September 2006 14:02
все!! с программой покончено!! правда осталось пару вопросиков:
1.как узнать, что она все-таки наиболее рациональная??
2. пока я писала программу на МТ, у меня появилась пара лишних строк.. как их удалить из окна программы, не переписывая программу заново??
zzz
Re: пятая лабораторная...
30 September 2006 15:03
raster@wa писал(а):

> все!! с программой покончено!!

Сдана?

> правда осталось пару вопросиков:
> 1.как узнать, что она все-таки наиболее рациональная??

Доказать теорему о неулучшаемости сложностной оценки предложенного алгоритма. Или опровергнуть, предложив лучший способ.
Гость
Re: пятая лабораторная...
30 September 2006 15:03
Способ доказательства весьма меня интересует.
Т.е. как на Матике?
Я пока не окончил свою программу. И меня интересуют наиболее простые методы. У меня вычитание. Я знаю примерно как решить задачу в столбик. Это, как говорят умные люди лучший способ, но он сложнее и не соответствует моему заданию.

Re: пятая лабораторная...
30 September 2006 16:04
> Сдана?

сдать ее у меня еще не было времени, но по крайней мере на МТ она работает!! а как доказывать теорему о неулучшаемости сложностной оценки алгоритма??усложнить задачу в n раз?? и засечь время??)))у меня же нет такого точного прибора.. а жаль.. ведь по идее время должно увеличиться в 2 раза.. я правильно поняла?
Re: пятая лабораторная...
30 September 2006 17:05
и кстати, что значит, увеличить размер задачи??в какой системе счисления нужно увеличить число в n раз??или здесь имеется ввиду увеличить длину слова в n раз?
zzz
Re: пятая лабораторная...
30 September 2006 17:05
raster@wa писал(а):

> > Сдана?
>
> сдать ее у меня еще не было времени, но по крайней мере на МТ
> она работает!!

Проверьте, все ли требования задания выполнены!

> а как доказывать теорему о неулучшаемости
> сложностной оценки алгоритма??

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

> усложнить задачу в n раз?? и
> засечь время??)))у меня же нет такого точного прибора.. а
> жаль.. ведь по идее время должно увеличиться в 2 раза.. я
> правильно поняла?

В описании ЛР №5 написано, что одна из программ ведёт подсчёт статистики выполнения. ВременнАя сложность измеряется не в секундах, а в у.е.
zzz
Re: пятая лабораторная...
30 September 2006 17:05
123098 писал(а):

> Способ доказательства весьма меня интересует.
> Т.е. как на Матике?

Да, на лекциях у нас и по ДМ будут рассмотрены разные способы, например индукция по длине входной цепочки, по высоте дерева или по глубине скобочной структуры.
zzz
Re: пятая лабораторная...
30 September 2006 17:05
raster@wa писал(а):

> и кстати, что значит, увеличить размер задачи??в какой системе
> счисления нужно увеличить число в n раз??или здесь имеется
> ввиду увеличить длину слова в n раз?

У каждой задачи свой размер, например, значение числа или длина его записи.
Re: пятая лабораторная...
03 October 2006 16:04
все!!! теперь сдана!!!
zzz
Re: пятая лабораторная...
03 October 2006 17:05
raster@wa писал(а):

> все!!! теперь сдана!!!

Я уже знаю, мне сообщили в 14:45.
Re: пятая лабораторная...
03 October 2006 22:10
ну вот.. ((все-таки по МАИ быстро распространяется информация.. видно даже и у стен есть уши..так что, ребят, поосторожнее с фразами-то!!))))
zzz
Re: пятая лабораторная...
04 October 2006 18:06
raster@wa писал(а):

> ну вот.. ((все-таки по МАИ быстро распространяется информация..
> видно даже и у стен есть уши..так что, ребят, поосторожнее с
> фразами-то!!))))

Просто Ваш преподаватель сказал мне (с гордостью!), что уже сдана первая в группе ЛР №5, причём работа сделана самостоятельно после безуспешных попыток проконсультироваться на форуме!
Re: пятая лабораторная...
04 October 2006 21:09
Меня опередили ! Все из-за справки в военкоммат. Я сдал вторым grinning smiley
Re: пятая лабораторная...
04 October 2006 21:09
не волнуйся.. успеем еще посоревноваться.. !!!smiling smileyесли ты можешь считать слабую девушку настоящим соперником..))
Re: пятая лабораторная...
04 October 2006 23:11
zzz
Re: пятая лабораторная...
05 October 2006 13:01
PhanT0m писал(а):

> Меня опередили ! Все из-за справки в военкоммат. Я сдал вторым
> grinning smiley

Зато стал мужчиной!
Гость
Re: пятая лабораторная...
10 October 2006 18:06
А вот 4-ки типа <99,1,1,98> <10,л,л,11> <19,0,0,20> допустимы?
Это ведь пустые! Но иногда, при отладке приходится для "красоты" переписывать всю прогу.
zzz
Re: пятая лабораторная...
10 October 2006 19:07
123098 писал(а):

> А вот 4-ки типа <99,1,1,98> <10,л,л,11> <19,0,0,20>
> допустимы?
В качестве заплаток? Да.
> Это ведь пустые! Но иногда, при отладке приходится для
> "красоты" переписывать всю прогу.
Уже должно быть ясно, что программа МТ целиком и полностью состоит из заплаток qi a v qj, пришитых как попало.
DIZ
Re: пятая лабораторная...
10 October 2006 21:09
"Это ведь пустые!..."
какие же это пустые, когда приведенные примеры чистой воды ветвления (переходы)!



С уважением, Дмитрий
Гость
Re: пятая лабораторная...
12 October 2006 20:08
""" Каждая кнопка - 6 долларов""""

>когда приведенные примеры чистой воды ветвления (переходы)!

Но их можно обойти. Строка прогу бережет.

Гость
Re: пятая лабораторная...
12 October 2006 20:08
А слабо все проги со **?
Давйте не на скорость а на сложность.!!!!!

<666,!,@,666>
DIZ
Re: пятая лабораторная...
13 October 2006 11:11
Ветвления нельзя избежать. Просто обычно в одной четверке осуществляется и операция перемещения (замены), и перехода одновременно. В приведенных четверках есть только переход. IMHO они ничем не хуже других.
Насчет слабо/не слабо. Каждый выбирает сам чем заняться. Любое задание можно усложнить при желании. К примеру, 24-27 легко "усиливаются" если основанием target системы взять 10, например.
Мне вполне хватает 14-ой smiling smiley



С уважением, Дмитрий
Гость
e: пятая лабораторная...
13 October 2006 18:06
Существенный вопрос, как написать 24-27 проги (д-мы), но в обратном порядке. В 16-ную систему примерно знаю, а вот без 2^n? (14)
Мне слабо.
Вообще, в прямом ходу на входной 10, - четверки, такие же как в 16, но без доп 6 наборов.
А наоборот... Как быть если пользователь ввел несуществующие тетры?

Автор DIZ, желаю познакомиться лично, как можно Вас найти?

DIZ
Re: пятая лабораторная...
13 October 2006 22:10
Что в прямом, что в обратном направлениях 24-27 (здесь и ранее имеются ввиду номера заданий для Л5, если не указано иное, а то уже путаница некоторая) решаются буквально в одном прогоне. Тут основания систем исчисления кратны друг другу. Т.е. что значит основание 2 и 8? Делим одно на другое. и получается, что первое число в 4 раза длинее второго. Именно ровно в 4. т.е. для преобразования из двоичного числа в восьмиричное нужно каждой четверке поставить в соответсвие число от 0 до 7 в восьмеричной системе. В друх других задачах то же самое, только основание кратно 3.
Совсем другое дело, когда основания не "родственны", т.е. не делятся нацело друг на друга. Здесь применимо общее правило преобразования из разных систем исчислений. По-моему оно есть в лекциях. Оно так же работает для 24-27, но эти задачи проще реализуются.
Показываю на примере:
14FD3h преобразуем в 10-ое число.
1*16^4+4*16^3+15*16^2+13*16^1+3*16^0.
Из 10-ой в 16-ричную с точностью до наоборот. Делим 10-ое число на 16. Остаток от деления записывая справа налево.
Вот этот алгоритм написать на для МТ действительно почетно smiling smiley

2 Илья. В карточке есть ICQ.



С уважением, Дмитрий
DIZ
Re: пятая лабораторная...
13 October 2006 23:11
Еще веселее преобразование из, к примеру, 12-ричной в 14-ричную.
Это уже на 5* тянет smiling smiley



С уважением, Дмитрий
Re: пятая лабораторная...
13 October 2006 23:11
>Т.е. что значит основание 2 и 8? Делим одно на другое. и получается, что первое число в 4 раза длинее второго.

а вот я почему-то всегда думала, что число в двоичной системе счисления в три раза длиннее числа в восьмеричной системе счисления)))...и еще.. в примере перевода 14FD3h откуда h-то взялась?))))
DIZ
Re: пятая лабораторная...
14 October 2006 10:10
Конечно в 3, Ира. Это я под ошибся smiling smiley
2^1 -двоичная. 2^3 -восьмиричная. Делим степени.
h обозначает, что запись в 16-ричной системе.



С уважением, Дмитрий
zzz
Re: пятая лабораторная...
14 October 2006 13:01
DIZ писал(а):

> Конечно в 3, Ира. Это я под ошибся smiling smiley
> 2^1 -двоичная. 2^3 -восьмиричная. Делим степени.
Всюду логарифмы!!!
> h обозначает, что запись в 16-ричной системе.
>
Гость
Re: пятая лабораторная...
15 October 2006 23:11
На бумаге и в формулах еще все сносно.
А вот как ?
>....Еще веселее преобразование из, к примеру, 12-ричной в 14-ричную.

Я пока представляю, через натуральную.
Но так на лог-сложности можно ставить крест.

Я подумал
>// Вообще, в прямом ходу на входной 10, - четверки, такие же как в 16, но без доп 6 наборов. - Неверно вкорне.
Re: пятая лабораторная...
16 October 2006 22:10
Скажите, пожалуйста, можно использовать маркеры при выполнении 5ой лабораторной работы??
Гость
Re: пятая лабораторная...
16 October 2006 23:11
>Скажите, пожалуйста, можно использовать маркеры при выполнении 5ой лабораторной работы??

Помниться на лекции сказали, что это чреввато снижением Балла. на 1 или 2 ед. Если Вы сможете доказать, что это необходимо, то возможно Оц. не понизят.

Гость
Re: пятая лабораторная...
16 October 2006 23:11
Помнится без Ь. чревато с 1 в.

zzz
Re: пятая лабораторная...
17 October 2006 13:01
Alexander писал(а):

> Скажите, пожалуйста, можно использовать маркеры при выполнении
> 5ой лабораторной работы??

Перечитайте условие ЛР №5. Об этом уже много раз говорили. И в шутку ($6), и всерьёз. Последний раз -- 11 X:
"Дополнительные несобственные буквы по теореме о нормированной вычислимости всегда излишни!"
К сожалению, только зарегистрированные пользователи могут писать в этом форуме.

Авторизоваться на форуме