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

1 Методические требования к подготовке школьников, участвующих в интеллектуальных турнирах по информатике XVII турнир им. М.В. Ломоносова

2 выявление и поощрение талантливых школьников, поощрение интереса школьников к информатике, к возможной работе в сфере ИТ оценка уровня знаний учащихся, отбор участников на очный тур Цели турнира XVII турнир им. М.В. Ломоносова

3 XVII турнир им. М.В. Ломоносова Предметные секции: 9-е классы е классы

4 XVII турнир им. М.В. Ломоносова Структура заданий только задания с кратким ответом Секция 9-х классов: 7 заданий Секция классов: 10 заданий Время выполнения: 90 минут

5 XVII турнир им. М.В. Ломоносова Возможные формы ответов целое число – вариант: ответ – несколько целых чисел, записанных подряд без разделителей Пример. Укажите все верные варианты ответа (в порядке возрастания): 1)слон 2)конь 3)пешка Ответ 13 означает, что выбраны варианты 1 и 3.

6 XVII турнир им. М.В. Ломоносова Возможные формы ответов набор целых чисел через запятую без пробелов Пример. Найдите все значение целочисленных переменных x и y, удовлетворяющих условию … В ответ запишите значения x,y. Возможный ответ: 5,13

7 XVII турнир им. М.В. Ломоносова Возможные формы ответов строка символов Пример 1. Дан алгоритм обработки строк символов… Укажите результат его работы. Возможный ответ: abcde Пример 2. Вася, Коля и Петя участвуют в турнире… Укажите первые буквы имен участников, занявших 1-е, 2-е и 3-е места. Возможный ответ: КВП

8 XVII турнир им. М.В. Ломоносова Возможные формы ответов В ответе не указываются: основания систем счисления, единицы измерения.

9 XVII турнир им. М.В. Ломоносова Оценивание ответов простые задания: 1 – ответ верный, 0 – ответ неверный, сложные задания – до трех баллов: 2 (3) – ответ верный, 0 – ответ неверный, 1 (2) – неверный ответ специального вида

10 XVII турнир им. М.В. Ломоносова Порядок проведения Разрешается: калькулятор (не программируемый). Запрещается: любые другие технические средства, справочная литература

11 XVII турнир им. М.В. Ломоносова Основные темы заданий теоретические знания, технические знания, программирование (старшие классы), логическое и алгоритмическое мышление.

12 XVII турнир им. М.В. Ломоносова Тематика заданий (теоретические знания) системы счисления, комбинаторика, теория информации основы математической логики, элементы теории графов.

13 XVII турнир им. М.В. Ломоносова Тематика заданий (технические знания) устройство компьютера, назначение внешних устройств, представление информации в ЭВМ, файловая система, работа с электронными таблицами.

14 XVII турнир им. М.В. Ломоносова Тематика заданий (программирование) линейные алгоритмы, циклические алгоритмы, сочетания управляющих инструкций, рекурсивные алгоритмы.

15 XVII турнир им. М.В. Ломоносова Представление алгоритмов школьный алгоритмический язык, блок-схемы.

16 XVII турнир им. М.В. Ломоносова Тематика заданий (логическое мышление) головоломки и числовые ребусы, текстовые логические задачи.

17 XVII турнир им. М.В. Ломоносова Среди перечисленных устройств, укажите те, которые предназначены для долговременного хранения данных: 1)оперативная память, 2)RAID-массив, 3)роутер, 4)CD-RW. Устройство компьютера

18 XVII турнир им. М.В. Ломоносова Среди перечисленных устройств, укажите те, которые предназначены для долговременного хранения данных: 1)оперативная память, 2)RAID-массив, 3)роутер, 4)CD-RW. Ответ: 24. Устройство компьютера

19 Флэш-накопитель отформатирован под файловую систему FAT32. Размер кластера -- 4 килобайта. На устройстве созданы две папки. В папке «Документы» записано 9 файлов, размеры которых равны 1000 байтов, 17 Кб, 40 Кб, 70 Кб, 160 Кб, 280 Кб, 326 Кб, 4 Мб и 5 Мб. Единицы измерения информации XVII турнир им. М.В. Ломоносова

20 файл 1000 байтов: 1 кластер = 4 Кб, Единицы измерения информации XVII турнир им. М.В. Ломоносова

21 файл 1000 байтов: 1 кластер = 4 Кб, 17 Кб: 5 кластеров = 20 Кб, Единицы измерения информации XVII турнир им. М.В. Ломоносова

22 файл 1000 байтов: 1 кластер = 4 Кб, 17 Кб: 5 кластеров = 20 Кб, 40 Кб: 40 Кб, 70 Кб: 72 Кб, 160 Кб: 160 Кб, 280 Кб: 280 Кб, 326 Кб: 328 Кб, 4 Мб: 4 Мб, 5 Мб: 5 Мб, всего: Кб. Единицы измерения информации

23 В папке «Результаты эксперимента» записаны 100 файлов по 150 Кб каждый. Единицы измерения информации XVII турнир им. М.В. Ломоносова

24 В папке «Результаты эксперимента» записаны 100 файлов по 150 Кб каждый. 1 файл 150 Кб: 38 кластеров = 152 Кб, 100 файлов: Кб. Единицы измерения информации XVII турнир им. М.В. Ломоносова

25 Содержимое папки «Результаты эксперимента» заархивировали, не удаляя исходные файлы. Архиватор уменьшил суммарный размер на 20%. Единицы измерения информации

26 Содержимое папки «Результаты эксперимента» заархивировали, не удаляя исходные файлы. Архиватор уменьшил суммарный размер на 20%. Данные в исходных 100 файлах: 100 х 150 Кб = Кб, размер архива: 0,8 х Кб = Кб, всего в папке 101 файл размером Кб. Итого на устройстве: = Кб. Единицы измерения информации

27 XVII турнир им. М.В. Ломоносова Системы счисления В системе счисления по основанию p существует ровно 448 трехзначных чисел. Укажите все возможные p с таким свойством.

28 XVII турнир им. М.В. Ломоносова Системы счисления Трехзначное число: abc, a {1,…p–1}, b,c {0,…p}, (p – 1) p p = 448, (p – 1) p 2 = 448.

29 XVII турнир им. М.В. Ломоносова Системы счисления Ищем делитель d=p 2, p>1, числа 448: 448 = = = = , 448 = Делители вида p 2 >1: 2 2 = 4, 2 4 = 16, 2 6 = 64.

30 XVII турнир им. М.В. Ломоносова Системы счисления Проверка: p 2 p p-1 (p-1) p Ответ: 8

31 XVII турнир им. М.В. Ломоносова Измерение информации Станок делает прямоугольные детали. Тип детали - размеры сторон a b, a,b {1,…10} (целые числа). Типы деталей нумеруются по порядку натуральными числами, начиная с 1. Сколько байтов занимает запись о типах 1000 деталей?

32 XVII турнир им. М.В. Ломоносова Измерение информации Количество типов деталей = количеству пар чисел (a, b), a,b {1,…10}, но пары (a, b) и (b, a) считаем равными.

33 XVII турнир им. М.В. Ломоносова Измерение информации Количество типов деталей = количеству пар чисел (a, b), a,b {1,…10}, но пары (a, b) и (b, a) считаем равными. Считаем количество пар (a, b), где a любое, b a.

34 XVII турнир им. М.В. Ломоносова Измерение информации a b a кол-во … … … … … Всего типов деталей: (1+10)/2 * 10 = 55.

35 XVII турнир им. М.В. Ломоносова Измерение информации Число бит для хранения одного из 55 типов: 2 5 =32 < 55 < 2 6 =64,

36 XVII турнир им. М.В. Ломоносова Измерение информации Число бит для хранения одного из 55 типов: 2 5 =32 < 55 < 2 6 =64, запись о типе одной детали: 6 бит,

37 XVII турнир им. М.В. Ломоносова Измерение информации Число бит для хранения одного из 55 типов: 2 5 =32 < 55 < 2 6 =64, запись о типе одной детали: 6 бит, 1000 деталей: 6000 бит = 750 байтов.

38 Логические выражения F(x, y, z) и G(x, y, z) имеют указанные таблицы истинности. Сколько единиц в таблице истинности выражения H(x, y, z) = F( G(z, y, x), x, y z ) ? Математическая логика XVII турнир им. М.В. Ломоносова xyzFG

39 Математическая логика XVII турнир им. М.В. Ломоносова xyzFGG(z,y,x)

40 Математическая логика XVII турнир им. М.В. Ломоносова xyzFGG(z,y,x)

41 Математическая логика XVII турнир им. М.В. Ломоносова xyzFGG(z,y,x) xy z

42 H(x, y, z) = F( G(z, y, x), x, y z ), 6 единиц. Математическая логика XVII турнир им. М.В. Ломоносова xyzFGG(z,y,x) xy z H

43 XVII турнир им. М.В. Ломоносова Математическая логика Пусть Div(x,y) обозначает «x – делитель y». Сколько целых чисел из отрезка [1; 10] удовлетворяют логическому выражению: x 7 (x 4 Div(x,28)) ?

44 XVII турнир им. М.В. Ломоносова Математическая логика Преобразовать импликации по правилу: a b ~ a b.

45 XVII турнир им. М.В. Ломоносова Математическая логика Преобразовать импликации по правилу: a b ~ a b. x 7 (x 4 Div(x,28)) ~ ~ x 7 x 4 Div(x,28) ~ ~ x > 7 x < 4 Div(x,28) (x [1; 10]) 8, 9, 10 1, 2, 3 4, 7 (1, 2) Ответ: 8

46 XVII турнир им. М.В. Ломоносова Что будет выведено на экран в результате выполнения программы? a := 2 нц для i := 1 до 3 a := a * i + 1 кц вывод a Программирование

47 XVII турнир им. М.В. Ломоносова Что будет выведено на экран в результате выполнения программы? a := 2 нц для i := 1 до 3 a := a * i + 1 кц вывод a до цикла цикл i a Ответ: 22.

48 цел A[1:10], B[1:10] N := 10 нц для i := 1 до N ввод A[ i ] кц B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] Введены числа: 12, 5, 3, 7, 10, 11, 10, 1, 15, 8. Результат работы - ?

49 цел A[1:10], B[1:10] N := 10 нц для i := 1 до N | ввод элементов массива A ввод A[ i ] кц B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N]

50 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] B[1] = A[1]

51 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2]

52 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3]

53 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3] B[i] = A[1] + A[2] + … + A[i]

54 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] A: 12, 5, 3, 7, 10, 11, 10, 1, 15, 8 B: 12, B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3] B[i] = A[1] + A[2] + … + A[i]

55 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] A: 12, 5, 3, 7, 10, 11, 10, 1, 15, 8 B: 12, 17, B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3] B[i] = A[1] + A[2] + … + A[i]

56 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] A: 12, 5, 3, 7, 10, 11, 10, 1, 15, 8 B: 12, 17, 20 B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3] B[i] = A[1] + A[2] + … + A[i]

57 цел A[1:10], B[1:10] N := 10 | ввод элементов массива A … B[1] := A[1] нц для i := 2 до N B[ i ] := B[ i – 1 ] + A[ i ] кц вывод B[N] A: 12, 5, 3, 7, 10, 11, 10, 1, 15, 8 B: 12, 17, 20, 27, 37, 48, 58, 59, 74, 82 - ответ B[1] = A[1] B[2] = B[1] + A[2] = = A[1] + A[2] B[3] = B[2] + A[3] = = A[1] + A[2] + A[3] B[i] = A[1] + A[2] + … + A[i]

58 Двумерные массивы ввод x res := 0 нц для i := 1 до N s := 0 нц для j := 1 до i s := s + T [ i, j ] + T [ j, i ] кц если s > x то res := res + s все кц вывод res N = 4, x = 13, T – таблица размера N N T:

59 Двумерные массивы ввод x res := 0 нц для i := 1 до N s := 0 нц для j := 1 до i s := s + T [ i, j ] + T [ j, i ] кц если s > x то res := res + s все кц вывод res N = 4, x = 13, T – таблица размера N N T: i =

60 Двумерные массивы ввод x res := 0 нц для i := 1 до N s := 0 нц для j := 1 до i s := s + T [ i, j ] + T [ j, i ] кц если s > x то res := res + s все кц вывод res N = 4, x = 13, T – таблица размера N N T: i =

61 Двумерные массивы ввод x res := 0 нц для i := 1 до N s := 0 нц для j := 1 до i s := s + T [ i, j ] + T [ j, i ] кц если s > x то res := res + s все кц вывод res N = 4, x = 13, T – таблица размера N N T: i s 1) 20 2) 12 3) 17 4) 12

62 Двумерные массивы ввод x res := 0 нц для i := 1 до N s := 0 нц для j := 1 до i s := s + T [ i, j ] + T [ j, i ] кц если s > x то res := res + s все кц вывод res N = 4, x = 13, T – таблица размера N N T: i s 1) 20 2) 12 3) 17 4) 12 Суммы, большие x, добавляется к res. Ответ: 37.

63 алг ПОИСК(цел x, цел y) нач если x + y > 10 то вывод (, x,,, y, ) иначе ПОИСК(x + 5, y – 2) ПОИСК(x + 1, y + 1) все кон Рекурсивный алгоритм XVII турнир им. М.В. Ломоносова Результат работы ПОИСК(2,1) (кол-во пар чисел на экране) ?

64 …….. ПОИСК(x + 5, y – 2) ПОИСК(x + 1, y + 1) ……… Рекурсивный алгоритм XVII турнир им. М.В. Ломоносова ПОИСК(2,1) 2, 1 7, –13, 2 x+5, y–2x+1, y+1

65 …….. ПОИСК(x + 5, y – 2) ПОИСК(x + 1, y + 1) ……… Рекурсивный алгоритм XVII турнир им. М.В. Ломоносова ПОИСК(2,1) ……………. Ответ: 12 2, 1 7, –13, 2 x+5, y–2x+1, y+1 2, 1 7, –13, 2 x+5, y–2x+1, y+1 12, –38, 0 4, 3

66 XVII турнир им. М.В. Ломоносова Литература: 1. Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по информатике: всероссийская олимпиада школьников. – М.: Бином, Ресурсы Интернет: 1. Красноярская школа программиста: 2. Дистанционная подготовка по информатике: 3. Сайт «Омские олимпиады»

67 XVII турнир им. М.В. Ломоносова Приглашаем принять участие в нашем турнире и желаем успехов