25.12 в 301 кабинете 10д класс
29.12 в 302 кабинете 11д класс
10д класс - письменная контрольная в формате тестовой части ЕГЭ (1-23 задания)
Оценка ставится:
«отлично» – 17-23 баллов;
«хорошо» – 12-16 баллов;
«удовлетворительно» – 8-11 баллов;
«неудовлетворительно» – 0-7 баллов.
Темы к устному зачету в 11Д классе
1. Уточнение понятия алгоритма. Универсальный исполнитель «Машина Тьюринга».
2. Уточнение понятия алгоритма. Универсальный исполнитель «Машина Поста».
3. Уточнение понятия алгоритма. Универсальный исполнитель «Алгорифмы Маркова».
4. Сложность алгоритма сортировки обменом.
5. Сложность алгоритма сортировки вставками.
6. Сложность алгоритма сортировки выбором.
7. Сложность алгоритма быстрой сортировки.
8. Сложность алгоритма сортировки подсчетом.
9. Сложность алгоритмов поиска (линейный и бинарный).
10. Инвариант цикла в алгоритме Евклида и других.
11. Алгоритм нахождения простых чисел. Решето Эратосфена.
12. Алгоритм сложения двух «длинных» чисел. Числа Фибоначчи.
13. Создание базы данных с помощью структур. Хранение данных с помощью типизированных файлов. Поиск и выборка данных.
14. Структура. Хранение данных с помощью типизированных файлов. Сортировка в базах данных. Составление отчетов.
15. Динамические массивы. Тип вектор.
16. Динамические структуры данных: списки (словари). Задача о частоте слов.
17. Динамические структуры данных: стек. Скобочные выражения.
18. Динамические структуры данных: очередь. Задача о раскраске.
19. Динамические структуры данных: деревья. Вычисление арифметического выражения.
20. Граф. Представление графа в программировании.
21. Граф. Задача Прима-Крускала. "Жадный" алгоритм.
22. Граф. Кратчайшие маршруты. Алгоритм Дейкстры.
23. Граф. Кратчайшие маршруты. Алгоритм Флойда.
24. Динамическое программирование. Поиск оптимального решения. Задача о куче.
25. Динамическое программирование. Количество решений.
Задачи:
Билет состоит из 2-х вопросов:
1. Алгоритм решения задачи на компьютере и теоретическое обоснование (см. темы).
2. Тестовое задание из ЕГЭ (1 часть:11,12,19-23)
Критерии оценивания:
От 0 до 2 баллов (0 – нет ответа или неправильно; 1 – частично отвечен, неполный ответ, 2 – полный и правильный ответ) можно получить:
o за объяснение теории,
o за приведенный пример,
o за программу на компьютере,
o за тестовое задание ЕГЭ.
Оценка ставится:
«отлично» – 7-8 баллов;
«хорошо» – 5-6 баллов;
«удовлетворительно» – 3-4 балла;
«неудовлетворительно» – 0-2 балла.
29.12 в 302 кабинете 11д класс
10д класс - письменная контрольная в формате тестовой части ЕГЭ (1-23 задания)
Оценка ставится:
«отлично» – 17-23 баллов;
«хорошо» – 12-16 баллов;
«удовлетворительно» – 8-11 баллов;
«неудовлетворительно» – 0-7 баллов.
Темы к устному зачету в 11Д классе
1. Уточнение понятия алгоритма. Универсальный исполнитель «Машина Тьюринга».
2. Уточнение понятия алгоритма. Универсальный исполнитель «Машина Поста».
3. Уточнение понятия алгоритма. Универсальный исполнитель «Алгорифмы Маркова».
4. Сложность алгоритма сортировки обменом.
5. Сложность алгоритма сортировки вставками.
6. Сложность алгоритма сортировки выбором.
7. Сложность алгоритма быстрой сортировки.
8. Сложность алгоритма сортировки подсчетом.
9. Сложность алгоритмов поиска (линейный и бинарный).
10. Инвариант цикла в алгоритме Евклида и других.
11. Алгоритм нахождения простых чисел. Решето Эратосфена.
12. Алгоритм сложения двух «длинных» чисел. Числа Фибоначчи.
13. Создание базы данных с помощью структур. Хранение данных с помощью типизированных файлов. Поиск и выборка данных.
14. Структура. Хранение данных с помощью типизированных файлов. Сортировка в базах данных. Составление отчетов.
15. Динамические массивы. Тип вектор.
16. Динамические структуры данных: списки (словари). Задача о частоте слов.
17. Динамические структуры данных: стек. Скобочные выражения.
18. Динамические структуры данных: очередь. Задача о раскраске.
19. Динамические структуры данных: деревья. Вычисление арифметического выражения.
20. Граф. Представление графа в программировании.
21. Граф. Задача Прима-Крускала. "Жадный" алгоритм.
22. Граф. Кратчайшие маршруты. Алгоритм Дейкстры.
23. Граф. Кратчайшие маршруты. Алгоритм Флойда.
24. Динамическое программирование. Поиск оптимального решения. Задача о куче.
25. Динамическое программирование. Количество решений.
Задачи:
1. Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.
2. Напишите программу для машины Поста, которая увеличивает в 2 раза число, записанное в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.
3. Напишите алгорифм Маркова, который «сортирует» цифры двоичного числа так, чтобы сначала стояли все нули, а потом – все единицы.
4. Напишите программу, которая сортирует элементы массива по возрастанию последней цифры десятичной записи чисел. (обменом)
5. Напишите программу, которая находит три наименьших элемента массива и переставляет их в начало массива. Остальные элементы должны следовать далее в том же порядке. (вставками)
6. Напишите программу, которая сортирует по возрастанию все элементы массива с нечётными значениями. При этом все элементы с чётными значениями должны остаться на своих местах. (выбором)
7. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. При этом элементы из первой половины не должны перемещаться во вторую и наоборот. (быстрая)
8. Напишите программу, которая сортирует массив целых чисел и определяет количество различных значений в нём. (подсчетом)
9. Найдите такое число x, что x2+sqrt(x)=C , с точностью не менее 6 знаков после точки. (линейный и бинарный поиск)
10. Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять наименьшее и наибольшее значение А.
11. Напишите программу, которая выводит все простые числа в диапазоне от K до N, оканчивающиеся на цифру 3.
12. Напишите программу для вычисления последней и первой цифры N-го члена последовательности Фибоначчи.
13. С помощью struct создайте БД на основе данных в текстовом файле input1.txt. Определите самый калорийный и низкокалорийный продукт.
14. С помощью struct создайте БД на основе данных в текстовом файле input2.txt. Определите 10 самых густонаселенных городов.
15. Дан набор целых чисел, заканчивающихся 0. Вывести количество введенных чисел, отсортированный по возрастанию массив, и подсчитать среднеарифметическое четных чисел.
16. На вход программы поступает последовательность из N натуральных чисел. Требуется определить, какая цифра чаще всего встречается в десятичной записи этих чисел. Если таких цифр несколько, необходимо вывести их все в порядке убывания – от большей к меньшей.
17. Напишите программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме. В выражении используются только целые числа и знаки арифметических операций. Знак '/' обозначает целочисленное деление. Элементы постфиксной записи разделены пробелами. Программа должна вывести значение переданного ей выражения. Если выражение записано неверно, программа должна вывести слово 'ERROR'.
(Реализация сортировки с помощью дерева на C++)
18. В файле input.txt записана информация о цвете пикселей цветного рисунка. Код цвета каждого пикселя – целое число в диапазоне от 0 до 255. Напишите программу, которая выполняет заливку области заданным цветом, начиная с заданной точки. Заливка происходит по всем 8-ми направлениям.
19. Напишите программу, которая преобразует символьную запись арифметического выражения в постфиксную и префиксную форму записи. В выражении используются только целые числа и знаки арифметических операций.
20. Неориентированный граф задан списком ребер. Найдите степени всех вершин графа и выведите матрицу смежности.
21. Требуется найти в связном графе остовное дерево минимального веса. Граф представлен в виде списка начала и конца ребер и их веса. Вывести минимальный вес, пройденного пути, а также список вершин, по которым этот путь пройден.
22. Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой, а также сам путь в виде списка номеров вершин. Если пути между указанными вершинами не существует, то вывести -1.
23. Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.
24. Кладоискатель хочет перейти из левого верхнего угла поля размером N на M клеток в правый нижний. За один шаг он может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Поле заполнено золотыми монетами, которые можно забрать по пути. Количество монет в каждой клетке поля известно. Определите путь, по которому должен пройти кладоискатель, чтобы он смог собрать как можно больше монет. Выведите это количество.
25. Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.
2. Напишите программу для машины Поста, которая увеличивает в 2 раза число, записанное в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.
3. Напишите алгорифм Маркова, который «сортирует» цифры двоичного числа так, чтобы сначала стояли все нули, а потом – все единицы.
4. Напишите программу, которая сортирует элементы массива по возрастанию последней цифры десятичной записи чисел. (обменом)
5. Напишите программу, которая находит три наименьших элемента массива и переставляет их в начало массива. Остальные элементы должны следовать далее в том же порядке. (вставками)
6. Напишите программу, которая сортирует по возрастанию все элементы массива с нечётными значениями. При этом все элементы с чётными значениями должны остаться на своих местах. (выбором)
7. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. При этом элементы из первой половины не должны перемещаться во вторую и наоборот. (быстрая)
8. Напишите программу, которая сортирует массив целых чисел и определяет количество различных значений в нём. (подсчетом)
9. Найдите такое число x, что x2+sqrt(x)=C , с точностью не менее 6 знаков после точки. (линейный и бинарный поиск)
10. Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять наименьшее и наибольшее значение А.
11. Напишите программу, которая выводит все простые числа в диапазоне от K до N, оканчивающиеся на цифру 3.
12. Напишите программу для вычисления последней и первой цифры N-го члена последовательности Фибоначчи.
13. С помощью struct создайте БД на основе данных в текстовом файле input1.txt. Определите самый калорийный и низкокалорийный продукт.
14. С помощью struct создайте БД на основе данных в текстовом файле input2.txt. Определите 10 самых густонаселенных городов.
15. Дан набор целых чисел, заканчивающихся 0. Вывести количество введенных чисел, отсортированный по возрастанию массив, и подсчитать среднеарифметическое четных чисел.
16. На вход программы поступает последовательность из N натуральных чисел. Требуется определить, какая цифра чаще всего встречается в десятичной записи этих чисел. Если таких цифр несколько, необходимо вывести их все в порядке убывания – от большей к меньшей.
17. Напишите программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме. В выражении используются только целые числа и знаки арифметических операций. Знак '/' обозначает целочисленное деление. Элементы постфиксной записи разделены пробелами. Программа должна вывести значение переданного ей выражения. Если выражение записано неверно, программа должна вывести слово 'ERROR'.
(Реализация сортировки с помощью дерева на C++)
18. В файле input.txt записана информация о цвете пикселей цветного рисунка. Код цвета каждого пикселя – целое число в диапазоне от 0 до 255. Напишите программу, которая выполняет заливку области заданным цветом, начиная с заданной точки. Заливка происходит по всем 8-ми направлениям.
19. Напишите программу, которая преобразует символьную запись арифметического выражения в постфиксную и префиксную форму записи. В выражении используются только целые числа и знаки арифметических операций.
20. Неориентированный граф задан списком ребер. Найдите степени всех вершин графа и выведите матрицу смежности.
21. Требуется найти в связном графе остовное дерево минимального веса. Граф представлен в виде списка начала и конца ребер и их веса. Вывести минимальный вес, пройденного пути, а также список вершин, по которым этот путь пройден.
22. Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой, а также сам путь в виде списка номеров вершин. Если пути между указанными вершинами не существует, то вывести -1.
23. Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.
24. Кладоискатель хочет перейти из левого верхнего угла поля размером N на M клеток в правый нижний. За один шаг он может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Поле заполнено золотыми монетами, которые можно забрать по пути. Количество монет в каждой клетке поля известно. Определите путь, по которому должен пройти кладоискатель, чтобы он смог собрать как можно больше монет. Выведите это количество.
25. Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.
Билет состоит из 2-х вопросов:
1. Алгоритм решения задачи на компьютере и теоретическое обоснование (см. темы).
2. Тестовое задание из ЕГЭ (1 часть:11,12,19-23)
Критерии оценивания:
От 0 до 2 баллов (0 – нет ответа или неправильно; 1 – частично отвечен, неполный ответ, 2 – полный и правильный ответ) можно получить:
o за объяснение теории,
o за приведенный пример,
o за программу на компьютере,
o за тестовое задание ЕГЭ.
Оценка ставится:
«отлично» – 7-8 баллов;
«хорошо» – 5-6 баллов;
«удовлетворительно» – 3-4 балла;
«неудовлетворительно» – 0-2 балла.
Комментариев нет :
Отправить комментарий