Решения задач с очного тура 2015
Описание файла
PDF-файл из архива "Решения задач с очного тура 2015", который расположен в категории "". Всё это находится в предмете "универсиада" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
стр. 1 из 9Решения задач очного тура— Общая часть —1.∫︁2Вычислить интеграл.2 + cos 0H Решение. Найдем неопределенный интеграл:∫︁{︁ }︁= = tg=2 + cos 2∫︁tg 222√√√√ + ;==2arctg+=arctg3 + 23333функция tg 2 разрывна в точке = . Одна из первообразных⎧tg ⎨√2 arctg √ 2 , ∈ [0; );33 () =⎩ √2 arctg tg√ 2 + * , ∈ (; 2];33 * находится их условия: ( − 0) = ( + 0), тогда * =N2Ответ. √ .32.2√.3Решите уравнение ′ − 24 = 2 ln .H Решение. Используем замену неизвестной функции. ′ − 24 = 2 ln ⇔ −1 ′ − 2 ln = 24 ⇔ { = ln } ⇔ ′ − 2 = 24 .Далее решим однородное уравнение ′ − 2 = 0.˜ 2.=2⇔ = Найдем ˜ методом вариации произвольной постоянной.
Подставляя в неоднородное уравнение2 , получим ˜˜ ′ () = 2, отсюда ()˜ = ()= 2 + , = 2 + 4 .N2 +4Ответ. = .3.Ане 15 лет, и в письме она использует смайлики. Каждый смайлик Ани состоит из двоеточияи произвольного конечного количества скобок одного типа: или открывающих круглых, или закрывающих. Например: «:)», «:)))))», «:((». Помимо смайликов, текст может содержать и обычныескобки.
Если после смайлика нужно поставить скобку того же типа, то, чтобы не было путаницы,она ставится после пробела: «Привет!!!! (если помнишь меня:))))) )».Напишите функцию, которая будет определять разность между общим количеством скобок в«веселых» смайликах и суммой скобок в «грустных» смайликах Ани. Допускается только одинпроход по тексту письма и использование конечного объема памяти (копирование письма в переменную недопустимо). Функция должна быть написана на одном из языков: Pascal, C, C++.Выбор того, в каком виде представлено письмо, остается за вами.H Решение. Наиболее простой способ решения — пройти по тексту письма, и при виде знакадвоеточия перейти в режим 1, находясь в котором, функция считает скобочки. Если при проходев режиме 1 встретилась не скобочка или скобочка не того типа, происходит переход обратно врежим 0, в котором функция пребывает по умолчанию.
Важно отметить две вещи:1. После смайлика может стоять скобка («Привет!! :)))(надеюсь ты меня не забыл)»), и она недолжна засчитываться как относящаяся к смайлику, поэтому нужно запоминать предыдущую скобку.2. Два смайлика могут идти подряд («А это я!!:)):))»), поэтому при переходе обратно в нулевойрежим надо не забыть после этого проверить симол, не двоеточие ли это.— Универсиада «Ломоносов» 2015 —стр.
2 из 9Решения задач очного тураЭти две ситуации отражены в решении всех вариантов. Решения отличаются только действиями над счетчиком «внутри» смайлика.Язык Pyhtondef count_smileys_1(s):mode = 0counter = 0prev_smiley = ’’for x in s:if mode == 1:if x == ’)’ and prev_smiley != ’(’:counter += 1prev_smiley = ’)’elif x == ’(’ and prev_smiley != ’)’:counter -= 1prev_smiley = ’(’else:mode = 0if x == ’:’:mode = 1prev_smiley = ’’return counterЯзык C++int count_smileys_1(char* s, int len_s) {int counter = 0;int mode = 0;char prev_smiley = ’-’;for(int i = 0; i < len_s; i++) {if(mode == 1) {if(s[i] == ’)’ && prev_smiley != ’(’) {counter++;prev_smiley = ’)’;}else if(s[i] == ’(’ && prev_smiley != ’)’) {counter--;prev_smiley = ’(’;}else {mode = 0;}}if(s[i] == ’:’) {mode = 1;prev_smiley = ’-’;}}return counter;}NОтвет.
Код программы.— Универсиада «Ломоносов» 2015 —стр. 3 из 9Решения задач очного тура— ВМ —4.Найдите температуру в бесконечном тонком однородном стержне с теплоизолированной поверхностью во все моменты времени > 0, если материал стержня описывается коэффициентом2 = 1, плотность распределения его внутренних источников/поглотителей тепла задается функцией −3 sin , а температура при = 0 равна cos 2.H Решение. Математически задача записывается следующим образом:{︂ = + −3 sin , = (, ), ∈ R, > 0,(, 0) = cos 2, ∈ R.Будем искать ее решение в виде = + , где{︂ = + −3 sin ,(, 0) = 0.{︂ = ,(, 0) = cos 2.Решения этих задач будем искать в виде = 1 () sin и = 2 () cos 2.
Тогда{︂ ′{︂ ′1 = −1 + −3 ,2 = −42 ,1 (0) = 0.2 (0) = 1.Теорема единственности гарантирует отсутствие других решений.N− − −3sin + −4 cos 2.Ответ.25.В пространстве 2 [0, /2] найти расстояние от точки () = cos до множества⎧⎫/2⎪⎪∫︁⎨⎬[︁ ]︁ = () ∈ 2 0,:4 sin () = 0 .⎪⎪2⎩⎭0H Решение. Заметим, что в задаче требуется в гильбертовом пространстве H найти расстояниеот некоторой точки до множества , которое представляет собой гиперплоскость, то есть ={ ∈ H : ⟨, ⟩ = 0}, где – фиксированный элемент гильбертова пространства .Тогда имеет место следующее соотношение (см. рис.):ℎ = − ,(1)где ℎ – проекция точки на множество , – вектор нормали гиперплоскости, – некотороечисло. Далее, так как ℎ ∈ , то⟨, ℎ⟩ = 0(2)Откуда с учетом (1) имеем=⟨, ⟩‖‖2(3)— Универсиада «Ломоносов» 2015 —стр.
4 из 9Решения задач очного тураТаким образом проекция точки на множество равнаℎ=−⟨, ⟩,‖‖2(4)а расстояние от точки до множества M равно‖‖ =|⟨, ⟩|‖‖(5)В варианте 1 = 4 sin , = cos ∫︁/2∫︁/228(1 − cos 2)2 = 4,(4 sin ) =‖‖ =200∫︁/2∫︁/2∫︁/21⟨, ⟩ = cos 4 sin =2 sin 2 = −2 cos 2 = .22000И расстояние от точки до множества√⟨, ⟩‖‖ ==.‖‖4N√Ответ.6..4Построить монотонную разностную схему, аппроксимирующую со вторым порядком задачу2 2+= − (1 , 2 ), (1 , 2 ) ∈ = {0 < 1 < 1 , 0 < 2 < 2 };21 22(0, 2 ) = 0, 0 < 2 < 2 ;1(1 , 2 ) = 0, (1 , 2 ) ∈ ∖{1 = 0, 0 < 2 < 2 }.Выписать метод Якоби для решения разностных уравнений.H Решение.
Введем разностную сетку = (1, , 2, ); 1, = ℎ1 , 2, = ℎ2 ; ℎ1 1 = 1 , ℎ2 2 = 2 ;1ℎ = { ; = 1, 2, . . . , 1 − 1; = 1, 2, . . . , 2 − 1} ;2ℎ = {0 ; = 1, 2, . . . , 2 − 1} ;ℎ = {0 , 2 , 1 ; = 0, 1, . . . , 1 − 1; = 1, 2, . . . , 2 − 1} .Основное уравнение аппроксимируем со вторым порядком с использованием пятиточечногоразностного оператора Лапласа:¯1 1 , + ¯2 2 , = − , ∈ 1ℎ .Рассмотрим аппроксимацию граничного условия 2-го рода на 2ℎ .ℎ1 2 (0 ) +(0 ) + (ℎ21 ) =12 21(︂)︂ℎ1 2 =(0 ) −(0 ) + (0 ) + (ℎ21 ) =12 22ℎ1=(0 ) − (¯2 2 ,0 + 0 ) + (ℎ21 + ℎ22 ).121 ,0 =— Универсиада «Ломоносов» 2015 —стр. 5 из 9Решения задач очного тураПриходим к уравнению1 ,0 + 0.5ℎ1 (¯2 2 ,0 + 0 ) = 0, 0 ∈ 2 .Учитывая равенства = 0, ∈ ℎ , монотонность схемы вытекает из канонической формызаписи разностных уравнений:)︂(︂1221+ 2 = 2 (−1 + +1 ) + 2 (−1 + +1 ) + , ∈ 1ℎ ;2ℎℎ2ℎ1ℎ2)︂(︂ 122120 = 2 1 + 2 (0−1 + 0+1 ) + 0 , 0 ∈ 2ℎ .+ℎ21 ℎ22ℎ1ℎ2NОтвет.¯1 1 , + ¯2 2 , = − , ∈ 1ℎ ;1 ,0 = −0.5ℎ1 (¯2 2 + )0 , 0 ∈ 2ℎ ; = 0, ∈ ℎ .Метод Якоби:()(+1)−1 − 2()+ +1ℎ21(+1)−20ℎ21(+1)()+ 21()+()+ +1ℎ22()+(+1)−1 − 2(+1)0−1 − 20= − , ∈ 1ℎ ;()+ 0+1ℎ22= −0 , 0 ∈ 2ℎ ;= 0, ∈ ℎ .— ММ —4.Пусть и – независимые случайные величины, определенные на одном вероятностномпространстве.
имеет равномерное распределение на отрезке [1, 2], а – дискретная случайнаявеличина, принимающая значения -1, 0, 1 с вероятностью 1/3 каждое. Пусть = . Найтиматематическое ожидание случайной величины .H Решение. По формуле полной вероятности = ( (|)). Далее ( (|)) =1( (| = −1) + (| = 0) + (| = 1)) .3Поскольку и независимы− (| = −1) = ∫︁2=− ,1 (| = 0) = 1,∫︁2 (| = 1) = = .1Вычисляя интегралы, получаем ответ.N)︀1 (︀ −2− + −1 + 1 − + 2 .Ответ.
=3— Универсиада «Ломоносов» 2015 —стр. 6 из 9Решения задач очного тура5.Найти точку минимума функции (1 , 2 , 3 ) = 81 2 3 + 2/(1 2 ) + 4/(1 3 ) + 5/(2 3 )в области 1 > 0, 2 > 0, 3 > 0.H Решение. Условия оптимальности первого порядка42= 82 3 − 2 − 2 = 0,11 2 1 325= 81 3 −− 2 = 0,221 2 2 345= 81 2 −−= 0.231 3 2 23Деля первое уравнение на 2 , а второе — на 1 , и, вычитая их, получим 2 = 45 1 . Аналогичнонаходим, что 3 = 52 1 .
Минимум функции(︁55 )︁24 1 , 1 , 1 = 2531 + 2425116 1/51/5 .достигается при 1 = ( 125) = 52 ( 252 )N(︂ )︂(︂ )︂(︂ )︂1/52 25 1/51 25 1/525Ответ. 1 =, 2 =, 3 =.5 22 226.Найти схемную сложность булевой функции (˜2 ) = (0110) в элементарном базисе.H Решение. Cхема (формула) сложности четыре — ( ∨ )&&. Докажем отсутствие схемыменьшей сложности. Схема меньшей сложности должна содержать два двухвходовых элемента иодин элемент отрицания (кроме задачи варианта 3).
Кроме этого пути от входов, соответствующихпеременным, по которым функции немонотонны и не антимонотоны, должны проходить как черезотрицание, так и мимо него. Выходной элемент не может быть отрицанием. Оставшиеся вариантысхем нетрудно перебрать. Для медианы (задача варианта 3) сначала доказывается отсутствиеотрицаний, а потом невозможность схем с двумя конъюнкциями и одной дизъюнкцией (в силусамодвойственности и наоборот).NОтвет. 4 (( ∨ )&&).— СП —4.База данных компании «Рога и Копыта» хранит ф.
и. о., должности, зарплаты сотрудников,проекты и задания. Предполагается, что должность сотрудника определяет его зарплату. Сотрудник может участвовать в нескольких проектах, но в каждом проекте выполняет только однозадание. Должность сотрудника определяется штатным расписанием компании и не зависит отпроектов, в которых он занят.Проектировщик схемы БД предложил всю информацию помещать в одно отношение (на данный момент он уже не работает в компании).
Вот это отношение:СотрудникИванов А. Б.Петров В. Г.Сидоров Д. Е.Иванов А. Б.Петров В. Г.Сидоров Д. Е.ДолжностьруководительпрограммистпрограммиструководительпрограммистпрограммистЗарплата200001500015000200001500015000ПроектПроектПроектПроектПроектПроектПроектXXXYYYЗаданиеЯдроЯдроОболочкаЯдроОболочкаОболочкаПервичный ключ в этом отношении – {Сотрудник, Проект}. Предполагается, что ф.
и. о.сотрудников компании не совпадают.Диаграмма функциональных зависимостей выглядит следующим образом:— Универсиада «Ломоносов» 2015 —стр. 7 из 9Решения задач очного тураТребуется: 1) привести пример аномалии, возникающей при добавлении новых кортежей висходное отношение; 2) используя теорему Хита, выполнить декомпозицию без потерь для исходного отношения так, чтобы все полученные отношения находились в третьей нормальной форме,и чтобы количество полученных отношений было минимальным.
Полученные после декомпозицииотношения следует выписать в ответе.H Решение. После декомпозиции получатся следующие функциональные зависимости:Приводить схему в решении необязательно.NОтвет. 1) Должна быть описана одна из указанных далее аномалий (или обе). а) Невозможнодобавить нового сотрудника (указав должность и зарплату), который еще не участвует ни в одномпроекте. б) Невозможно сохранить данные о новой должности (и соответствующей этой должностизарплате), пока не появится первый сотрудник с этой должностью.2) Должны получиться 3 отношения:СотрудникИванов А.