Результаты экзамена по курсу "Алгоритмы и алгоритмические языки (2010/2011 уч

Результаты экзамена по курсу "Алгоритмы и алгоритмические языки (2010/2011 уч.гг.)."

01_23 Абдель Маджид Али Амир -+ + +- 4

Теорема о связи нижних оценок времени решения задач на принятие решения и количества линейно-разделимых компонент множества точек, на которых решением задачи будет `да’. Пример задачи на определение, совпадают ли два множества?

Что такое W? Дальше вообще все плохо: в кучу смешаны сравниваемые множества и множесто линейно-разделимых компонент. На самом деле, это – совершенно разные множества. Откуда взялась формула снизу?

02_04 Абдель Маджид Надя Амир +- + +/2 4

Может статься, что A₂_i>A_i и A₂_i₊₁>i. И что тогда делать? А если вызывать рекурсию для обоих элементов, то… Что? Даже не написано, чему это противоречит.

А почему первый вызов создает пирамиду?

03_05 Абдулпотиев Абдулмалик Абдулхамид угли + -+ - 3

Сортировка подсчетом:

Т.е. получается, что для каждого элемента надо делать линейный проход. Итого: время работы=O(n²). Это – не сортировка подсчетом.

Цифровая сортировка :

А где зависимость времени от числа бит? Ведь указанную операцию надо производить для каждого бита. И как сортировать по каждому биту?

04_22 Асамов Комилхон Маъруфхон угли + + + 5

Вы путаете понятия: преобразование типов используется, если необходимо математическое понимание переменной перенести в переменную другого типа (например, преобразовать целую единицу в вещественную единицу). А объединения нужны для того, чтобы по-разному проинтерпретировать один и тот же кусок памяти (например, проинтерпретировать его как целую и как вещественную переменную).

05_14 Атахужаев Собитхон Акбаралиевич +. + +- 5

Следующее определение на языке С абсолютно бессмысленно:

По логике, здесь надо писать что-то вроде:

#define NEdge 100

int edges[NEdge] [2];

06_15 Ахунов Рустам Ахмедович + + +- 5

Ой, у вас определение графа было, как минимум, на ДВУХ предметах. Пора бы и выучить.

07_03 Бекташев Руслан Анварович +- + +. 5

В этом и есть содержательная часть вопроса: надо доказать, что эти константы a и b можно найти и при этом эти константы должны не зависеть от N.

08_12 Бобров Борис Павлович + + + 5

09_16 Бочкарев Артем Сергеевич +. +- - 4

Сортировка подсчетом:

Очевидно, что массив B должен иметь не тот же размер, что и массив A.

Логические операции:

Не сказано, что может быть на входе. А ведь это не только 0 или 1. Не сказано, какая связь между понятиями Истина и Ложь и целыми переменными.

10_10 Буронов Бунёд Мамуржон угли +- -+ - 3

Прежде чем рассмотреть вершину, в которой нарушился баланс, его (баланс) надо как-то нарушить. Нет описания того, с чего надо начинать вставку элемента в сбалансированное дерево (т.е. вставки элемента в дерево поиска).

Про то, как до балансировки удалить вершину тоже ничего не сказано.

Нет определения строки в понимании языка С. Из приведенных функций две не имеют никакого отношения к строкам. Остальные имеют отношение только к вводу/выводу строк. Где копирование, поиск, сравнение строк?

Оценка выставлена с учетом работы в семестре.

11_21 Валиев Комронхон Аббосович +- +- +- 4

Константы.

Это, конечно, не верно. Тип зависит только формы написания константы: константа типа int – 1; константа типа long – 1L; константа типа char – ’ \01’;

Следующие константы не символьные, а строковые:

Нижние оценки.

Понятия принимающая/отвергающая вершина относится только к листьям. Собственно, это вершины, которые дают ответ задачи.

Следующее определение бессмысленно абсолютно:

Вообще-то, с учетом работы в семестре и незаконченности ответа на второй вопрос, надо ставить тройку… Ну да ладно…

12_21 Волков Станислав Анатольевич +- + - 4

Задача поиска всех различных элементов множества никак не приведена к теореме из билета. Т.е. нижняя оценка для нее не доказана.

13_10 Галимзянова Асия Хакимовна + +- + 5

Простим откровенное плавание во втором вопросе.

14_11 Ганиходжаев Хасан Аскарович + + +- 5

Оценка с учетом работы в семестре.

15_06 Гарипов Чингиз Равшанович ? ? - 3

Честно говоря, я не знаю, как оценивать ответ: складывается впечатление, что вы вообще не понимали, что писали. Как иначе можно понять фразу если левое выражение =false, то левое не выполняется? Заметим, что фраза встречается с небольшим изменением дважды. Также заметим, что в приведенной фразе речь идет о непонятном операторе and. Это из какого языка?

Сортировки: чувство такое же. Как, иначе можно понять фразу (о принципе сортировки подсчетом):

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

16_02 Гуломов Саидхужа Ботир угли +/2 +/2 -+ 3

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

Сортировка слиянием без рекурсии:

Конечно, это – не то. В лекциях рассказывался вариант алгоритма сортировки слиянием, когда сначала весь массив разбивается на пары элементов и элементы в парах сливаются, потом сливаются пары пар, потом пары четверок и т.д.

Базовые типы. Очень много неточностей:

Начнем с того, что вам по определению не известны размеры переменных. Известно только, что sizeof(char)<=sizeof(short)<=sizeof(int)<=sizeof(long) и sizeof(float)<=sizeof(double)<=sizeof(long double) (последнего типа на конкретном компиляторе может и не быть). Про то, что размеры вещественных переменных у вас нереальные, я молчу.

Не сказано, как взаимосвязаны группы понятий {signed, unsigned} и {char, short int, int, long int}.

Вообще ничего не сказано про определение, описание, инициализацию переменных.

17_09 Дейнека Наталья Игоревна + + - 5

Несмотря на несделанную задачу, ответ на билет мне так понравился, что я, с учетом работы в семестре, поставил 5.

18_15 Зверев Алексей Юрьевич +- + +- 4

Алгоритм Дейкстры:

Здесь вообще не сказано, что такое l, w,v, так что определением это считаться не может.

Что обозначает последнее N ? Перед этим появляется явно не то N.

19_17 Ибрагимова Дилноза Тахировна +- + +- 4

Неправильное определение бинарного дерева поиска:

Даже если предположить, что сравнивая деревья, вы сравниваете все элементы в деревьях, то вы ничего не предполагаете о элементе, связывающем поддеревья. А самое главное: о каком правом и левом поддереве идет речь?

Далее, о высоте чего идет речь? :

Алгоритм поиска следующего элемента неправильный:

20_07 Кадыров Тимур Вадимович +- + -+ 4

В доказательстве оценки времени работы алгоритма поиска медианы самый главный переход выполнен без доказательства:

В целом выкладка выглядит так:

21_23 Кан Александр Николаевич - +- +- 3

Нижние оценки:

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

Следующая теорема, очевидно, не верна:

Дальше в ответе на первый вопрос идет что-то, вообще, бессмысленное.

Арифметические операции.

Про операцию + никогда не говорят, что это – бинарная операция. Бинарными называют операции, которые действуют побитово, т.е. значение каждого бита результата зависит только от соответствующих битов аргументов. Для сложения это не так. Кроме этого этот оператор может применяться не только для целых и вещественных типов. Также он может применяться для указателей и целых. Например, корректно выражение:

const char *s; s=”mama”+2;

22_02 Капкаев Данияр Дамирович +. +. +- 5

Сформулированная теорема неверна:

Контрпример: алгоритм сортировки слиянием основан на сравнении и имеет время обмена двух элементов T=O(N) (точное время =const), а верхняя оценка для него лучше, чем для пузырька.

Следующий факт неверен:

В современной 64-битной архитектуре для совместимости, обычно, sizeof(int)==4

Следующее утверждение не совсем верно:

В зависимости от установок компилятора, char может быть signed или unsigned.

Следующее утверждение неполно:

Вещественные числа в компьютере бывают с плавающей и фиксированной точкой.

И, все-таки, волевым усилием я ставлю 5. В принципе, существенный недостаток ответа один: формулировка теоремы. Простим это.

23_19 Каримов Анвар Маратович - +- - 3

Следующее выражение имеет весьма непонятный смысл:

Поиск элемента:

Списывать надо правильно!

В следующем примере также демонстрируется вопиющее непонимание списываемого:

Добавление элемента в дерево. Вероятно, картинки с вариантами разбалансировки дерева в шпору не поместились. Увы. В ответе они и не появились.

Очень понравился алгоритм удаления вершины:

Из написанного видно, что для удаления вершины надо только что-то найти. А удалять ничего не нужно. И так сойдет…

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

24_05 Каримов Даврон Фаррух угли + +. - 4

Сортировка:

А где зависимость от числа разрядов?

25_03 Кидяева Арина Игоревна +- +. +- 4

Сортировка:

К сожалению, одной фразы т.о. получается здесь совершенно недостаточно, чтобы сделать этот переход. А он здесь – основной.

Константы: в целом, все похоже на правду, только не надо использовать слово const в применении к константам. Слово const используется в отношении переменных, а не констант!

26_13 Коночкин Артем Игоревич + +- - 4

Условные операторы.

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

Следующее тоже не совсем правильно:

После case должно стоять не выражение, а константа. Это – принципиально. На самом деле, switch не есть прямая замена if…else if… . switch придуман для того, чтобы можно было бы за константу операций (не зависящую от количества операторов case) вычислить, на какой из операторов case можно было бы перейти. Это возможно, если возможных значений выражения switch не много (например, если значение выражения имеет тип char или short int) и только если после case стоят константы.

27_10 Курбонов Далер Туйчиевич + +- -+ 4

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

28_18 Ли Евгений Юрьевич + + + 5

29_12 Маркеев Анатолий Федорович + + + 5

Мда… Вы не прочитали в условии задачи всего одно слово: граф. Ну да ладно… Бывает…

30_04 Мирхамидов Мираъзам Хусан угли + +- -+ 4

Структуры:

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

Student.name=”Ivan”;

31_09 Пак Ольга Эдуардовна + + + 5

32_01 Пигалова Елена Викторовна + + +- 5

33_11 РонжинДмитрий Владимирович + + + 5

34_03 Ситдыков Искандар Маратович -+ +- - 3

Почему значится номер билета=3, а написан 14-тый билет?

Я не могу придумать ни одной интерпретации написанных слов во второй и третьей строке:

Если здесь написано смешность, то это к смежности отношения не имеет. Смешность, это – мера смеха, но не свойство двух вершин быть инцидентными одному ребру, или двух ребер быть инцидентными одной вершине.

А в этих двух первых строках все слова понятны, но вот смысла в них найти нет никакой возможности:

Рассмотрим следующую фразу:

Т.е. получается, что время работы чего-то вершин =O(M), т.е. это время зависит только от числа ребер. Такого быть не может. Да и вообще, форма хранения графа не задана, а время работы уже выписывается.

Следующее описание структуры не несет никакого смысла:

Работа со строками.

В следующем определении совершенно непонятно что и куда копируется:

Это, мягко говоря, не так.

35_20 Сытдыков Тимур Рашидович + + + 5

36_16 Турдиев Жалоладдин Махмуджанович + + +- 5

37_13 Утаев Авазжон Абдурахмон угли +- +- +. 4

На первый вопрос дана только идея решения.

Второй вопрос.

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

38_07 Хегай Сергей Игоревич + + + 5

39_01 Чен Марина Алексеевна +. + - 4

Следующее утверждение идеологически принципиально неправильное: