(2 курс ФИИТ) Алгоритмы и структуры данных


#1

Вопросы по курсу.


#2

На момент переезда был открыт вопрос – делать ли третье задание (множество на основе БСП). Так вот, не знаю, что такое «БСП», но задание реализовать нужно, тем более, что оно не сложное.


#3

Перезагрузить сервер с мудлом за 20 минут до дедлайна - какой цинизм. :grimacing:


#4

Сервер с мудлом не перезагружался.


#5

Ну не знаю. Вчера в 23:40 кинулся заливать работу, но moodle и форум лежали - поднялись примерно 00:10


#6

Проблемы были у сети университета, она была недоступна.


#7

у меня такая же ситуация вчера была: не мог задание загрузить


#8

Лежала вся сеть ЮФУ. Мне кажется, это хороший урок о том, что задания не нужно делать в последний момент. Такова жизнь.


#9

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


#11

Вопрос. Задание сдал в классе, черновик залил, а отправить забыл… Теперь задание “висит” как не сданное. Что с ним делать?


#12

Да ничего не делать, раз сдали. На практике просто указать на это преподавателю, и всё.


#13

А если так регулярно делать: в процессе работы заливать и обновлять версии черновика, а если что-то в жизни случится, замотаться в других делах и не успеть нажать кнопку “Отправить задание”, то будет ли это критично? Т.е. так делать нежелательно, но баллы будут за это ставится или не будут, или всё равно - нажато ли там чего, лишь бы залито???


#15

Не важно, черновик это, или представлено к оценке – главное, чтобы была возможность выставить оценку.


#16

Если $m_h$ — минимальное число вершин в AVL-дереве высоты $h$. Как показать, что $m_{h+2} = m_{h+1} + m_h + 1$?

Это $h(L) + h® + 1$?


#17

Ну да, это практически очевидно, Вы всё правильно поняли.

Если AVL-дерево имеет высоту $h+2$, то, согласно определению, одно из поддеревьев корня имеет высоту $h+1$, а второе – $h+1$ или $h$. Для того, чтобы исходное дерево имело минимальное число вершин, левое и правое поддеревья корня должны иметь минимальное число вершин, тогда получаем: $$m_{h+2}=1 + m_{h+1} + min{m_{h+1},m_h}$$Осталось только показать, что $m_{h+1} > m_h$, что можно принять как очевидное, а можно и более строго попробовать доказать вспомогательное утверждение, что из AVL-дерева всегда можно удалить лист, и полученное дерево также будет AVL-деревом. Ну, остальное просто, хотя для полноты надо еще проверить верность утверждения для базиса – деревьев высотой 0 и 1, к примеру.

А как тут формулы-то по-человечески вставлять?


Пишем формулы и учим Маркдаун
#18

5 сообщений перенесены в новую тему: Пишем формулы и учим Маркдаун


#19

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

Что это за задание, и зачем реализовывать множество на основе предыдущего задания (сбалансированные деревья)?


#20

Эта задача обсуждалась на лекции, и представляет собой простейший словарь, где ключ - слово, а значение по ключу - кол-во вхождений слова в текст. Другими словами, нода представляется в виде пары ключ-значение, т.е. D[слово] равно какому-то целочисленному значению - кол-ву вхождений слова в текст.


#21

Надеюсь, словарь не надо делать на основе кучи?


#22

Зря надеетесь. Если эта надежда связана с предположением о том, что преподаватель опять заставляет использовать неэффективные алгоритмы, могу предложить такой вариант: если Вы реализуете это задание по-своему, и докажете эффективность реализации, то получите x2 баллов. Не сможете доказать эффективность или «изобретете велосипед» – x0, причём выбор структуры для реализации ассоциативного массива оптимизацией не является.

Кстати, пояснение по заданию в Moodle обновлено.