- •Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •Системы счисления, переводы чисел из одной позиционной системы в другую.
- •Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.
- •Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •Статические и динамические переменные, динамическая память, работа с динамическими переменными.
- •Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •Использование динамических переменных для представления и работы со стеком.
- •Очередь, реализация очереди массивом.
- •Очередь, представление и реализация основных операций с помощью динамических переменных.
- •Реализация основных операций со списком: добавление, удаление, поиск.
- •Деревья, основные операции над деревьями, представление дерева массивом.
- •Двусвязные линейные списки, построение и обход бинарного дерева.
- •Операции поиска и удаления в бинарном дереве.
- •Понятие графа, представление графа на эвм.
- •Представление графа списком инцидентности, алгоритм обхода графа в глубину.
- •Представление графа списком списков, алгоритм обхода графа в ширину.
- •Технологии программирования, концепции, заложенные в ооп.
- •Основные понятия ооп: абстракция, инкапсуляция, полиморфизм.
- •Понятие объекта, его состояние и поведение, классы, определение класса и объявление класса.
- •Статические, дружественные и виртуальные поля и методы, особенности их использования.
- •Абстрактные классы, их назначение и использование.
- •Понятие области видимости: общие, личные, защищённые и опубликованные поля и методы объекта.
- •Указатель this и перегрузка методов.
- •Использование классов, различные способы инициализации.
- •Использование классов, работа с массивами и указателями на обьекты.
- •Наследование, пример использования наследования.
- •Конструкторы и деструкторы, их назначение и использование.
- •Архитектура пк, основные функциональные устройства и их назначение.
- •Мп с точки зрения программиста, регистры общего назначения.
- •Оперативная память, понятие исполняемого и физического адреса, сегментные регистры.
- •Регистр флажков, его назначение и использование.
- •Форматы данных и форматы команд, машинный формат двухадресной машины.
- •Адресация операндов, способы адресации, примеры команд с различными способами адресации.
- •Понятие команды и директивы в Ассемблере, формат команды и директивы.
- •Структура программы на Ассемблере с использованием стандартных директив сегментации.
- •Основные элементы языка Ассемблер: имена, константы, переменные, выражения.
- •Директивы определения данных и памяти, примеры.
- •Команда прерывания, команды работы со стеком.
- •Упрощённые директивы сегментирования, структура программы с использованием точечных директив, пример программы.
- •Этапы выполнения Ассемблерной программы на эвм, понятие com-файла.
- •Различие между exe - и com – файлами, требования, предъявляемые к исходному модулю, предназначенному для создания com – файла, примеры программ.
- •Понятие структурного программирования, этап проектирования – композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.
- •Понятие частичной и полной корректности программы, правила вывода – общий вид, правила консеквенции.
- •Правила вывода для операторов: пустого, присваивания, составного.
- •Правила вывода для операторов ветвления.
- •Правила вывода циклов с предусловием и посусловием.
Понятие алгоритма: рекурсивные функции, системы текстовых замен.
Алгоритм - конечная последовательность действий, приводящих к результату.
Терминистический, если для любой последовательности шагов алгоритма, он заканчивается за конечное число шагов. Детерминированный – независимо от кол-ва шагов результат определяется однозначно. Детерминистический – нет никакой последовательности в выборе след. Шага.
Свойства алгоритма:
1) конечность
2) определенность (каждый шаг должен быть точно определен: перед началом шага должен быть определен вес и данные)
3) результативность,
4) массовость,
5) алгоритм состоит из конечного числа шагов,
6) эффективность
Алгоритм Евклида – находит НОД двух чисел (вычитает из наиб наим и сравнивает их).
Существование или не существование можно определить, если найти такой математический объект, который будет существовать тогда, когда существует алгоритм.
1) Оператор рекурсии строит рекурсивную функцию след. Образом: значение искомой функции при нулевом значении главного дополнительного аргумента считать значением функции f1, а для последующего значения главного дополнительного аргумента значение функции f2. Для предыдущего значения ГДА и для значения ВДА, совпадающего со значением искомой функции на предыдущем шаге : f(0)=f1;f(i)=fi(i,f(i));
Пример (для функции f(x)=x-1): f::=R {φ0, ψ2, 1(x, y), x(y)}
f (0)=y0=0
f(1)=f2(0,0)= ψ2,1(0,0)=0
f(2)= f3(0,0)= ψ2,1(1,0)=1
2) Оператор подстановки или суперпозиции F(f1,..,fn)
Сначала вычисляются значения f1 и f2 и используют как аргумент для вычисления функции F: τ(y)=λ(λ(y))=λ(y’)=y’’
3) Оператор минимизации или построения по первому нулю.
f::=μ{f1,y}; f(x1,..xn)= μ{f1(x1,..xn, y),y}
Передавать значение доп аргументу последовательно, начиная с нуля, вычисляя при этом значение ф-ии f1. Как только значение стало равно 0, значением искомой ф-ии можно считать значение доп. Аргумента при тех же значениях главного арг, при кот вычислялось значение f1.
Пример: f(x)::= μ(ψ2,1(x,y), y)
f(0)=0; f(i)= ψ2,1(i,y)=i
Классом рекурсивных ф-ий исчерпывается класс вычислительных ф-ий.
СТЗ- конечное множество замен R над множеством символов vЄV*. Пусть V множество символов тогда пара (v,w) ЄV*xV* замена над V. Конечное множ-во R замен будем называть СТЗ, а элементы этой системы правилами ТЗ.
Замена s->t применение правила v->w, если есть слова a,v,w,z ЄV*, такие что справедливо: s=a*v*z; t=a*w*z
Пример: пусть есть правило замены Н на РАБ, s=БАНАН a=БА v=Н
w=РАБ z=АН, тогда получим : ба*н*ан->ба*раб*ан
Слово s будет терминальным для СТЗ R, если не существует слова vЄV*: справедлива замена s->t Применение правила из R. Алг работает так: если одно из правил множ-ва R применимо к слову t, значит существует sЄV*:t->s применение одного из правил множ-ва R, то применив правило к t и затем применив снова к слову s, в противном случае прекращаем выполнение алг.
Системы счисления, переводы чисел из одной позиционной системы в другую.
Система счисления- совокупность правил наименований и записи чисел.
- позиционные(значение цифры числа зависит от ее положения)
- римская(не зависит)
1) для перевода двоичного числа в десятичное надо его записать в виде многочлена, состоящего из произведений цифр числа и соответствующей степени 2 и вычислить по правилам арифметики
2)для перевода восьмеричного числа в десятичное его надо записать в виде многочлена, состоящего из произведений цифр числа в соответствующей степени 8(аналогично для 16)
3) для перевода десятичного числа в двоичную СС нудно делить десятичное число на 2 пока остаток не будет =1 или =0 затем записать 4исло а обратном порядке (аналогично для 8 и 16)
4) чтобы перевести число из двоичной в восьмеричную, надо разбить его на триады, и начиная с младшего разряда и каждую триаду заменить 8-ричной цифрой (аналогично для 16)
5) для перевода из 8-ой в двоичную надо каждую цифру заменить эквивалентной ей двоичной триадой (аналог для 16)
5)при переходе из 8-ричной в 16-ричную нужно переводить 4ерез двоичную СС.
Понятие подпрограммы, функции, возвращающие значения в С/С++, описание и использование.
Понятие подпрограммы, функции, не возвращающей значение в С/С++, описание и использование.
Подпрограмма - отдельная структурна единица, имеющая собственное имя, реализующая вспомогательный алгоритм, который неоднократно используется в основной программе или в другой подпрограмме, с различными значениями этих величин, называемых параметрами.
Назначение:
1) позволяет избегать дублирования программы, делает ее короче;
2) Делает структуру программы 4еткой и более понятной. Программа с использованием подпрограммы более эффективна с точки зрения разработки, отладки, модификации. Отдельные подпрограммы могут храниться в отдельных файлах(смысл модульного программирования)
3) подпрограммы позволяют расширять языки программирования, добавив в него новые ф-ии, операции, операторы- процедуры. Программа, разрабатывая новый проект, создает собственную библиотеку подпрограмм, которые затем могут использоваться для разработки других проектов.
Функция- именованная последовательность описаний и операторов, выполняющая какое – либо законченное действие. Ф-ия может принимать параметры возвращать значения.
Пример ф-ии возвращающей сумму 2-х чисел:
#include <iostream>
Using namespace std;
Int sum(int x, int y)
{return x+y;}
Int main(){ int a=5, b=6,c;
C=sum(a,b);
Cout<<”sum=”<<c<<endl;
Cout<<”sum=”<<sum(a,b);
Return 0;
}
В С\С++ используется один тип подпрограмм - функция, но они могут выдавать один результат и тогда обращение к ним - указатель ф-ии (фактический параметр) и в этом слу4ае обращение-операнд, и когда несколько результатов и выходные параметры-результаты (обращение к ф-ии- самостоятельный оператор), а в С это ф-ии не возвращающие зна4ение.
Пример: #include <stdio.h>
Void p (int k(по значению), int *d (по адресу указатель)){
Int j; *d=1;
For (j=2;j<=k;j++) *d=*d*j;
Return;}